排序算法之归并排序
一、基本思想归并排序,和快排一样同样采用了分治的思想,将两个(或以上)有序表合并成一个新的有序表。
归并排序步骤如下:
把N个记录看成 N个长度为 1 的有序子表;
进行两两归并使记录关键字有序,得到 N/2 个长度为 2 的有序子表;
重复第2步直到所有记录归并成一个长度为N的有序表为止。
二、算法实现
下面是归并排序算法的递归实现:
#include <iostream> #include <malloc.h> using namespace std; // 合并两个有序部分 void mergeArray(int a[], int first, int mid, int last, int temp[]) { if (first >= last) { return; } int i = first, j = mid + 1; int k = first; while (i <= mid && j <= last) { if (a[i] > a[j]) { temp[k++] = a[j++]; } else { temp[k++] = a[i++]; } } while (i <= mid) { temp[k++] = a[i++]; } while (j <= last) { temp[k++] = a[j++]; } // 回写到原来数组中 for (k = first; k <= last; k++) { a[k] = temp[k]; } } // 递归调用归并 void mSort(int* a, int first, int last, int *temp) { if (first < last) { int mid = (first + last) >> 1; mSort(a, first, mid, temp); mSort(a, mid + 1, last, temp); mergeArray(a, first, mid, last, temp); } } // 归并排序算法 void mergeSort(int *a, int len) { int* temp = (int*) malloc(len * sizeof(int)); mSort(a, 0, len - 1, temp); free(temp); } int main() { int arr[] = { 213, 43, 43, 123, 45, 52, 67, 234, 452, 5, 67 }; int len = 11; cout << "Before sorting:" << endl; for (int i = 0; i < len; i++) { cout << arr[i] << "\t"; } mergeSort(arr, len); cout << endl << "After merge sorting:" << endl; for (int i = 0; i < len; i++) { cout << arr[i] << "\t"; } cout << endl; return 0; }
三、算法分析
归并排序最好、平均、最坏时间复杂度都是:O(n*log2(n)),
归并排序需要额外的存储空间,其空间复杂度为:O(n).
归并排序和快排、堆排序一样是一种高效的排序算法,在数据规模较大而且存储空间要求足够的情况下是非常好的选择。
四、算法改进
归并排序改进和优化的方向如下:
当问题分割很小到某个规模的时候停止递归,采用简单插入排序;
消除递归调用
消除反复回写
...
下面是改进的一个消除递归算法:
#include <iostream> #include <malloc.h> using namespace std; // 合并数组中连续的两个有序部分 void mergeArray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int k = first; while (i <= mid && j <= last) { if (a[i] > a[j]) { temp[k++] = a[j++]; } else { temp[k++] = a[i++]; } } while (i <= mid) { temp[k++] = a[i++]; } while (j <= last) { temp[k++] = a[j++]; } } // 根据设定的步长来顺序归并 void mergeStep(int a[], int step, int len, int temp[]) { int first, mid, last; first = 0; last = first + step + step - 1; mid = first + step - 1; while (last < len) { mergeArray(a, first, mid, last, temp); first = last + 1; last = first + step + step - 1; mid = first + step - 1; } // 末端注意数组边界 if (mid > len) { for (int i = first; i < len; i++) { temp[i] = a[i]; } } else { mergeArray(a, first, mid, len - 1, temp); } } void mergeSort(int a[], int len) { cout << "Before sorting:" << endl; for (int i = 0; i < len; i++) { cout << a[i] << "\t"; } cout << endl; // int flag = 0; // 写入方向标识 int* temp = (int*) malloc(len * sizeof(int)); // 消除递归 for (int step = 1; step < len; step = step << 1) { // 避免返易做图写 if (flag++ % 2) { // flag初始为奇数,向a写入排序结果,执行后flag为偶数 mergeStep(temp, step, len, a); } else { // flag初始为偶数,向temp写入即可,执行后flag为奇数 mergeStep(a, step, len, temp); } } // 若flag为奇数,则表明排序结果存在于temp中,需要回写 if (flag % 2) { for (int i = 0; i < len; i++) { a[i] = temp[i]; } } // free(temp); // cout << "After merge sorting:" << endl; for (int i = 0; i < len; i++) { cout << a[i] << "\t"; } cout << endl; } int main() { int arr[17] = { 213, 67, 89, 10, 23, 9, 23, 45, 12, 456, 234, 67, 12, 0 }; int len = 17; mergeSort(arr, len); return 0; }
补充:软件开发 , C++ ,