总结图
以下代码如无特殊说明,均为从小到大排序。
0x01 选择排序$O(n^2)$
- 原理:每次在未排序数组中找到最大/最小的值,放到该数组最后一个位置,然后在剩下的未排序数组中继续循环上述操作。第$i$轮($i$从$0$开始)时在$[0,n-i-1]$中找最值。共寻找$n-1$轮。
- 特点:依次找到未排序列的最值。
public static void selectionSort(int[] arr, int n) {
int maxIndex, temp;
for (int i = 0; i < n - 1; i++) {
maxIndex = 0;
for (int j = 0; j < n - i; j++) {
if (arr[j] > arr[maxIndex])
maxIndex = j;
}
temp = arr[n-1-i];
arr[n-1-i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
0x02 冒泡排序$O(n^2)$
- 原理:每次比较两个元素,如果顺序错误则交换位置。每次比较都会把最大/最小的值冒泡冒到最后,因此第$i$轮($i$从$0$开始)只需要比较$n-1-i$次,共需要比较$n-1$轮。
- 特点:比较并交换元素
public static void bubbleSort(int[] arr, int n) {
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 1; j < n - i; j++) {
if (arr[j-1] > arr[j]) {
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
0x03 插入排序O($n^{2}$)
- 原理:在有序序列基础上(初始从1个元素开始),每次插入一个元素到相应位置。
- 特点:比较元素+移动数组
public static void insertSort(int[] arr, int n) {
for (int i = 1; i < n; i++) {
//第一个元素作为基准元素,从第二个元素开始把其插到正确的位置
if (arr[i] < arr[i - 1]) {
//如果第i个元素比前面的元素小
int j = i - 1;
int temp = arr[i];
while (j >= 0 && temp < arr[j]) {
//找正确位置,比arr[i]大的元素依次后移
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
0x04 希尔排序$O(n^{1.3})$
又叫缩小增量排序,是插入排序的改进版。
- 原理:对数组按照一定间隔(即增量)进行分组,每个组都在组内进行插入排序,然后缩小增量再次分组,重复上述。核心是增量,常见的希尔增量初始化是$n/2$,每次缩小$2$倍。
常用增量序列:
- 希尔增量:$\{N/2, (N / 2)/2, ..., 1\}$,最坏时间复杂度是$O(n^{2})$
- Hibbard:$\{1, 3, ..., 2^k-1\}$,最坏时间复杂度是$O(n^{1.5})$
- Sedgewick:$\{1, 5, 19, 41, 109...\}$该序列中的项或者是$9*4^i - 9*2^i + 1$或者是$4^i - 3*2^i + 1$
- 特点:分组,组内插入排序
// 希尔增量
public static void shellSort(int[] arr, int n) {
for (int step = n / 2; step > 0; step /= 2) {
// 对每个分组进行插入排序
for (int i = 0; i < step; ++i) {
for (int j = i + step; j < n; j += step) {
if (arr[j] < arr[j - step]) {
int temp = arr[j];
int k = j - step;
while (k >= 0 && arr[k] > temp) {
arr[k + step] = arr[k];
k -= step;
}
arr[k + step] = temp;
}
}
}
}
}
// Hibbard增量
public static void shellSortByHibbard(int[] arr, int n) {
// 先找到增量序列的最大值,然后递减到1
int t = 1;
while((1 << t) - 1 < n) t++;
t --;
// 此时(2^t)-1是增量序列的最大值, 递减到1
while (t > 0) {
int step = (1 << t) - 1;t --;
// 对每个分组进行插入排序
for (int i = 0; i < step; ++i) {
for (int j = i + step; j < n; j += step) {
if (arr[j] < arr[j - step]) {
int temp = arr[j];
int k = j - step;
while (k >= 0 && arr[k] > temp) {
arr[k + step] = arr[k];
k -= step;
}
arr[k + step] = temp;
}
}
}
}
}
0x05 堆排序$O(n\log n)$
- 原理:利用堆这种数据结构,依次从堆顶中取出最值放到数组中。每次取出都要shiftDown调整树($O(\log n)$),取$n$次。
- 特点:数据结构堆
private static int pop() {
int t = arr[1];
arr[1] = arr[size--];
shiftDown(1);
return t;
}
private static void push(int x){
arr[++size] = x;
shiftUp(size);
}
private static void shiftUp(int idx){
while(idx > 1 && arr[idx] < arr[idx>>1]){
int j = idx >> 1;
int t = arr[idx]; arr[idx] = arr[j]; arr[j] = t;
idx >>= 1;
}
}
private static void shiftDown(int idx){
while (idx * 2 <= size) {
int j = idx << 1;
if(j + 1 <= size && arr[j+1] < arr[j])
j = j | 1;
if(arr[idx] < arr[j]) break;
int t = arr[idx]; arr[idx] = arr[j]; arr[j] = t;
idx = j;
}
}
public static int size;
private static int[] arr = new int[N]; //堆
private static int[] res = new int[N]; //结果数组
/***** main *****/
for(int i = 1 ; i <= n ; i ++){
int x = sc.nextInt();
push(x);
}
for(int i = 0 ; i < n ; i ++){
res[i] = pop();
}
0x06 快速排序/快排/三路快排$O(n\log n)$
- 原理:通过一趟排序将序列分为三部分,小于关键字+ 等于关键字 +大于关键字。然后进而对这两部分分别进行排序。当数组有大量重复元素时仍然保持较高性能。
- 特点:分治法,拆分数组
原始/二路快排:
- 原始快排:将序列分为两部分,小于关键字+大于等于关键字(或小于等于关键字+大于关键字)
- 二路快排:将序列分为两部分,小于等于关键字+大于等于关键字。避免了原始快排遇大量重复元素退化到$O(n^2)$
public static void quickSort(int l, int r){
if (l >= r) return;
// ===== partition分区操作 =====
int t = l + r >> 1; // 取中间的值作为关键字
int i = l - 1, j = r + 1, x = arr[t];
while (i < j){
do i ++ ; while (arr[i] < x);
do j -- ; while (arr[j] > x);
if (i < j) {
int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
边界问题:
- 递归$[l, j ]$和$[j + 1, r]$的时候,防止死循环,$t$不能取到右边界,要写$l + r $
- 递归$[l, i -1 ]$和$[i, r]$的时候,防止死循环,$t$不能取到左边界,要写$l + r + 1$
当$l=0, r = 1$时,结束时$j=t-1$
快排优化
小区间使用插入排序优化
0x07 归并排序$O(n\log n)$
- 原理:将已有序的子序列数组合并,得到完全有序的序列。一般是每次将两个有序的数组合并,称为2-路归并
- 特点:分治法,合并数组
//public static int[] temp = new int[N];
public static void mergeSort(int[] arr, int l, int r){
if(l >= r) return;
int mid = l + r >> 1;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
temp[k ++] = arr[i] <= arr[j] ? arr[i ++] : arr[j ++];
while(i <= mid)
temp[k ++] = arr[i ++];
while(j <= r)
temp[k ++] = arr[j ++];
for(i=l, j =0 ; j < k ; i ++, j++)
arr[i] = temp[j];
}
0x08 桶排序
- 原理:类似哈希的链地址法,利用函数映射将数组序列映射到一些槽/桶中,这样这些不同桶中的数天然具备了大小关系。比如$[10,34, 5,7,13,25,11,31,23]$,按$\div 10$关系映射结果如下。
桶 | 元素 |
---|---|
0 | $5, 7$ |
1 | $10, 13, 11$ |
2 | $25, 23$ |
3 | $34,31$ |
可以看到,关系是$0$号桶元素 < $1$号桶元素 < $2$号桶元素 < $3$号桶元素,在每一个桶内进行元素排序,然后按照桶的顺序遍历元素即可。
- 特点:映射到桶+桶内排序+桶间天然有序
- 核心问题:映射函数,需要对不同的场景设计不同的映射函数。
- 注意:对负数特判
代码略
0x09 基数排序(LSD)
- 原理:遍历每一位上的数字,先看个位,按照个位的值放入0~10的桶中,然后依次取出(此时个位有序),接着看十位,重复上述操作,此时十位有序。
- 特点:依次对个位十位百位进行排序。
- 注意:对负数特判
代码略
0x0A 计数排序
- 原理:遍历数组,计算每个数出现的次数,然后按顺序输出。
- 特点:统计出现次数
- 注意:对负数特判
代码略
桶/基数/计数 排序比较
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
- 桶排序:每个桶存储一定范围的数值;
- 计数排序:每个桶只存储一个值;
- 基数排序:根据值的每一位上的数字来分配桶;
- - - 结束 - - -