目录
1.选择算法
2.归并排序
3.链表归并
4.堆排序
1.选择算法
#include
#define less(A,B) (A)<(B)
#define exch(A,B) {int c = A; A = B; B = c;}
void select1(int a[], int head, int end, int n);
void select2(int b[], int head, int end, int n);
int Partition(int a[], int head, int end);
int main()
{
int n, k;
int a[15] = { 2,3,1,4,6,8,7,0,9,5,12,34,53,12,50 };
int b[15] = { 6,34,1,22,3,8,7,39,9,5,12,34,53,2,18 };
printf("输入a中查找第n位的数字：");
scanf_s("%d", &n);
select1(a, 0, 14, n);
printf("输入b中查找第n位的数字：");
scanf_s("%d", &k);
select2(b, 0, 14, k);
printf("a:%dn",a[n]);
printf("b:%dn", b[k]);
}
void select1(int a[], int head, int end, int n)
{
int i;
if (head >= end)
return;
i = Partition(a, head, end);
if (i < n)
select1(a, i + 1, end, n);
else
select1(a, head, i - 1, n);
}
void select2(int b[], int head, int end, int n)
{
int i;
while (head <= end)
{
i = Partition(b, head, end);
if (i > n)
end = i - 1;
else
head = i + 1;
}
}
int Partition(int num[], int head, int end)
{
int i = head - 1, j = end;
int numb = num[end];
while(1)
{
while (less(num[++i], numb));
while (less(numb, num[--j]))
{
if (j == head)
break;
}
if (i >= j)
break;
exch(num[i], num[j]);
}
exch(num[i], num[end]);
return i;
}
2.归并排序
两种归并，自底向下和自顶向上。
归并图
自顶向下归并排序 自底向上归并排序
3 2 4 6 9 1 5 0 8 7 3 2 4 6 9 1 5 0 8 7
2 3**************** 2 3****************
****4 6************ ****4 6************
2 3 4 6************ ********1 9********
********1 9******** ************0 5****
************0 5**** ****************7 8
************0 1 5 9 2 3 4 6************
0 1 2 3 4 5 6 9**** ********0 1 5 9 7 8
****************7 8 0 1 2 3 4 5 6 9****
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
#includevoid Merge(int a[], int head, int m, int end); void MergeSortA(int a[], int head, int end); void MergeSortB(int a[], int head, int end); int main() { int a[10] = { 3,2,4,6,9,1,5,0,8,7 }; int b[10] = { 3,2,4,6,9,1,5,0,8,7 }; MergeSortB(a, 0, 9); MergeSortA(b, 0, 9); for (int i = 0; i < 10; i++) printf("%d ", a[i]); } void Merge(int a[], int head, int m, int end) { if (head >= end) return; int c[10] = { 0 }; int i = head, j = m + 1, t; for (t = 0; t < end - head + 1; t++) { if (i == m + 1) { c[t] = a[j++]; continue; } if (j == end + 1) { c[t] = a[i++]; continue; } c[t] = a[i] < a[j] ? a[i++] : a[j++]; } i = head; for (t = 0; t < end - head + 1; t++) { a[i++] = c[t]; } } void MergeSortA(int a[], int head, int end) { int m = (end + head) / 2; if (head >= end) return; MergeSortA(a, head, m); MergeSortA(a, m + 1, end); Merge(a, head, m, end); } void MergeSortB(int a[], int head, int end) { int i, m; for (m = 1; m < end; m = m * 2) { for (i = 0; i < end; i = i + m * 2) { if (i + m * 2 - 1 < end) Merge(a, i, i + m - 1, i + m * 2 - 1); else { if (i + m < end) Merge(a, i, i + m - 1, end); else Merge(a, i, (i + end) / 2, end); } } } }
3.链表归并
传入的链表是有序链表，从小到大传入。
下面有一种方法没有用到。
#include#include #define less(A, B) (A) < (B) typedef struct ListNode { int data; struct ListNode* next; }List; List* createlist(); void Empty(List* list); List* reverse(List* head); void printlist(List* head); List* merge(List* a, List* b); List* mergelists(List* list1, List* list2); int main() { struct ListNode* head1, * head2; printf("输入链表1："); head1 = createlist(); printf("输入链表2："); head2 = createlist(); //head2 = mergelists(head1, head2); head2 = merge(head1, head2); head2 = reverse(head2); printlist(head2); Empty(head2); return 0; } List* createlist() { int a; struct ListNode* head = NULL; struct ListNode* p, * q; while (scanf_s("%d", &a) == 1) { if (a == 0) break; p = (List*)malloc(sizeof(List)); p->data = a; p->next = NULL; if (head == NULL) { head = p; } else { q = head; while (q->next != NULL) { q = q->next; } q->next = p; } } return head; } void Empty(List* list) { List* p; while (list != NULL) { p = list; list = list->next; free(p); } } List* reverse(List* head) { List* p1, * p2, * p3, * h = NULL; while (head != NULL) { p1 = (List*)malloc(sizeof(List)); p1->data = head->data; p1->next = h; h = p1; p2 = head; head = head->next; free(p2); } return h; } void printlist(List* head) { List* p = head; while (p) { printf("%d ", p->data); p = p->next; } printf("n"); } List* mergelists(List* list1, List* list2) { List* p, * q; if (list1->data < list2->data) { p = list1; list1 = list1->next; } else { p = list2; list2 = list2->next; } q = p; while (1) { if (list1 == NULL) { q->next = list2; return p; } if (list2 == NULL) { q->next = list1; return p; } if (list1->data < list2->data) { q->next = list1; q = q->next; list1 = list1->next; } else { q->next = list2; q = q->next; list2 = list2->next; } } return p; } List* merge(List* a, List* b) { List head; List* c = &head; while ((a != NULL) && (b != NULL)) { if (less(a->data, b->data)){ c->next = a; c = a; a = a->next; } else { c->next = b; c = b; b = b->next; } } c->next = (a == NULL) ? b : a; return head.next; }
4.堆排序
第一个堆排序没有完美的序列，仅仅是一个堆。
第二个堆排序已经是一个完美的序列。
#include#define less(A, B) (A) < (B) #define exch(A, B) {int c = A; A = B; B = c;} void fixUp(int a[], int k); void fixDown(int a[], int k, int n); void HeapSort(int a[], int l, int r); int main() { int a[10] = { 10,9,8,7,6,5,4,3,2,1 }; int b[10] = { 1,4,5,9,2,3,10,8,7,6 }; for (int i = 1; i < 10; i++) { fixUp(b, i); } HeapSort(a, 0, 9); printf("b:"); for (int i = 0; i < 10; i++) { printf("%d ", b[i]); } printf("na:"); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } } void fixUp(int a[], int k) { while (k >= 1 && less(a[k/2], a[k])) { exch(a[k / 2], a[k]); k = k / 2; } } void fixDown(int a[], int k, int n) { int j; while (2 * k <= n) { j = 2 * k; if (j < n && less(*(a + j), *(a + j + 1))) { j++; } if (less(*(a + k), *(a + j)) == 0) { break; } exch(*(a + k), *(a + j)); k = j; } } void HeapSort(int a[], int l, int r) { int k; int N = r - l + 1; int* pq = a + l - 1; for (k = N / 2; k >= 1; k--) { fixDown(pq, k, N); } while (N > 1) { exch(pq[1], pq[N]); fixDown(pq, 1, --N); } }
You never know what you are capable of until you try.
如果不用于尝试，你就永远不知道自己有多强大。
