首页 > 代码库 > 常用排序算法之——归并排序

常用排序算法之——归并排序

2024-07-17 01:14:14   224人阅读

归并排序的原理：

如果数组的元素个数大于1，则：

　　将数组平均分为两部分；

　　左边的数组归并排序；递归

　　右边的数组归并排序；递归

　　将两个各自有序的数组合并，需要一个额外的辅助数组，暂时保存合并结果；返回

否则，数组元素个数为1时，已经有序；直接返回。

 

稳定排序。时间复杂度在最坏、最好、平均情况下都为O(N lgN)，空间复杂度为O(N)。

 

代码：

 1 #include <iostream> 2 using namespace std; 3  4 template<typename T> 5 void mergeSortedArray(T src[], int first, int mid, int last, T tmp[]) 6 { 7     int i = first, j = mid + 1; 8     int idx = 0; 9 10     while(i <= mid && j <= last)11     {12         tmp[idx++] = src[i] < src[j] ? src[i++] : src[j++];13     }14 15     while(i <= mid)16     {17         tmp[idx++] = src[i++];18     }19     while(j <= last)20     {21         tmp[idx++] = src[j++];22     }23 24     for(i = 0; i < idx; ++i)25     {26         src[first + i] = tmp[i];27     }28 }29 30 template<typename T>31 void mergeSort(T src[], int first, int last, T tmp[])32 {33     if(first >= last)34         return;35 36     int mid = first + ((last - first) >> 1);  //找到中间元素下标，将数组分为两部分37 38     mergeSort(src, first,   mid,  tmp);       //排序左边子数组39     mergeSort(src, mid + 1, last, tmp);40 41     mergeSortedArray(src, first, mid, last, tmp);  //合并，tmp为辅助数组，用于记录临时合并的结果42 }43 44 int main()45 {46     const int n = 5;47 48     int    ia[n] = {1, 3, 6, 2, 4};49     int    itmp[n];50     mergeSort(ia, 0, n - 1, itmp);  //sort51     for(int i = 0; i < n; ++i)52         cout << ia[i] << ‘ ‘;53     cout << endl;54 55     double da[n] = {1.2, 3.4, 6.7, 2.3, 4.5};56     double dtmp[n];57     mergeSort(da, 0, n - 1, dtmp);  //sort58     for(int i = 0; i < n; ++i)59         cout << da[i] << ‘ ‘;60     cout << endl;
61     return 0;
62 }

 


联系
我们