思想:
分治和递归
拆分再合并:
将元素拆分为每一个单位
怎么拆分的,就怎么合并
完整代码
#include <stdio.h> #include <stdlib.h> void PrintSort(int * a, int n) { printf(" "); int i; for (i=0; i<n; i++) { printf("%d ", a[i]); } printf(" "); } void swap(int * a, int * b) { int t = *a; *a = *b; *b = t; } void MergeArr(int * a, int * temp, int l, int mid, int h) { // 标记左右半区第一个未排序的元素 int lPos = l; int rPos = mid + 1; // 临时数组元素的下标 int pos = l; while(lPos <= mid && rPos <= h) { if (a[lPos] < a[rPos]) { temp[pos++] = a[lPos++]; } else { temp[pos++] = a[rPos++]; } } // 合并左半区剩余元素 while(lPos <= mid) { temp[pos++] = a[lPos++]; } // 合并右半区剩余元素 while(rPos <= h) { temp[pos++] = a[rPos++]; } // 把临时数组中合并后的元素 复制回原来的数组 while(l <= h) { a[l] = temp[l]; l++; } } // 划分 void SplitSort(int * a, int * temp, int l, int h) { // 如果只有一个元素,不需继续划分 // 只有一个元素本身就是有序的,直接归并就行 // l<h:表示有两个以上元素 if (l < h) { // 找到中间位置 int mid = (l+h)/2; // 对左半区划分 SplitSort(a, temp, l, mid); // 对右半区划分 SplitSort(a, temp, mid+1, h); // 合并 MergeArr(a, temp, l, mid, h); } } void MergeSort(int * a, int n) { // 分配一个辅助数组 int * temp = (int *) malloc (sizeof(int) * n); if (temp) { SplitSort(a, temp, 0, n-1); free(temp); } } void main() { int n = 8; int a[] = {6, 3, 10, 23, 8, 72, 12, 80}; printf("原本: "); PrintSort(a, n); MergeSort(a, n); printf("排序结果: "); PrintSort(a, n); }