冒泡排序、插入排序、选择排序、归并排序、快速排序算法（C++实现）

文章目录

一、冒泡排序
- 上浮法冒泡排序（从小到大排序）
- 下浮法冒泡排序（从大到小排序）
二、选择排序
三、插入排序
四、归并排序
五、快速排序
参考

一、冒泡排序

冒泡排序应该算是最经典最简单的排序算法，我一开始学习排序算法就是从冒泡排序开始入门的。
冒泡排序算法的基本思路：（循环遍历，相邻元素比较）

冒泡排序通过多轮遍历数组，每一轮比较相邻的元素，如果相邻元素的顺序不符合要求（升序或降序），则交换它们的位置。
每一轮重复以上的比较操作，就会将当前未排序的最大（升序）或者最小（降序）元素排序到数组的末尾位置。
重复以上步骤，直到一轮遍历中没有发生任何交换，表示数组已经排序完成。
循环遍历的次数最多n-1次，最少为1次。
时间复杂度：最好为O(n) 最差为O(n^2)
空间复杂度：O(1)

上浮法冒泡排序（从小到大排序）

#include <iostream>
#include <vector>using namespace std;void bubbleSortUp(vector<int> &nums)
{for (int i = 0; i < nums.size() - 1; i++){bool isSwap = false;for (int j = 0; j < nums.size() - i - 1; j++){if (nums[j] > nums[j + 1]){swap(nums[j], nums[j + 1]);isSwap = true;}}if (isSwap == false){cout << "排序已完成" << endl;break;}}
}int main(int argc, char const *argv[])
{vector<int> nums = {5, 6, 675, 4, 43, 63, 1, 2, 3, 8, 5, 6, 675, 4, 43, 63, 1, 2, 3};bubbleSortUp(nums);for (auto num : nums){cout << num << " ";}cout << endl;return 0;
}

下浮法冒泡排序（从大到小排序）

如果会了上浮法冒泡排序，那下浮法的就很简单，只需要将上浮法中的if (nums[j] > nums[j + 1])改成if (nums[j] < nums[j + 1])即可。
时间复杂度：最好为O(n) 最差为O(n^2)
空间复杂度：O(1)

