实现归并排序的C++程序
归并排序技术基于分治技术。我们将while数据集分成更小的部分,并按排序顺序将它们合并为一个更大的部分。它对最坏情况也非常有效,因为该算法在最坏情况下也具有较低的时间复杂度。
归并排序技术的复杂性
时间复杂度:O(nlogn)适用于所有情况
空间复杂度:O(n)
Input − The unsorted list: 14 20 78 98 20 45 Output − 排序后的数组: 14 20 20 45 78 98
算法
merge(array,left,middle,right)
输入:数据集数组,左中右索引
输出:合并后的列表
Begin nLeft := m - left+1 nRight := right – m define arrays leftArr and rightArr of size nLeft and nRight respectively for i := 0 to nLeft do leftArr[i] := array[left +1] done for j := 0 to nRight do rightArr[j] := array[middle + j +1] done i := 0, j := 0, k := left while i < nLeft AND j < nRight do if leftArr[i] <= rightArr[j] then array[k] = leftArr[i] i := i+1 else array[k] = rightArr[j] j := j+1 k := k+1 done while i < nLeft do array[k] := leftArr[i] i := i+1 k := k+1 done while j < nRight do array[k] := rightArr[j] j := j+1 k := k+1 done End
mergeSort(array,left,right)
输入:数据数组,以及数组的下界和上界
输出:排序后的数组
Begin if lower < right then mid := left + (right - left) /2 mergeSort(array, left, mid) mergeSort (array, mid+1, right) merge(array, left, mid, right) End
示例代码
#include输出结果using namespace std; void swapping(int &a, int &b) { //交换a和b的内容 int temp; temp = a; a = b; b = temp; } void display(int *array, int size) { for(int i = 0; i > n; int arr[n]; //创建具有给定元素数量的数组 cout << "输入元素:" << endl; for(int i = 0; i > arr[i]; } cout << "排序前的数组: "; display(arr, n); mergeSort(arr, 0, n-1); //(n-1)用于最后一个索引 cout << "排序后的数组: "; display(arr, n); }
输入元素数量: 6 输入元素: 14 20 78 98 20 45 排序前的数组: 14 20 78 98 20 45 排序后的数组: 14 20 20 45 78 98