排序算法
记录常用算法第一篇，内容来自各个角落，做一名合格的搬运工。
基本概念
时间复杂度：大O表示，衡量解决问题所需时间和问题规模之间的增长关系
空间复杂度：大O表示，衡量解决问题所需空间和问题规模之间的增长关系
稳定排序：相等的2个元素排序完成后相对位置不变，比如原来是A，B（A==B），排序后还是A，B
原地排序：元素在当前数组内直接完成排序，不借助其他临时数组
内部排序：在内存中直接完成数据排序
外部排序：借助外部磁盘存储完成数据排序
所有排序默认从小到大排序
n 为待排序数组的元素个数
1. 冒泡排序
| 时间复杂度 | 空间复杂度 | 稳定排序 | 原地排序 |
|---|---|---|---|
| O(n^2) | O(1) | 是 | 是 |
算法思想
-
比较相邻的元素，更大的元素交换到右边
-
每一轮从左到右，重复步骤1，结束后，最大的元素在最右边（冒泡效果）
-
每一轮选出的元素不参与下一轮比较
-
重复n-1次
-
设置标志，当某一轮没有元素交换时排序完成，不需要继续重复（优化手段）
实现代码
void swap(int a[],int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void bubble_sort(int a[], int n)
{
// 重复操作 n-1 次
for (int i = 0; i < n - 1; i++) {
bool flag = false;
// 相邻元素比较，大的往后交换（冒泡效果）
// 每一轮冒出
for (int j = 0; j < n- i - 1; j++) {
if (a[j] > a[j+1]) {
swap(a, j, j+1);
flag = true;
}
}
// 某一轮没有交换操作，
if (!flag) { return; }
}
}
2. 插入排序
| 时间复杂度 | 空间复杂度 | 稳定排序 | 原地排序 |
|---|---|---|---|
| O(n^2) | O(1) | 是 | 是 |
算法思想
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。
冒泡排序每一轮是数组的后端元素是排好序的
插入排序每一轮是数组的前端元素是排好序的
实现代码
void insertion_sort(int a[], int n) {
int i, j, temp;
// i - 1 之前是排好序的
for (i = 1; i < n; i++) {
temp = a[i];
for (j = i; j > 0 && a[j - 1] > temp; j--) {
// 把比 temp 大的数字往后移
a[j] = a[j - 1];
}
// temp 插入合适的位置
a[j] = temp;
}
}
3. 选择排序
| 时间复杂度 | 空间复杂度 | 稳定排序 | 原地排序 |
|---|---|---|---|
| O(n^2) | O(1) | 否 | 是 |
算法思想
第一次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
实现代码
void selection_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
// 每次选中最小的一个元素，放到 i 位置
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
swap(a, min, i);
}
}
4. 归并排序
| 时间复杂度 | 空间复杂度 | 稳定排序 | 原地排序 |
|---|---|---|---|
| O(nlogn) | O(n) | 是 | 否 |
算法思想
归并排序采用分治思想，采用递归实现，将待排序数组划分成（A，B）2部分，单独排序，然后合成一个有序数组。
对 A，B 排序递归上述过程，直到某次递归，数组无法划分（单个元素认为是排好序的），递归结束。
实现代码
void merge_sort(int a[],int n)
{
merge_sort_c(a, 0, n - 1);
}
void merge_sort_c(int a[], int p, int q)
{
// 数组无法划分，递归结束
if (p >= q)
return;
int r = (p+q)/2;
// [p...r],[r+1...q] 分别排序
merge_sort_c(a, p, r);
merge_sort_c(a, r + 1, q);
// 合并 [p...r],[r...q];
merge(a, p, r, q);
}
void merge(int a[],int p,int r,int q)
{
int i = p, j = r + 1;
int temp[q - p + 1];
int k = 0;
while (i <= r && j <= q) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
}
else {
temp[k++] = a[j++];
}
}
// 拷贝剩余部分
while (i <= r) {
temp[k++] = a[i++];
}
while (j <= q) {
temp[k++] = a[j++];
}
// 合并后的元素拷贝回原数组
for (int m = p; m <= q; m++) {
a[m] = temp[m - p];
}
}
5. 快速排序
| 时间复杂度 | 空间复杂度 | 稳定排序 | 原地排序 |
|---|---|---|---|
| O(nlogn) | O(1) | 否 | 是 |
算法思想
快排也是利用分治的思想，对数组以某个元素为基准划分，小的放左边，大的放右边，并对左右两边分别重复上述过程，直到无法划分为止。
实现代码
void quick_sort(int a[], int n)
{
quick_sort_c(a, 0, n - 1);
}
void quick_sort_c(int a[], int p, int q)
{
if (p >= q)
return;
int r = partition(a, p, q);
quick_sort_c(a, p, r - 1);
quick_sort_c(a, r + 1, q);
}
int partition(int a[],int p, int q)
{
// 随机化处理
int r = rand()%(q - p + 1) + p;
swap(a, r, q);
int pivot = a[q]; // pivot 为划分基准元素
int i = p; // i 代表已划分区间, i-1之前的都是比 pivot 小的
for (int j = p; j < q; j++) {
// 每找到一个比 pivot 小的，就将i往后移动
if (a[j] < pivot) {
swap(a, i, j);
i++;
}
}
swap(a, i, q);
return i;
}
6. 堆排序
| 时间复杂度 | 空间复杂度 | 稳定排序 | 原地排序 |
|---|---|---|---|
| O(nlogn) | O(1) | 否 | 是 |
算法思想
堆排序是利用堆这种数据结构的排序算法，堆的特点：
- 一颗完全二叉树（也就是生成节点的顺序是：上到下，左到右）
- 每一个节点必须满足父节点的值不大于（不小于）子节点的值
通过不断的堆化获取最大值，交换到数组最后面，数组前部分是堆结构，
后部分是排好序的元素序列。
实现代码
void heapify(int tree[], int n, int i) {
// n 表示序列长度，i 表示父节点下标
if (i >= n) return;
// 左侧子节点下标
int left = 2 * i + 1;
// 右侧子节点下标
int right = 2 * i + 2;
int max = i;
if (left < n && tree[left] > tree[max]) max = left;
if (right < n && tree[right] > tree[max]) max = right;
if (max != i) {
swap(tree, max, i);
heapify(tree, n, max);
}
}
void build_heap(int tree[], int n) {
// 树最后一个节点的下标
int last_node = n - 1;
// 最后一个节点对应的父节点下标
int parent = (last_node - 1) / 2;
int i;
for (i = parent; i >= 0; i--) {
heapify(tree, n, i);
}
}
void heap_sort(int tree[], int n) {
build_heap(tree, n);
int i;
for (i = n - 1; i >= 0; i--) {
// 将堆顶元素与最后一个元素交换
swap(tree, i, 0);
// 调整成大顶堆
heapify(tree, i, 0);
}
}
更多参考：动画详解十大经典排序算法