#include <iostream>
#include <vector>using namespace std;void bubbleSortUp(vector<int> &nums)
{for (int i = 0; i < nums.size() - 1; i++){bool isSwap = false;for (int j = 0; j < nums.size() - i - 1; j++){// 下浮法只需要修改这里即可if (nums[j] < nums[j + 1]){swap(nums[j], nums[j + 1]);isSwap = true;}}if (isSwap == false){cout << "排序已完成" << endl;break;}}
}int main(int argc, char const *argv[])
{vector<int> nums = {5, 6, 675, 4, 43, 63, 1, 2, 3, 8, 5, 6, 675, 4, 43, 63, 1, 2, 3};bubbleSortUp(nums);for (auto num : nums){cout << num << " ";}cout << endl;return 0;
}

二、选择排序

选择排序算法的基本思路：（循环遍历，找到最小元素并交换位置）

遍历整个列表的n个元素，找到最小的元素，与第一个元素交换位置。
遍历列表剩余的n-1个元素，找到最小的元素，与第二个元素交换位置。
以此类推，重复以上步骤，直到需要遍历的列表元素个数小于等于1，则表示排序完成。
时间复杂度：O(n^2)
空间复杂度：O(1)

#include <iostream>
#include <vector>using namespace std;void selectSort(vector<int> &nums)
{for (int i = 0; i < nums.size() - 1; i++){int minIndex = i;for (int j = i + 1; j < nums.size(); j++){if (nums[j] < nums[minIndex]){minIndex = j;}}swap(nums[i], nums[minIndex]);}
}int main(int argc, char const *argv[])
{vector<int> nums = {-1, -181, 0, 0, 5, 6, 675, 4, 43, 63, 1, 2, 3, 8, 5, 6, 675, 4, 43, 63, 1, 2, 3, -999};selectSort(nums);for (auto num : nums){cout << num << " ";}cout << endl;return 0;
}

三、插入排序

插入排序算法的基本思路：（逐个取出元素，与前面有序部分依次比较并插入正确位置）

从第二个元素开始，将这个元素作为待插入元素与前面有序的元素进行比较；
如果待插入的元素比前面有序的元素小，则将有序的元素往后移动，相当于腾出空间；
继续比较和移动，直到找到合适的位置（大于等于前一个数且小于等于后一个数），将待插入的元素放入该位置；
重复上述步骤，直到整个数组有序。
时间复杂度：正序时最好为O(n) 逆序时最差为O(n^2)
空间复杂度：O(1)

#include <iostream>
#include <vector>using namespace std;void insertSort(vector<int> &nums)
{for (int i = 1; i < nums.size(); i++){int j = i - 1;int temp = nums[i];while (j >= 0 && nums[j] > temp){nums[j + 1] = nums[j];j--;}nums[j + 1] = temp;}
}int main(int argc, char const *argv[])
{vector<int> nums = {-43, 3, 4, 124, 2345, 456, 5, 6, 7, 6, 5, 0, 12, 33, 3, 22, 2, 77, 2, 34, 55, 5, 56, 1, 100, 88, 21, 99};insertSort(nums);for (auto num : nums){cout << num << " ";}cout << endl;return 0;
}

一开始在写插入排序时，我用到了另一种方法：这种方法虽然也能实现排序，但是这种方法似乎不太符合插入排序的基本思路，而且用到了swap，在一定程度上会增加时间复杂度。

void insertSort(vector<int> &nums) 
{ for (int i = 1; i < nums.size(); i++) { for (int j = i; j > 0; j--) { if (nums[j] < nums[j - 1]) { swap(nums[j], nums[j - 1]); } } } 
}

四、归并排序

归并排序有两种实现方法，一种是递归，一种是迭代。
归并排序的基本思路：（分治算法）

分解，将待排序的数组从中间分成两半，分别递归地对这两半进行排序，不断分解，直到数组的长度为 1，此时每个子数组都被视为有序。
合并，将子数组两两合并，合并的过程中排序，按大小顺序将元素从两个子数组中取出，形成一个新的有序数组。
归并排序算法的特点：
是稳定排序算法
速度仅次于快速排序
一般用于对总体无序，但是各子项相对有序的数列。
时间复杂度：O(nlogn)
空间复杂度：O(n)

#include <iostream>
#include <vector>
using namespace std;/*** 归并函数（二路合并）* start:第一段的首元素索引* mid:第二段的首元素索引* end:第二段的末尾元素索引*/
void merge(vector<int> &nums, const int start, const int mid, const int end)
{vector<int> merArray;int p1 = start;int p2 = mid;while (p1 < mid && p2 <= end){if (nums[p1] <= nums[p2]){merArray.push_back(nums[p1++]);}else{merArray.push_back(nums[p2++]);}}// 将剩余的元素加入到merArraywhile (p1 < mid){merArray.push_back(nums[p1++]);}while (p2 <= end){merArray.push_back(nums[p2++]);}int pos = start;for (auto it : merArray){nums[pos++] = it;}
}/*** 用迭代的方法实现归并排序* 时间复杂度：O(nlogn)* 空间复杂度：O(n)，因为排序过程中多次拆分的子数组需要放在内存*/
void mergeSortIteration(vector<int> &nums)
{for (int i = 0; i < nums.size(); i++){int start = 0;int len = 1 << i;if (len > nums.size())break;while (start < nums.size()){// 注意区分这里的mid和传入merge函数的mid+1// mid是第一段的末尾元素，mid+1是第二段的首元素int mid = start + len - 1;if (mid >= nums.size())break;int end = min(start + 2 * len - 1, (int)nums.size() - 1);merge(nums, start, mid + 1, end);start += len * 2;}}
}/*** 用递归的方法实现归并排序* 时间复杂度：O(nlogn)* 空间复杂度：O(n)，因为排序过程中多次拆分的子数组需要放在内存* 传参都是统一传递有效索引*/
void mergeSortRecursion(vector<int> &nums, int start, int end)
{if (start < end){int mid = (start + end) / 2;mergeSortRecursion(nums, start, mid);mergeSortRecursion(nums, mid + 1, end);merge(nums, start, mid + 1, end);}
}int main(int argc, char const *argv[])
{vector<int> nums = {-43, -22, 8, 44, 11, 223, 4, 0, 1, 2, 2, 3, 3, 33, 3};mergeSortIteration(nums); // 迭代法// mergeSortRecursion(nums, 0, nums.size() - 1); // 递归法for (int num : nums){cout << num << " ";}cout << endl;return 0;
}

五、快速排序

快速排序采用的也是分治的策略，它是一种基于二叉树结构的交换排序算法。快速排序是一种不稳定的排序方法，但是他的效率非常高。
快速排序算法的基本思路：

先从数列中取出一个数作为基准数，然后将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
对左右区间重复步骤一的操作，直到各区间只有一个数。
时间复杂度：最差为O(n^2)，平均为O(NlogN)
空间复杂度：受递归深度影响，最好为O(logn)，最差为O(n)

#include <iostream>
#include <vector>using namespace std;/*** 快速排序算法（左右指针法/hoare法）* 时间复杂度：最差为O(n^2)，平均为O(NlogN)* 空间复杂度：受递归深度影响，最好为O(logn)，最差为O(n)*/
void quickSort(vector<int> &nums, int begin, int end)
{if (begin >= end)return;// 保存左右节点int left = begin;int right = end;// 选取第begin节点为keyint key = begin;while (begin < end){// 右边选小，遇到大于nums[key]的数就跳过while (begin < end && nums[end] >= nums[key]){end--;}// 左边选大，遇到小于nums[key]的数就跳过while (begin < end && nums[begin] <= nums[key]){begin++;}swap(nums[begin], nums[end]);}// 交换相遇点的值和nums[key]值swap(nums[key], nums[begin]);key = begin;// 递归quickSort(nums, left, key - 1);quickSort(nums, key + 1, right);
}int main(int argc, char const *argv[])
{vector<int> nums = {-43, -22, 8, 44, 11, 223, 4, 0, 1, 2, 2, 3, 3, 33, 3};quickSort(nums, 0, nums.size() - 1);for (auto num : nums){cout << num << " ";}cout << endl;return 0;
}