当前位置：首页 > news >正文

归并排序（C/C++）

news 来源：原创 2024/4/24 16:11:38

本文目录

1. 算法思想
2. 简单概述
3. 算法步骤
4. 代码实现（C++）
- 4.1 vector 类型的递归
- 4.2 vector 类型的迭代
5. 补充知识
6. 其它排序算法

1. 算法思想

将一个大的无序数组有序化，可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组，由于两个小的数组都是有序的，所以合并时很快。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后把两个数组大小为1的合并成一个数组大小为2的，再把两个数组大小为2的合并成大小为4的…直到全部的小数组合并起来。

归并排序是建立在归并操作上的一种有效的排序算法，该算法是 分治法 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

2. 简单概述

平均时间复杂度： O(n * log n)
最好情况： O(n * log n)
最坏情况：O(n * log n)
排序方式：非原地排序
稳定性：稳定
空间复杂度： O(n)

3. 算法步骤

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

4. 代码实现（C++）

4.1 vector 类型的递归

#include<iostream>
#include<vector>
using namespace std;void printVector(vector<int>& nums)
{for (auto num : nums){cout << num << " ";}cout << endl;
}void mergeSortCore(vector<int>& data, vector<int>& dataTemp, int low, int high) 
{if (low >= high){return;}int len = high - low, mid = low + len / 2;int start1 = low, end1 = mid, start2 = mid + 1, end2 = high;mergeSortCore(data, dataTemp, start1, end1);mergeSortCore(data, dataTemp, start2, end2);int index = low;while (start1 <= end1 && start2 <= end2) {dataTemp[index++] = data[start1] < data[start2] ? data[start1++] : data[start2++];}while (start1 <= end1) {dataTemp[index++] = data[start1++];}while (start2 <= end2) {dataTemp[index++] = data[start2++];}for (index = low; index <= high; ++index) {data[index] = dataTemp[index];}
}void mergeSort(vector<int>& data) 
{int len = data.size();vector<int> dataTemp(len, 0);mergeSortCore(data, dataTemp, 0, len - 1);
}int main()
{vector<int> nums = { 8,7,1,4,2,3,6,9,5 };mergeSort(nums);printVector(nums);system("pause"); //按任意键继续return 0;
}

4.2 vector 类型的迭代

#include<iostream>
#include<vector>
using namespace std;void printVector(vector<int>& nums)
{for (auto num : nums){cout << num << " ";}cout << endl;
}void mergeSort(vector<int>& data) 
{int len = data.size();vector<int> dataTemp(len, 0);for (int seg = 1; seg < len; seg += seg) {for (int start = 0; start < len; start += seg + seg) {int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);int index = low, start1 = low, end1 = mid, start2 = mid, end2 = high;while (start1 < end1 && start2 < end2) {dataTemp[index++] = data[start1] < data[start2] ? data[start1++] : data[start2++];}while (start1 < end1) {dataTemp[index++] = data[start1++];}while (start2 < end2) {dataTemp[index++] = data[start2++];}}swap(data, dataTemp);}
}int main()
{vector<int> nums = { 8,7,1,4,2,3,6,-3,5 };mergeSort(nums);printVector(nums);system("pause"); //按任意键继续return 0;
}

5. 补充知识

稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序；
非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序；
非原地排序：需要利用额外的数组来辅助排序。
时间复杂度：一个算法执行所消耗的时间（次数，因为同一程序在不同系统的执行时间可能不同）；
空间复杂度：运行完一个算法所需的内存大小。
十大排序中的稳定排序：
- 冒泡排序（bubble sort） — O(n * n)
- 插入排序（insertion sort）— O(n * n)
- 归并排序（merge sort）— O(n * log n)
十大排序中的非稳定排序：（面试考察中一般问快排，选择，希尔，堆这几种非稳定排序）
- 选择排序（selection sort）— O(n * n)
- 希尔排序（shell sort）— O(n * log n)
- 堆排序（heapsort）— O(n * log n)
- 快速排序（quicksort）— O(n * log n)

6. 其它排序算法

冒泡排序
选择排序
快速排序
插入排序
希尔排序
归并排序
堆排序
计数排序
桶排序
基数排序