//插入排序
int insertion_sort(int a[], int n) { int i, j; for (i=1; i<n; i++) { int key = a[i]; // 將a[i]插入到排好序的a[0, i-1]中 for (j=i-1; j>=0 && a[j] > key; j--) a[j+1] = a[j]; a[j+1] = key; } return 0; }
分治法 (divide-and-conquer)
合並排序 (merge-sort)
//合並排序 (merge-sort)// p、q、r 是下標，滿足 p < q < r// a[p..q]和a[q+1..r]都已經排好序。
int merge(int a[], int p, int q, int r); int merge_sort(int a[], int p, int r) { if (p<r) { int q=(p+r)/2; if (merge_sort(a, p, q) < 0) return -1; if (merge_sort(a, q+1, r) < 0) return -1; if (merge(a, p, q, r) < 0) return -1; } return 0; } int merge(int a[], int p, int q, int r) { int *cpy_a = (int*) malloc((r-p+1)*sizeof(int)); if (NULL==cpy_a) return -1; memcpy(cpy_a, a+p, (r-p+1)*sizeof(int)); { int *a0 = cpy_a; int *a1 = cpy_a + (q-p+1); int *e_a0 = a1; int *e_a1 = cpy_a + (r-p+1); int k; for (k=p; k<=r && a0<e_a0 && a1<e_a1; k++) { if (*a0 < *a1) a[k] = *a0++; else a[k] = *a1++; } while (k<=r && a0<e_a0) a[k++] = *a0++; while (k<=r && a1<e_a1) a[k++] = *a1++; } free(cpy_a); return 0; }
合並排序是应用了分治和递归的思想。
插入排序最坏效率：O(n^2);合并排序最坏效率：O(nlgn);但是n较小时，插入排序更快，所以可以将两者结合使用。
当n<K时，用插入排序；否则用合并排序。
如何确定K值？
int merge_sort(int a[], int p, int r) { if (r-p+1>K) { int q=(p+r)/2; if (merge_sort(a, p, q) < 0) return -1; if (merge_sort(a, q+1, r) < 0) return -1; if (merge(a, p, q, r) < 0) return -1; } else insertion_sort(a+p, r-p+1); return 0; }
转载于:https://www.cnblogs.com/prajna/archive/2013/02/25/2932723.html
相关资源：数据结构—成绩单生成器