C++实现的归并排序算法详解
本篇章节讲解C++实现的归并排序算法。分享给大家供大家参考,具体如下: 归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法。 归并过程 1、比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到temp[k]中,并令i和k分别加上1; 归并排序的算法我们通常用递归实现,先把待排序区间[first,last]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[first,last]。 归并操作的工作原理 第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 算法复杂度 时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。 算法C++代码 //合并两个序列 void mergeArray(int arr[],int first,int mid,int last,int temp[]) { int i = first; int j = mid + 1; int m = mid ; int n = last; int k = 0; while (i <= m && j<=n) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= m) temp[k++] = arr[i++]; while (j <= n) temp[k++] = arr[j++]; for (i = 0; i < k; i++) arr[first + i] = temp[i]; } void mySort(int arr[],int temp[]) { if (first < last) { int mid = (first + last) / 2; mySort(arr,first,mid,temp); mySort(arr,mid+1,last,temp); mergeArray(arr,temp); } } bool mergeSort(int arr[],int len) { int*p = new int[len]; if (NULL == p) return false; mySort(arr,len - 1,p); delete[] p; return true; } 算法测试 #include <iostream> using namespace std; //上述归并排序源码 int main() { int arr[] = { 2,23,32,34,45,6,5,65,7,87,8,798,35,46,756,876,344,3,32 }; int len = sizeof(arr) / sizeof(int); mergeSort(arr,len); for (int i = 0; i < len; i++) cout << arr[i] << " "; cout << endl; system("pause"); } 运行结果: 2 3 5 5 6 6 7 7 8 8 23 32 32 34 34 34 35 45 45 46 65 65 87 87 87 87 344 756 798 876 请按任意键继续. . . 希望本文所述对大家C++程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |