首页 > 代码库 > 归并排序
归并排序
介绍
归并排序法是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。
过程
第一步：申请空间，使之大小为两个已经排序序列之和，该空间用来存放合并后的序列；
第二步：设定两个指针，最初位置为两个已经排序序列的起始位置；
第三步：比较两个指针所指向的元素，将相对较小的元素放入到合并空间，并移动指针到下一个位置。
重复步骤3直到某一指针超出序列，将另一序列剩下的所有元素直接复制到合并序列尾。
代码
#include<iostream>using namespace std;void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex){ int i = startIndex, j = midIndex + 1, k = startIndex; while (i != midIndex + 1 && j != endIndex + 1){ if (sourceArr[i] > sourceArr[j]){ tempArr[k++] = sourceArr[j++]; } else{ tempArr[k++] = sourceArr[i++]; } } while (j != endIndex + 1){ tempArr[k++] = sourceArr[j++]; } while (i != midIndex + 1){ tempArr[k++] = sourceArr[i++]; } for (i = startIndex; i <= endIndex; i++){ sourceArr[i] = tempArr[i]; }}//内部使用递归void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){ int midIndex; if (startIndex < endIndex){ midIndex = (startIndex + endIndex) / 2; MergeSort(sourceArr, tempArr, startIndex, midIndex); MergeSort(sourceArr, tempArr, midIndex + 1, endIndex); Merge(sourceArr, tempArr, startIndex, midIndex, endIndex); }}int main(){ int a[8] = { 50, 10, 20, 30, 70, 40, 80, 60 }; int i, b[8]; MergeSort(a, b, 0, 7); for (i = 0; i < 8; i++){ cout << a[i] << " "; } return 0;}
时间复杂度
0(n*log(n))
空间复杂度
0(n)
归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。