首页 > 代码库 > 归并排序

归并排序

归并排序重点在治,即合并两个有序数组:

 1 void merge(int A[], int p, int q, int r) 2 { 3     int i = 0, j = 0, k = p; 4     int m = q - p + 1; 5     int n = r - q; 6     int *S = new int[m]; 7     int *T = new int[n]; 8     for (i = 0; i < m; i++) 9         S[i] = A[p + i]; 10     for (j = 0; j < n; j++)11         T[j] = A[q + j + 1]; 12 13     i = j = 0;14     while ((i < m) && (j < n)) 15         if (S[i] < T[j])16             A[k++] = S[i++];17         else18             A[k++] = T[j++];19     while (i < m)20         A[k++] = S[i++];21     while (j < n)22         A[k++] = T[j++];23     24     delete[] S;25     delete[] T;26 }

有了合并以后,merge sort就很简单了。

void merge_sort(int A[], int p, int r){    int q;    if (p < r)    {        q = (p + r) / 2;        merge_sort(A, p, q);        merge_sort(A, q + 1, r);        merge(A, p, q, r);    }}

 

归并排序