市政工程建设规范免费下载网站,网站建设项目进度表,塔里木油田公司档案馆网站建设研究,wordpress 插件 浮动小人归并排序#xff08;Merge Sort#xff09;是一种基于分治思想的排序算法#xff0c;它将待排序数组分成两个子数组#xff0c;然后对这两个子数组分别进行排序#xff0c;最后将两个已排序的子数组合并成一个有序数组。归并排序是一种稳定的排序算法#xff0c;具体体现…归并排序Merge Sort是一种基于分治思想的排序算法它将待排序数组分成两个子数组然后对这两个子数组分别进行排序最后将两个已排序的子数组合并成一个有序数组。归并排序是一种稳定的排序算法具体体现在其时间复杂度上。
下面是使用 C 实现的归并排序算法
#include algorithm
#include iostream
#include random
#include vectorusing namespace std;void mergeSortImplementation(vectorint array, int left, int right)
{if (left right){return;}const int mid left ((right - left) 1);mergeSortImplementation(array, left, mid);mergeSortImplementation(array, mid 1, right);vectorint temp(right - left 1);int p1 left;int p2 mid 1;for (unsigned int i 0; i temp.size(); i){if (p1 mid 1){temp[i] array[p2];continue;}if (p2 right 1){temp[i] array[p1];continue;}if (array[p1] array[p2]){temp[i] array[p1];}else{temp[i] array[p2];}}for (unsigned int i left; i right 1; i){array[i] temp[i - left];}
}void mergeSort(vectorint array)
{if (array.size() 2){return;}mergeSortImplementation(array, 0, array.size() - 1);
}int main(int argc, char* argv[])
{// Create an array to test sort methodvectorint array {2, 3, 4, 0, 7};cout Before sorting: ;for (int i 0; i array.size(); i){cout array[i] ;}cout endl;mergeSort(array);cout After sorting: ;for (int i 0; i array.size(); i){cout array[i] ;}cout endl;return 0;
}
归并排序的实现过程可以分为两个步骤
分割子问题将待排序数组分成两个子数组分别对两个子数组进行排序。合并解决方案将两个已排序的子数组合并成一个有序数组。
具体来说归并排序的分割子问题的实现可以使用递归算法每次将待排序数组分成两个子数组然后对两个子数组分别进行排序合并解决方案的实现则需要额外的存储空间将两个已排序的子数组合并成一个有序数组。
归并排序的时间复杂度为 O(nlogn)O(nlogn)O(nlogn)其中 n 是待排序数组的长度。归并排序每次将待排序数组分成两个子数组分别对两个子数组进行排序然后再将两个已排序的子数组合并成一个有序数组。这个过程的时间复杂度可以表示为
T(n)2T(n/2)O(n)T(n) 2T(n/2) O(n)T(n)2T(n/2)O(n)
其中 T(n) 表示对长度为 n 的数组进行归并排序的时间复杂度。通过递归展开可以得到
T(n)2T(n/2)O(n)2[2T(n/4)O(n/2)]O(n)4T(n/4)2O(n)4[2T(n/8)O(n/4)]2O(n)8T(n/8)3O(n)...nT(1)lognO(n)T(n) 2T(n/2) O(n)\\ 2[2T(n/4) O(n/2)] O(n)\\ 4T(n/4) 2O(n)\\ 4[2T(n/8) O(n/4)] 2O(n)\\ 8T(n/8) 3O(n)\\ ...\\ nT(1) lognO(n)T(n)2T(n/2)O(n)2[2T(n/4)O(n/2)]O(n)4T(n/4)2O(n)4[2T(n/8)O(n/4)]2O(n)8T(n/8)3O(n)...nT(1)lognO(n)
故而其最终算法时间复杂度为O(nlogn)O(nlogn)O(nlogn)。
