写在前面
总结一下经典的排序算法, 这次是基本排序算法, 冒泡插入和选择, 加上自己的理解与C++实现.
辅助代码
这里给出了输出数组的函数, 通过STL的vector来完成.
#include <iostream>
#include <vector>
using namespace std;
void printArray(const vector<int>& arr) {
for (size_t i = 0; i < arr.size(); ++i) cout << arr[i] << " ";
cout << endl;
}
冒泡
最为经典的排序算法, 虽然时间复杂度也相当高, 应该是很多同学入门编程语言学到的第一个排序算法.
思路很简单, 就是通过每次比较相邻两数的大小, 保证较大的那个值在后面, 如此进行n轮(数组长度), 即可得到排序好的数组.
void BubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = n; i > 0; --i) {
// 每一轮都标记是否进行过交换
bool exchanged = false;
for (int j = 1; j < i; ++j)
if (arr[j - 1] > arr[j]) {
swap(arr[j - 1], arr[j]);
exchanged = true;
}
if (!exchanged) break;
}
}
另一种写法:
void BubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
bool exchanged = false;
for (int j = 0; j < n - i; ++j)
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
exchanged = true;
}
if (!exchanged) break;
}
}
插入
按照算法导论上面的比喻, 插入排序就是从桌上扣过来的未排序的扑克牌中依次向手上的已排好序的扑克牌中插入.
void InsertionSort(vector<int> &arr) {
int n = arr.size();
// 左边为已排序区,右边是待排序区
for (int j = 1; j < n; ++j) {
int i = j - 1, tmp = arr[j]; // tmp:待插入元素
// 往后挪元素,腾出来位置留给tmp
while (i >= 0 && arr[i] > tmp) {
arr[i + 1] = arr[i];
--i;
}
// 上面的这个while循环可以用for一行完成:
// for (; i >= 0 && arr[i] > tmp; --i) arr[i + 1] = arr[i];
// 最后插入tmp
arr[i + 1] = tmp;
}
}
使用 swap 更方便: (要多花一些时间)
void insertion_sort(vector<int>& arr) {
for (int i{1}; i < arr.size(); ++i)
while (i >= 0 && arr[i - 1] > arr[i])
swap(arr[i - 1], arr[i--]);
}
但是这里我就有一个困惑了, 为什么不能用从前向后的遍历方式呢?
后来我写了个前向遍历, 才发现了问题所在.
void InsertionSort(vector<int> &arr) {
int n = arr.size();
// 遍历待插入元素
for (int i = 1; i < n; ++i) {
int tmp = arr[i], j{};
// 从前往后遍历, 寻找插入位置(遍历已排好序的元素)
while (j < i && arr[j] <= tmp) ++j;
if (j == i) continue;
int idx = j;
// 下面两种for循环, 结果是一样的
// for (; i > idx; --i) arr[i] = arr[i - 1];
for (int k{}; k <= i - idx; ++k) arr[i - k] = arr[i - 1 - k];
arr[idx] = tmp;
}
}
前向遍历需要先找到待插入的位置, 然后往后移动腾出来待插入元素要放置的位置, 相当于在遍历未排序部分的内部套了两个循环, 而不是像后往前遍历那样直接在寻找到要插入的位置之后就直接进行挪元素了, 省去了一重循环, 并且写起来方便很多.
选择
通过每次遍历数组的未排序部分, 找到最大值(或者最小值)放在已排序数组的末尾, 即可.
void SelectSort(vector<int> &arr) {
int n = arr.size(), i{};
while (i < n) {
int min1 = i;
for (int j = i + 1; j < n; ++j)
if (arr[min1] > arr[j]) min1 = j;
if (min1 != i) swap(arr[min1], arr[i]);
i++;
}
}
或者for写法:
void SelectSort(vector<int> &arr) {
int n = arr.size();
for (int i{}; i < n; ++i) {
int min1 = i;
for (int j = i + 1; j < n; ++j)
if (arr[min1] > arr[j]) min1 = j;
if (min1 != i) swap(arr[min1], arr[i]);
}
}
总结
这三种都是比较经典的原地排序算法, 但是时间复杂度都比较高, 其中蕴含的思路可以为之后的快排等算法打基础.