常见的排序算法 【复习笔记】

注意：

1. 后面的排序算法实现都只考虑升序，对于逆序，只有知道原理，实现很容易

2. 案例题：

    题目描述：将读入的 N 个数从小到大输出 ( 1 <= N <=10e5)

    输入描述：第一行一个正整数 N  

                      第二行 N 个空格隔开的正整数 ai 

    输出描述：给定的 N 个数从小到大输出，空格隔开，行末换行无空格

    输入：5
               4 2 4 5 1

    输出：1 2 4 4 5

1. 插入排序

1.1 算法思想

每次将一个待排序元素按照关键字大小插入到已排序好的序列中

时间复杂度：1. 当整个序列升序，时间复杂度O(n)

                      2. 当整个序列逆序，时间复杂度O(N^2)

1.2 代码实现

​#include<iostream>
using namespace std;const int N = 1e5 + 10;
int a[N];
int n;void insert_sort()
{//从第二个元素开始，依次枚举待排序元素for (int i = 2; i <= n; i++){//先存储要排序的元素int tmp = a[i];//依次和前面的元素比较int j = i - 1;while ( a[j] > tmp&&j >= 1){a[j+1] = a[j];j--;}//当出循环时，要么a[j]<=tmp,要么遍历完已排序序列//直接在j+1的位置放入元素a[j+1] = tmp;}
}
int main()
{cin >> n;//从a[1]开始放入元素for (int i = 1; i <= n; i++) cin >> a[i];//插入排序insert_sort();for (int i = 1; i <= n; i++)cout << a[i] << " ";return 0;
}​

 2. 选择排序

2.1 算法思想

每次找出未排序序列的最小元素，然后放入有序序列后面

时间复杂度：总会遍历一遍所有未排序序列，时间复杂度O(n^2)

2.2 代码实现

#include<iostream>
using namespace std;const int N = 1e5 + 10;
int a[N];
int n;void selection_sort()
{//待排序序列为 [i,n]for (int i = 1; i < n; i++){//从 [i,n] 中选择最小值的位置int pos = i;for (int j = i+1; j <= n; j++){if (a[pos] > a[j]) pos = j;}//进行交换，将最小元素放入有序序列后面swap(a[i], a[pos]);}
}int main()
{cin >> n;//从a[1]开始放入元素for (int i = 1; i <= n; i++) cin >> a[i];//选择排序selection_sort();for (int i = 1; i <= n; i++)cout << a[i] << " ";return 0;
}

3. 冒泡排序

3.1 算法思想

进行 n -1 趟操作，每一趟进行多次比较，每次比较相邻的两个元素，如果满足排序条件，就交换；每趟可以将一个元素放到正确位置，像气泡一样，气泡大的慢慢冒出来，较大的数慢慢到最终的位置上

对于最朴素的冒泡排序，如果数组本身就是升序，还是会进行 n -1 趟操作，时间复杂度O(n^2)

但我们可以进行优化，如果有一趟操作，所有的元素都没有交换，证明数组已经是升序了，不用进行接下来的操作

优化后的冒泡排序时间复杂度：

1. 数组升序，只扫描一遍，时间复杂度O(n)

2. 数组逆序，时间复杂度O(n^2)

3.2 代码实现

#include<iostream>
using namespace std;const int N = 1e5 + 10;
int a[N];
int n;void bubble_sort()
{//进行 n - 1 趟排序for (int i = n; i > 1; i--){//标记是否交换元素bool flag = false;// [ 1,i] 为待排序区间for (int j = 1; j < i; j++){//每一趟比较相邻元素if (a[j] > a[j + 1]){swap(a[j], a[j + 1]);flag = true;}}//如果没交换元素，直接结束if (flag==false) return;}
}int main()
{cin >> n;//从a[1]开始放入元素for (int i = 1; i <= n; i++) cin >> a[i];//冒泡排序bubble_sort();for (int i = 1; i <= n; i++)cout << a[i] << " ";return 0;
}

4. 堆排序

4.1 算法思想

本质是优化选择排序，将数据放入堆（堆和STL —— priority——queue）中，可以快速得到待排序元素的最小值或最大值

步骤：1. 建堆，升序大根堆，降序小根堆。

              注意： 建堆不是新建一个堆结构，将数据放入新建的堆结构中。而是将数组的逻辑结构化为堆结构

               具体方法：从倒数第一个非叶子结点开始，倒着到根结点位置，每个结点向下调整

           2. 排序，每次将堆顶元素和堆最后一个元素交换，堆元素就少一个，将堆顶元素向下调整。直到堆剩一个元素

