归并排序是分治思想的典型应用。它的基本步骤有3步：
1. 划分。将要排序的数组分为两部分。
2. 递归求解。分别递归使用归并排序将两部分排序。
3. 合并。将两个有序的序列合并为一个有序的序列。
将序列分为两部分用时O（1），而对子序列进行递归排序耗时2 * T(n/2)，对排好的两个序列合并用时O（n）。
由于每次减为n/2 。算法的总体复杂度为O（nlogn）
主代码mergesort
代码的主体部分如下：
思想是，排序前半部分，排序后半部分，将两部分归并为一个部分。
|
1 2 3 4 5 6 7 8 9 10 11 |
void merge_sort(int *a, int low, int high) { int mid; if (high - low < 2) return; //递归基 该序列只有一个元素 是有序的 mid = (low + high) / 2; merge_sort(a, low, mid); //左半部分排序 merge_sort(a, mid, high); //右半部分排序 merge(a, low, mid, high); //合并两个排好序的序列 } |
归并两个有序序列
只需每次比较两个序列的第一个，取出较小者，再比较两个序列的第一个……
左半部分[low, mid) 右半部份[mid, high)
代码如下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <malloc.h> #define N 1000 void merge(int *_elem, int lo, int mid, int hi); void mergesort(int *_elem, int lo, int hi); int main(void) { int i; int a[N]; srand((int)time(NULL)); for (i = 0; i < N; ++i) { a[i] = rand() % 10000; } mergesort(a, 0, N); for (i = 0; i < N; ++i) printf("%d ", a[i]); printf("\n"); return 0; } void merge(int *_elem, int lo, int mid, int hi) { int i, j, k; int * L = (int *)malloc(sizeof(int)*(mid-lo)); int lenL = mid - lo; //左半部分备份出来 for (i = lo; i < mid; ++i) L[i-lo] = _elem[i]; i = 0; //左半部分指针 j = mid; //右半部分指针 k = lo; //记录结果数组下标 while (i < lenL && j < hi) { if (L[i] <= _elem[j]) _elem[k++] = L[i++]; else _elem[k++] = _elem[j++]; } while (i < lenL) _elem[k++] = L[i++]; } void mergesort(int *_elem, int lo, int hi) { if (hi - lo < 2) return; int mid = lo + (hi - lo) / 2; mergesort(_elem, lo, mid); mergesort(_elem, mid, hi); merge(_elem, lo, mid, hi); } |
支付宝打赏 
微信打赏