)
排序算法
文中使用的图片来自慕课网课程算法与数据结构
为什么要学习 的排序算法
- 这是一种简单的算法, 但是不因为其简单而不重要, 相反, 其是一种基础的算法, 是很多复杂问题的基础.
- 编码简单, 易于实现, 是一些简单场景的首选.
- 在一些特殊的情况下, 简单的排序算法会更加有效.
- 简单的排序算法基础能够衍生出更复杂的排序算法.
选择排序
选择排序的算法非常简单:
- 假设我们有一个数组, 大小为
.
- 需要进行
次循环, 归位第
- 找到
中的最小值
- 交换 i 和最小值位置的值.
- 找到
void selectionSort(int arr[], int n) {
for (int i = 0; i < n; ++i) {
// 第 i 个元素归位
int minIndex = i;
// 找到 [i, n) 元素中的最小值的位置
for (int j = i; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换 i 和 minIndex 的值
// swap 是 c++11 std 命名空间中的标准函数
// 在之前的标准中, 需要 #include <algorithm>
swap(arr[i], arr[minIndex]);
}
}
插入排序
插入排序类似于我们打扑克的时候, 抓牌的过程, 每次抓一张牌, 插入到手中已有牌的正确位置.
- 假设我们有一个数组, 大小为
- 需要进行
- 归为第
- 与前一个元素进行比较, 如果小于前一个元素, 交换位置.
- 直到大于等于前一个元素, 结束第
- 归为第
代码实现:
template<typename T>
void insertionSort(T arr[], int n) {
for (int i = 1; i < n; ++i) {
// 寻找元素 arr[i] 的合适插入位置
for (int j = i; j > 0 && arr[j] < arr[j - 1]; --j) {
swap(arr[j], arr[j - 1]);
}
}
}
我们和之前的选择排序进行比较, 结果如下:
int main() {
int n = 10000;
int *arr = SortTestHelper::generateRandomArray(n, 0, n);
int *arr2 = SortTestHelper::copyArray(arr, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
delete[] arr;
delete[] arr2;
return 0;
}
插入排序的改进
相较于选择排序, 插入排序在循环过程中, 有提前结束的机制, 理论上效率应当比选择排序要高, 但是在上面的结果中, 为什么插入排序要比选择排序差呢? 主要原因在于交换, 我们上面的代码实现中, 每一次循环, 都要进行一次交换, 因此我们的一个优化思路是, 能不能减少交换的次数.
我们优化的思路是, 将交换操作使用数组的移动操作来代替, 能够大大减少数组中赋值操作的消耗 (一次交换是三次赋值), 具体来说, 就是待排序的元素与前一个元素比较, 如果小于前一个元素, 则将该元素复制一份, 将前一个元素后移一位; 然后再将待排序元素与前一个元素进行比较, 直到不小于前一个元素为止.
对于几乎为顺序的数组来说, 插入排序的效率会非常高, 使用如下代码进行测试:
int main() {
int n = 10000;
int *arr = SortTestHelper::generateNearlyOrderedArray(n, 100);
int *arr2 = SortTestHelper::copyArray(arr, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);
delete[] arr;
delete[] arr2;
return 0;
}
插入排序在极端情况下, 即对于完全有序的数组, 其是一个时间复杂度为 的算法. 因此插入排序算法也不是一无是处.
冒泡排序 (Bubble Sort)
冒泡排序过程中, 每一次循环中, 如果相邻的两个元素之间顺序错误, 则交换这两个元素, 我们可以想象, 最大的那个元素会像冒泡一样一直到最后一个位置, 这就是冒泡排序名字的由来, 那么下一次循环就可以少进行一次比较, 因为最后一个元素已经归位. 那么基于此我们有如下实现:
template<typename T>
void bubbleSort(T *arr, int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
冒泡排序的优化
对于上述代码, 我们循环次数是固定的, 然而, 冒泡排序可以使用提前结束的条件判定, 如果在一次循环过程中, 没有发生交换, 那么就可以结束算法.
template<typename T>
void bubbleSort2(T *arr, int n) {
bool isSwaped;
do {
isSwaped = false;
for (int j = 0; j < n - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
isSwaped = true;
}
}
n--;
} while (isSwaped);
}
进一步优化
其实, 我们还可以对冒泡排序进行进一步优化, 之前的算法中, 我们每一轮迭代只归位最后一个元素, 其实, 在最后一个发生交换的元素之后的元素, 都可以认为已经完成了归位, 因此, 我们的算法还可以进一步优化.
template<typename T>
void bubbleSort3(T *arr, int n) {
int swapPosition;
do {
// 为零表示没有进行交换
swapPosition = 0;
for (int j = 0; j < n - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapPosition = j + 1;
}
}
n = swapPosition;
} while (swapPosition > 0);
}
希尔排序 (Shell Sort)
希尔排序利用的是插入排序对近似有序数组的排序效率非常高, 希尔排序采用的是分而治之, 逐渐合并的思想.
第一步, 分. 将原数组以相等的间隔进行划分.
第二步, 对每一个分数组进行插入排序.
第三步, 逐渐缩小划分的间隔, 直到间隔为 1, 那么即完成了整个数组的排序.
通过对每一个子序列先进性排序, 使得数组整体上呈现近似顺序的状态, 因此使用插入排序会非常高效.
为了高效, 具体操作过程中, 第一轮排序, 每一个子数组中包含 3 个元素, 然后以三倍的形式扩大, 为了使最终间距能够到达 1, 我们可以从 1 开始生成一个 increment sequence, 然后对每个子序列进行插入排序.
template <typename T>
void shellSort(T arr[], int n) {
// 生成 increment sequence
int h = 1;
while (h < n) {
h = h * 3 + 1;
}
// 等于 1 的时候进行最后一轮排序
while (h >= 1) {
// 对每个子序列进行排序
// 例如: 对于 1 2 3 4 5 6 7 8 9 10
// 首先, 子序列分别为:
// 1, 5
// 2, 6
// 3, 7
// 4, 8
// 1, 5, 9
// 2, 6, 10
int j;
T e = arr[j];
for (j = i; j > 0 && arr[j - h] > e; j -= h) {
arr[j] = arr[j - h];
}
arr[j] = e;
h /= 3;
}
}