时间复杂度：1. 建堆的时间复杂度通过每个结点的调整层数计算约为O(n)

                      2. 排序的时间复杂度为O(nlog n)

所以总的时间复杂度为O(nlog n)

4.2 代码实现

#include<iostream>
using namespace std;const int N = 1e5 + 10;
int a[N];
int n;//向下调整
void down(int parent, int len)
{int child = parent * 2;while (child <= len){if (child + 1 <= len && a[child] < a[child+1])child++;if (a[parent] >= a[child])return;swap(a[parent], a[child]);parent = child;child = parent * 2;}
}void heap_sort()
{//建堆，从第一个非叶结点开始for (int i = n / 2; i >= 1; i--){down(i, n);}//排序for (int i = n; i > 1; i--){swap(a[i], a[1]);//堆元素减去1down(1, i-1);}
}
int main()
{cin >> n;//从a[1]开始放入元素for (int i = 1; i <= n; i++) cin >> a[i];//堆排序heap_sort();for (int i = 1; i <= n; i++)cout << a[i] << " ";return 0;
}

5. 快速排序

5.1 算法思想

5.1.1 常规快排

在待排序区间任取一个元素作为基准元素，按照这个基准元素的大小将区间元素分为左右两个部分，左边区间元素小于基准元素，右边区间元素大于等于基准元素。再递归排序基准值左区间和基准值右区间（其实，快速排序有点像树的先序遍历）

5.1.2 优化

有两种极端情况：

a. 如果每次选择基准元素为待排序序列的最左边元素，那如果整个序列升序，右区间每次划分都会很长，递归层数就是 n 层，那时间复杂度就退化为O(n^2)

b. 如果每次选择基准元素为待排序序列的中间元素，那如果整个序列为相同元素，那时间复杂度依旧会退化为O(n^2)

优化一：随机选择基准元素

#include<iostream>
#include<ctime>
using namespace std;int main()
{//种下一个种子srand(time(0));//获得一个随机数rand();return 0;
}

优化二：数组分三块（数组分块问题 【刷题反思】-CSDN博客）

按基准元素，小于基准元素的放入左边区间，等于基准元素的放入中间区间，大于基准元素的放入右边区间。中间区间不用管，递归处理左右区间即可

经过优化，块排的时间复杂度为O(nlog n)

5.2 代码实现

#include<iostream>
#include<ctime>
using namespace std;const int N = 1e5 + 10;
int a[N];
int n;int get_rand(int left,int right)
{//保证随机元素在区间内return  a[rand() % (right - left + 1) + left];
}void quick_sort(int left, int right)
{//递归结束条件if (left >= right) return;//得到随机基准元素int q = get_rand(left,right);//排序，数组分三块int l = left - 1, i = left, r = right + 1;while (i < r){if (a[i] < q) swap(a[++l], a[i++]);else if (a[i] == q)i++;else swap(a[--r], a[i]);}//递归处理左右区间quick_sort(left, l);quick_sort(r, right);
}
int main()
{cin >> n;//从a[1]开始放入元素for (int i = 1; i <= n; i++) cin >> a[i];//快速排序//种下一个随机数种子srand(time(0));quick_sort(1,n);for (int i = 1; i <= n; i++)cout << a[i] << " ";return 0;
}

6. 归并排序

6.1 算法思想

归并排序的思想是分治思想，先将整个数组区间从中间一分为二，然后把左右区间排序合并。这是递归实现的，每次都将先将区间一分为二，再排序（这一过程类似树的后序遍历）

时间复杂度：每次都是一分为二，时间复杂度可以稳定O(nlog n)

6.2 代码实现

#include<iostream>
using namespace std;const int N = 1e5 + 10;
int a[N];
int n;//创建辅助数组合并两个有序序列
int tmp[N];
void merge_sort(int left, int right)
{//递归结束条件if (left >= right) return;//先一分为二int mid = (left + right) / 2;//左右区间先有序merge_sort(left, mid);merge_sort(mid + 1, right);//合并左右两个有序区间int cur1 = left, cur2 = mid+1, i = left;while (cur1 <= mid && cur2 <= right){if (a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];else tmp[i++] = a[cur2++];}while (cur1 <= mid)tmp[i++] = a[cur1++];while(cur2 <= right)tmp[i++] = a[cur2++];for (int j = left; j <= right; j++){a[j] = tmp[j];}
}
int main()
{cin >> n;//从a[1]开始放入元素for (int i = 1; i <= n; i++) cin >> a[i];//归并排序merge_sort(1,n);for (int i = 1; i <= n; i++)cout << a[i] << " ";return 0;
}