#define MAX_SIZE 100
typedef struct LNode {
int data;
struct LNode *next;
}LNode, *LinkList;
void createLinkList(LinkList &L) {
int data;
scanf("%d", &data);
if (data == 0) {
L = NULL;
return;
}
else {
L = (LinkList)malloc(sizeof(LNode));
L->data = data;
L->next = NULL;
createLinkList(L->next);
return;
}
}
//选择排序
void arrayselectsort(int A[], int n) {
for (int i = 0;i < n - 1;i++) {
int min= i;
for (int j = i + 1;j < n;j++) {
if (A[j] < A[min])min = j;
}
if (min != i) {
int temp = A[min];
A[min] = A[i];
A[i] = temp;
}
}
}
LinkList getminpre(LinkList L) {
LinkList minpre, min, pre, cur;
minpre = NULL;
min = L;
pre = L;
cur = L->next;
while (cur) {
if (cur->data < min->data) {
minpre = pre;
min = cur;
}
pre = cur;
cur = cur->next;
}
return minpre;
}
void linklistselectsort(LinkList L) {
LinkList tail, cur, minpre, min;
tail = NULL;
minpre = NULL;
min = NULL;
cur = L;
while (cur) {
min = cur;
minpre = getminpre(cur);
if (minpre) {
min = minpre->next;
minpre->next = min->next;
}
cur = cur == min ? cur->next : cur;
if (tail == NULL) {
L->next = min;
}
else {
tail->next = min;
}
tail = min;
}
}
//快速排序
int pivot(int A[], int low, int high) {
int k = A[low];
while (low<high) {
while (low<high&&A[high]>=k)high--;
A[low] = A[high];
while (low<high&&A[low]<=k)low++;
A[high] = A[low];
}
A[low] = k;
return low;
}
void arrayquicksort(int A[], int low, int high) {
if (low < high) {
int k = pivot(A, low, high);
arrayquicksort(A, low, k - 1);
arrayquicksort(A, k + 1, high);
}
}
LinkList partition(LinkList head, LinkList tail) {
if (head->next == tail || head->next->next == tail) {
return head;
}
LinkList r = head, p = head->next, pre = head;
int x = p->data;
while (p != tail) {
if (p->data < x) {
if (p == r->next) {
r = r->next;
pre = p;
p = p->next;
}
else {
pre->next = p->next;
p->next = r->next;
r->next = p;
r = r->next;
p = pre->next;
}
}
else
{
pre = p;
p = p->next;
}
}
return r->next;
}
void linklistquicksort(LinkList head,LinkList tail) {
if (head->next == tail || head->next->next == tail) {
return;
}
else{
LinkList r = partition(head, tail);
linklistquicksort(head, r);
linklistquicksort(r, tail);
}
}
int findmedian(int A[], int n) {
int low = 0, low_temp = 0;
int high = n - 1, high_temp = n - 1;
int flag = 1;
int pivot;
int k = n / 2;
while (flag) {
pivot = A[low];
while (low < high) {
while (low < high&&A[high] >= pivot)high--;
A[low] = A[high];
while (low < high&&A[low] <= pivot)low++;
A[high] = A[low];
}
A[low] = pivot;
if (low == k - 1)flag = 0;
else if (low < k - 1) {
high = high_temp;
low = low + 1;
low_temp = low;
}
else {
high = high - 1;
high_temp = high;
low = low_temp;
}
}
return A[low];
}
//归并算法
int B[MAX_SIZE];
void arraymerge(int A[], int low,int mid, int high) {
for (int i = low;i <= high;i++) {
B[i] = A[i];
}
int i, j, k;
for (i = low, j = mid + 1,k = low;i <= mid&&j <= high;) {
if (B[i] <= B[j]) {
A[k++] = B[i++];
}
else {
A[k++] = B[j++];
}
}
while (i <= mid)A[k++] = B[i++];
while (j <= high)A[k++] = B[j++];
}
void arraymergesort(int A[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
arraymergesort(A, low, mid);
arraymergesort(A, mid + 1, high);
arraymerge(A, low,mid, high);
}
}
LinkList linklistmerge(LinkList left,LinkList right) {
LinkList temp = (LinkList)malloc(sizeof(LNode));
LinkList p=temp;
while (left&&right) {
if (left->data <= right->data) {
p->next = left;
p = p->next;
left = left->next;
}
else {
p->next = right;
p = p->next;
right = right->next;
}
}
if (left)p->next = left;
if (right)p->next = right;
return temp->next;
}
LinkList linklistmergesort(LinkList head) {
if (!head || !head->next) {
return head;
}
LinkList p = head, q = head->next;
while (q&&q->next) {
p = p->next;
q = q->next->next;
}
LinkList right = linklistmergesort(p->next);
p->next = NULL;
LinkList left = linklistmergesort(head);
return linklistmerge(left, right);
}
//冒泡排序
void arraybubblesort(int A[], int n) {
int flag;
for (int i = 0;i < n;i++) {
flag = 1;
for (int j = 0;j < n - i - 1;j++) {
if (A[j + 1] < A[j]){
int temp = A[j + 1];
A[j + 1] = A[j];
A[j] = temp;
flag = 0;
}
}
if (flag == 1)break;
}
}
void linklistbubblesort(LinkList L) {
LinkList p, q, tail;
tail = NULL;
while (L->next->next != tail) {
p = L;
q = L->next;
while (q->next != tail) {
if (q->data > q->next->data) {
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
q = p->next;
}
q = q->next;
p = p->next;
}
tail = q;
}
}
//插入排序
void arrayinsertsort(int A[], int n) {
int i, j, k;
for (i = 1;i < n;i++) {
if (A[i] < A[i - 1]) {
k = A[i];
for (j = i - 1;A[j] > k&&j >= 0;--j) {
A[j + 1] = A[j];
}
A[j + 1] = k;
}
}
}
void linklistinsertsort(LinkList L) {
LinkList p, q, r, u;
p = L->next;
L->next = NULL;
while (p != NULL) {
r = L;
q = L->next;
while (q != NULL&&q->data <= p->data) {
r = q;
q = q->next;
}
u = p->next;
p->next = r->next;
r->next = p;
p = u;
}
}
//堆排序
void AdjustDown(int A[], int k, int len) {
int temp = A[k];
for (int i = 2 * k;i < len;i = 2 * i) {
if (i < len - 1 && A[i] < A[i + 1]) {
i++;
}
if (A[i] <= temp) {
break;
}
else {
A[k] = A[i];
k = i;
}
}
A[k] = temp;
}
void BuildMaxHeap(int A[], int len) {
for (int i = (len - 1) / 2;i >= 0;i--) {
AdjustDown(A, i, len);
}
}
void heapsort(int A[], int len) {
BuildMaxHeap(A, len);
for (int i = len - 1;i >= 0;i--) {
int temp = A[0];
A[0] = A[i];
A[i] = temp;
AdjustDown(A, 0, i - 1);
}
}
void findmink(int A[], int len, int k) {
BuildMaxHeap(A, k);
for (int i = k + 1;i < len;i++) {
if (A[i] < A[0]) {
A[0] = A[i];
AdjustDown(A, 0, k);
}
}
}
//
