0 算法速览
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用两张图概括：
1 冒泡排序
1. 算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
对于遍历一遍没有任何交换的情况,则直接跳出循环
2. 动图演示
3. 什么时候最快
当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。
4. 什么时候最慢
当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。
5. 代码实现
#include <iostream>
template <typename T>
void bubble_sort(T arr[], ssize_t len) {
for (int i = 0; i < len - 1; ++i) {
bool break_flag = true;
for (int j = 0; j < len - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
break_flag = false;
std::swap(arr[j], arr[j + 1]);
}
}
if (break_flag) break;
}
}
int main() {
int arr[] = {2, 3, 1, 5, 4};
bubble_sort(arr, 5);
for (auto n : arr) {
std::cout << n << std::endl;
}
std::cout << std::endl;
double arr1[] = {2.0, 3.1, 1.4, 5.9, 4.11};
bubble_sort(arr1, 5);
for (auto n : arr1) {
std::cout << n << std::endl;
}
}2 选择排序
1. 算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
2. 动图演示
3. 代码实现
#include <iostream>
template <typename T>
void select_sort(T arr[], ssize_t len) {
for (int i = 0; i < len - 1; ++i) {
int min = i;
for (int j = i + 1; j < len; ++j) {
if (arr[j] < arr[min]) {
min = j;
}
}
std::swap(arr[i], arr[min]);
}
}
int main() {
int arr[] = {2, 3, 1, 5, 4};
select_sort(arr, 5);
for (auto n : arr) {
std::cout << n << std::endl;
}
std::cout << std::endl;
double arr1[] = {2.0, 3.1, 1.4, 5.9, 4.11};
select_sort(arr1, 5);
for (auto n : arr1) {
std::cout << n << std::endl;
}
}3 插入排序
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
1. 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2. 动图演示
3. 代码实现
#include <iostream>
template <typename T>
void insertion_sort(T arr[], ssize_t len) {
for (int i = 1; i < len; ++i) {
int j = i - 1;
T key = arr[i];
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {2, 3, 1, 5, 4};
insertion_sort(arr, 5);
for (auto n : arr) {
std::cout << n << std::endl;
}
std::cout << std::endl;
double arr1[] = {2.0, 3.1, 1.4, 5.9, 4.11};
insertion_sort(arr1, 5);
for (auto n : arr1) {
std::cout << n << std::endl;
}
}4 希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
1. 算法步骤
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
2. 动图演示
3. 代码实现
#include <iostream>
template <typename T>
void shell_sort(T arr[], ssize_t len) {
int h = 1;
while (h < len / 3) {
h = h * 3;
}
while (h >= 1) {
for (int i = h; i < len; ++i) {
int j = i - h;
T key = arr[i];
while (j >=0 && arr[j] > key) {
arr[j + h] = arr[j];
j -= h;
}
arr[j + h] = key;
}
h /= 3;
}
}
int main() {
int arr[] = {2, 3, 1, 5, 4, -1};
shell_sort(arr, 6);
for (auto n : arr) {
std::cout << n << std::endl;
}
std::cout << std::endl;
double arr1[] = {2.0, 3.1, 1.4, 5.9, 4.11, -1.32};
shell_sort(arr1, 6);
for (auto n : arr1) {
std::cout << n << std::endl;
}
}5 归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现有两种方法：
自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
1. 算法步骤
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。
2. 动图演示
3. 代码实现
#include <iostream>
template<typename T>
void merge(T arr[], T res[], ssize_t left, ssize_t mid, ssize_t right) {
int start1 = left, start2 = mid + 1;
int end1 = mid, end2 = right;
int idx = left;
while (start1 <= end1 && start2 <= end2) {
res[idx++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= end1) res[idx++] = arr[start1++];
while (start2 <= end2) res[idx++] = arr[start2++];
for (int i = left; i <= right; ++i) {
arr[i] = res[i];
}
}
template <typename T>
void merge_sort(T arr[], T res[], ssize_t left, ssize_t right) {
if (left >= right) return;
int mid = (left + right) / 2;
merge_sort(arr, res, left, mid);
merge_sort(arr, res, mid + 1, right);
merge(arr, res, left, mid, right);
}
int main() {
int arr[] = {2, 3, 1, 5, 4, -1};
int len = sizeof(arr)/sizeof(int);
int* res = new int[len]();
merge_sort(arr, res, 0, len - 1);
for (auto n : arr) {
std::cout << n << std::endl;
}
std::cout << std::endl;
for (int i = 0; i < len; ++i) {
std::cout << res[i] << std::endl;
}
delete[] res;
std::cout << std::endl;
double arr1[] = {2.0, 3.1, 1.4, 5.9, 4.11, -1.32};
int len1 = sizeof(arr1)/sizeof(double);
double* res1 = new double[len1]();
merge_sort(arr1, res1, 0, len1 - 1);
for (auto n : arr1) {
std::cout << n << std::endl;
}
std::cout << std::endl;
for (int i = 0; i < len; ++i) {
std::cout << res1[i] << std::endl;
}
delete[] res1;
}6 快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
1. 算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
2. 动图演示
3. 代码实现
#include <iostream>
template <typename T>
int partition(T arr[], int low, int high) {
T pivot = arr[low];
while (low < high) {
while (low < high && pivot <= arr[high]) --high;
std::swap(arr[low], arr[high]);
while (low < high && pivot >= arr[low]) ++low;
std::swap(arr[low], arr[high]);
}
arr[low] = pivot;
return low;
}
template <typename T>
void quick_sort(T arr[], int low, int high) {
if (low >= high) return;
int mid = partition(arr, low, high);
quick_sort(arr, low, mid - 1);
quick_sort(arr, mid + 1, high);
}
int main() {
int arr[] = {2, 3, 1, 5, 4, -1};
int len = sizeof(arr)/sizeof(int);
quick_sort(arr, 0, len - 1);
for (auto n : arr) {
std::cout << n << std::endl;
}
std::cout << std::endl;
double arr1[] = {2.0, 3.1, 1.4, 5.9, 4.11, -1.32};
int len1 = sizeof(arr1)/sizeof(double);
quick_sort(arr1, 0, len1 - 1);
for (auto n : arr1) {
std::cout << n << std::endl;
}
}7 堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
1. 算法步骤
创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
2. 动图演示
3. 代码实现
#include <iostream>
template <typename T>
void max_heap(T arr[], ssize_t start, ssize_t end) {
ssize_t father = start;
ssize_t child = father * 2 + 1;
while (child <= end) {
if (child + 1 <= end && arr[child] <= arr[child + 1]) ++child;
if (arr[father] >= arr[child]) return;
std::swap(arr[father], arr[child]);
father = child;
child = father * 2 + 1;
}
}
template <typename T>
void heap_sort(T arr[], ssize_t len) {
// 初始化, 从中间到0先调整一遍，让所有子树的父结点都是大根堆
for (int i = len / 2; i >= 0; --i) {
max_heap(arr, i, len - 1);
}
// 將第一位和最后一位做交换，再从新调整
for (int i = len - 1; i > 0; --i) {
std::swap(arr[0], arr[i]);
max_heap(arr, 0, i - 1);
}
}
int main() {
int arr[] = {2, 3, 1, 5, 4, -1};
int len = sizeof(arr)/sizeof(int);
heap_sort(arr, len);
for (auto n : arr) {
std::cout << n << std::endl;
}
std::cout << std::endl;
double arr1[] = {2.0, 3.1, 1.4, 5.9, 4.11, -1.32};
int len1 = sizeof(arr1)/sizeof(double);
heap_sort(arr1, len1);
for (auto n : arr1) {
std::cout << n << std::endl;
}
}
评论区