文章目录
一、冒泡排序
冒泡排序应该算是最经典最简单的排序算法，我一开始学习排序算法就是从冒泡排序开始入门的。
冒泡排序算法的基本思路：（循环遍历，相邻元素比较）
- 冒泡排序通过多轮遍历数组，每一轮比较相邻的元素，如果相邻元素的顺序不符合要求（升序或降序），则交换它们的位置。
- 每一轮重复以上的比较操作，就会将当前未排序的最大（升序）或者最小（降序）元素排序到数组的末尾位置。
- 重复以上步骤，直到一轮遍历中没有发生任何交换，表示数组已经排序完成。
- 循环遍历的次数最多
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++]);
}
}
// 将剩余的元素加入到merArray
while (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节点为key
int 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;
}