归并排序技术基于分治技术。我们将 while 数据集分成更小的部分,并按排序顺序将它们合并为一个更大的部分。它对最坏情况也非常有效,因为该算法在最坏情况下也具有较低的时间复杂度。
时间复杂度:O(n log n)适用于所有情况
空间复杂度: O(n)
Input − The unsorted list: 14 20 78 98 20 45 Output − 排序后的数组: 14 20 20 45 78 98
输入:数据集数组,左中右索引
输出:合并后的列表
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
输入:数据数组,以及数组的下界和上界
输出:排序后的数组
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<iostream> 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<size; i++) cout << array[i] << " "; cout << endl; } void merge(int *array, int l, int m, int r) { int i, j, k, nl, nr; //左右子数组的大小 nl = m-l+1; nr = r-m; int larr[nl], rarr[nr]; //填充左右子数组 for(i = 0; i<nl; i++) larr[i] = array[l+i]; for(j = 0; j<nr; j++) rarr[j] = array[m+1+j]; i = 0; j = 0; k = l; //marge 临时数组到实际数组 while(i < nl && j<nr) { if(larr[i] <= rarr[j]) { array[k] = larr[i]; i++; }else{ array[k] = rarr[j]; j++; } k++; } while(i<nl) { //左数组中的额外元素 array[k] = larr[i]; i++; k++; } while(j<nr) { //右数组中的额外元素 array[k] = rarr[j]; j++; k++; } } void mergeSort(int *array, int l, int r) { int m; if(l < r) { int m = l+(r-l)/2; // 对第一个和第二个数组进行排序 mergeSort(array, l, m); mergeSort(array, m+1, r); merge(array, l, m, r); } } int main() { int n; cout << "输入元素数量: "; cin >> n; int arr[n]; //创建具有给定元素数量的数组 cout << "输入元素:" << endl; for(int i = 0; i<n; i++) { cin >> 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