-
排序算法——七种排序算法汇总，详细
排序
排序的概念及应用
排序∶所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定的。一、直接插入排序
1. 简介
是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
2.动图展示
3.过程
1. 将序列中第一个元素看为有序的，将数组划分为有序和无序部分
- 下标i为待排序元素下标，从1开始。n个数需要n-1次遍历。
- j=i-1
2.每一次插入的比较都是从前一个数开始。即i下标位置待排序元素，与有序部分[0,j]下边处的末尾元素依次向前进行比较
-
若array[i]>array[j]:则array[j+1]=array[i]
下标 i 处的元素插入到 j+1 位置。
-
若array[i]
-
array[j+1]=array[j] , 执行 j-- 操作
-
不断与 j 下标元素比较，出现小于2的数，找到了插入位置，所以跳出循环，2就可以插入数组了，下标是j+1
3.i++，待排序元素更新，同样执行第二步操作，直至无序部分所有元素遍历完成为止
如上依次操作即可。
当待排序元素为2时，如下
经过排序插入后结果为如下：
可见经排序后，两个 2 的相对次序保持不变，说明直接插入排序是稳定的。
4.代码
public class TestSort { /** * 直接插入排序： * 时间复杂度： * 最坏情况下：O(N^2) 逆序的 * 最好情况下：O(N) 有序 如果 以后 数据量不大 而且基本上 趋于有序【优化】 * 空间复杂度：O(1) * 稳定性：稳定 * * 一个本身就稳定的排序，一定也可以实现为不稳定的 * * 但是本身就是不稳定的排序，你能把它变为稳定的排序吗？ * * @param array */ public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i-1; for (; j >= 0; j--) { //>= if(array[j] > tmp) { array[j+1] = array[j]; }else { //array[j+1] = tmp; break;// } } array[j+1] = tmp; } } public static void main(String[] args) { int[] array = {1,5,2,7,9,6,5,7}; System.out.println("排序前："+Arrays.toString(array)); insertSort(array); System.out.println("排序后："+Arrays.toString(array)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
5.总结
时间复杂度：
- 最坏情况下：O(n^2)
- 最好情况下：O(n) 有序情况下
空间复杂度： O(1)
稳定性： 稳定二、希尔排序
1.简介
希尔排序法：又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap，把待排序文件中所有记录分成几个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取比上次数小的gap，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
2.过程
3.代码
import java.util.Arrays; import java.util.Random; import java.util.Stack; public class TestSort { /** * * * @param array * @param gap */ public static void shell(int[] array,int gap) { for (int i = gap; i < array.length; i++) { int tmp = array[i]; int j = i-gap; for (; j >= 0; j-=gap) { //>= if(array[j] > tmp) { array[j+gap] = array[j]; }else { //array[j+1] = tmp; break;// } } array[j+gap] = tmp; } } /** * 时间复杂度： * * 空间复杂度： * O(1) * 稳定性： * 不稳定 * @param array */ public static void shellSort(int[] array) { int gap = array.length;//10 while (gap > 1) { gap /= 2; shell(array,gap); } shell(array,1); } public static void main(String[] args) { int[] array = {1,5,2,7,9,6,5,7}; System.out.println("排序前："+Arrays.toString(array)); shellSort(array); System.out.println("排序后："+Arrays.toString(array)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
4.总结
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap ==1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3.希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度: O(N^1.3)
O(N^2)
4. **空间复杂度：**O(1)
5. 稳定性: 不稳定三、选择排序
1.简介
每一次 **从待排序的数据元素**中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
2.代码
import java.util.Arrays; import java.util.Random; import java.util.Stack; public class TestSort { /** * 选择排序： * 时间复杂度：O(N^2) * 空间复杂度：O(1) * 稳定性： 不稳定 * @param array */ public static void selectSort(int[] array) { for(int i=0;i<array.length;i++){ for(int j=i+1;j<array.length;j++){ if(array[j]<array[i]){ swwap(array,i,j); } } } } public static void selectSort2(int[] array) { for(int i=0;i<array.length;i++){ int minIndex=i;//记录 最小值的下标 int j=i+1; for(;j<array.length;j++){ if(array[j]<array[minIndex]){ minIndex=j; } } swwap(array,i,minIndex); } } public static void swap(int[] array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } public static void main(String[] args) { int[] array = {1,5,2,7,9,6,5,7}; System.out.println("排序前："+Arrays.toString(array)); selectSort(array); System.out.println("排序后："+Arrays.toString(array)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
3.总结
时间复杂度： O(n^2)
空间复杂度： O(1)
稳定性： 不稳定
四、堆排序
1.代码
import java.util.Arrays; import java.util.Random; import java.util.Stack; public class TestSort { /** * 堆排序 * 时间复杂度：O(n*logn) 和数据有序无序无关 * 空间复杂度：O(1) * 稳定性：不稳定 * @param array */ public static void heapSort(int[] array) { //1、大根堆 O(N) createHeap(array); //2、排序O(n*logn) int end = array.length-1; while (end > 0) { swap(array,0,end); shiftDown(array,0,end);//向下调整大根堆 end--; } } private static void createHeap(int[] array) { for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) { shiftDown(array,parent,array.length); } } private static void shiftDown(int[] array,int parent,int len) { int child = (2*parent)+1; while (child < len) { if(child+1 < len && array[child] < array[child+1]) { child++;//他一定保存的是左右孩子的最大值的下标 } if(array[child] > array[parent]) { swap(array,child,parent); parent = child; child = 2*parent+1; }else { break; } } } public static void swap(int[] array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } public static void main(String[] args) { int[] array = {1,5,2,7,9,6,5,7}; System.out.println("排序前："+Arrays.toString(array)); heapSort(array); System.out.println("排序后："+Arrays.toString(array)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
2.总结
时间复杂度： O(n*logn) 和数据有序无序无关
空间复杂度： O(1)
**稳定性：**不稳定
五、冒泡排序
1.过程
2.代码
import java.util.Arrays; import java.util.Random; import java.util.Stack; public class TestSort { /** * 冒泡排序 * 不针对优化： * 时间复杂度：O(N^2) * 空间复杂度：O(1) * 稳定性：稳定 * @param array */ public static void bubbleSort(int[] array) { for (int i = 0; i < array.length-1; i++) { //boolean flg = false; for (int j = 0; j < array.length-1-i; j++) { if(array[j] > array[j+1]) { swap(array,j,j+1); //flg = true; } } //if(flg == false) { // break; //} } } public static void main(String[] args) { int[] array = {1,5,2,7,9,6,5,7}; System.out.println("排序前："+Arrays.toString(array)); bubbleSort(array); System.out.println("排序后："+Arrays.toString(array)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
3.总结
时间复杂度： O(N^2)
空间复杂度： O(1)
稳定性： 稳定
六、快速排序
1.简介
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为∶任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。将区间按照基准值划分为左右两半部分的常见方式有:
- hoare版本
- 挖坑法
- 前后指针版本
分而治之的思想，它的排序过程是一个递归调用的过程。
2.过程
一趟排序过程如下,
从上图可以看到，完整的快速排序是建立在一趟快速排序之上的，它的具体步骤如下：- 首先对待排序序列进行一趟快速排序；
- 一趟排序下来之后，基准元素（如30)的左边都是比它小的元素，右边都是比它大的元素；
- 再对基准元素左边的序列进行快速排序，对右边也进行快速排序；
- 重复步骤2、3，直到序列排序完成。
3.两种优化快速排序的思想
1.三数取中
面对完全有序的数组，快速排序每趟排序后，key的位置都在边缘，每层递归都只能固定一个数，时间复杂度变成了O(N^2)。面对这种情况，我们可以在取key时动手脚。每次取key我们不再只取最左或最右的值。而是对比最左、最右、中间的三个元素，取三个元素中，值在另外两者中间的元素作为key。这样，就打乱了有序数组，大大加快了快速排序在面对这种情况时的速度。
2.小区间优化
快速排序对一个元素不多的数组排序，仍需要进行多次递归调用，我们知道递归是比较消耗资源的，所以为了避免在快速排序递归的最后几层大量调用函数，我们可以在数组元素较少时不再递归，而是采用直接插入排序替代，这样就能在不损失多少速度的情况下减少大量的递归次数，达到优化速度的目的。4.代码-递归、非递归、优化
```java import java.util.Arrays; import java.util.Random; import java.util.Stack; public class TestSort { /** * 快速排序： * * 时间复杂度： * 最好情况：O(n*logn) 可以每次 尽量将待排序序列 均匀的分割 * 最坏情况：O(n^2) 正序 逆序 * 空间复杂度： * 最好情况：O(logn) * 最坏情况：O(N) * * 稳定性：不稳定的排序 * * @param array */ public static void quickSort1(int[] array) { quick(array,0,array.length-1); } /** * 三数取中法 * @param array * @param left * @param right * @return 三个数中的 中间数字的下标 */ private static int threeMid(int[] array,int left,int right) { int mid = (left+right) >>> 1; if(array[left] < array[right]) { if(array[mid] < array[left]) { return left; }else if(array[mid] > array[right]) { return right; }else { return mid; } }else { // array[left] > array[right] if(array[mid] < array[right]) { return right; }else if(array[mid] > array[left]) { return left; }else { return mid; } } } /** * * @param array */ private static void insertSort2(int[] array,int start,int end) { for (int i = start+1 ; i <= end; i++) { int tmp = array[i]; int j = i-1; for (; j >= start; j--) { //>= if(array[j] > tmp) { array[j+1] = array[j]; }else { //array[j+1] = tmp; break;// } } array[j+1] = tmp; } } private static void quick(int[] array,int start,int end) { if(start >= end) { return; } //递归到小区间时，插入排序 if(end-start+1 <= Constant.INSERT_SIZE) { //插入排序 insertSort2(array, start, end); return; } //三数取中法-》start end mid 找到中间的数字 //有序数据下的优化 int index = threeMid(array,start,end); swap(array,index, start); int pivot = partition(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); } /** * 快速排序：非递归实现 * @param array */ public static void quickSort(int[] array) { Stack<Integer> stack = new Stack<>(); int start = 0; int end = array.length-1; int pivot = partition(array,start,end); //左边有2个元素及以上 if(pivot > start+1) { stack.push(start); stack.push(pivot-1); } //右边有2个元素及以上 if(pivot < end-1) { stack.push(pivot+1); stack.push(end); } while (!stack.empty()) { end = stack.pop(); start = stack.pop(); pivot = partition(array,start,end); //左边有2个元素及以上 if(pivot > start+1) { stack.push(start); stack.push(pivot-1); } //右边有2个元素及以上 if(pivot < end-1) { stack.push(pivot+1); stack.push(end); } } } /** * 一次划分函数 * @param array * @param left * @param right * @return */ private static int partition(int[] array,int left,int right) { int tmp = array[left]; while (left < right) { //1 2 3 4 5 while (left < right && array[right] >= tmp) { right--; } //右边 找到小于tmp的数据 array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } //右边 找到小于tmp的数据 array[right] = array[left]; } array[left] = tmp; return left; } public static void main(String[] args) { int[] array = new int[10_0000]; Random random = new Random(); for (int i = 0; i < array.length; i++) { array[i] = i; //array[i] = random.nextInt(10_0000); } long startTime = System.currentTimeMillis(); quickSort(array); long endTimes = System.currentTimeMillis(); System.out.println(endTimes-startTime); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
public class Constant { public static final int INSERT_SIZE = 100; }- 1
- 2
- 3
- 4
5.总结
时间复杂度：
- 最坏情况下：有序：O(n^2)
- 最好情况下：O(n*logn) 尽量将待排序序列均匀分割
空间复杂度：
- 最坏情况下：O(n)
- 最好情况下：O(logn)
稳定性： 不稳定
七、归并排序
1.简介
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤:
2.过程
3.代码
1.递归
/** * 归并排序 * 时间复杂度：n*logn 不管有序还是无序 * 空间复杂度：O(N) * 稳定性：稳定 * * 冒泡 插入 归并 * @param array */ public static void mergeSort(int[] array) { mergeSortFunction(array,0,array.length-1); } private static void mergeSortFunction(int[] array,int low,int high) { if(low >= high) { return; } int mid = (low+high) >>> 1; mergeSortFunction(array,low,mid); mergeSortFunction(array,mid+1,high); merge(array,low,high,mid); } /** * 实现这个合并函数 * @param array * @param low * @param high * @param mid */ private static void merge(int[] array,int low,int high,int mid) { int[] tmp = new int[high-low+1]; int k = 0; int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; while (s1 <= e1 && s2 <= e2) { //两个归并段 都有数据 if(array[s1] <= array[s2]) { tmp[k++] = array[s1++]; }else { tmp[k++] = array[s2++]; } } while (s1 <= e1) { tmp[k++] = array[s1++]; } while (s2 <= e2) { tmp[k++] = array[s2++]; } for (int i = 0; i < k; i++) { array[i+low] = tmp[i]; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
2.非递归
/** * 归并排序 ：非递归 * @param array */ public static void mergeSort2(int[] array) { int gap = 1; while (gap < array.length) { for (int i = 0; i < array.length; i += gap*2 ) { int low = i; int mid = low+gap-1; if(mid >= array.length) { mid = array.length-1; } int high = mid+gap; if(high >= array.length) { high = array.length-1; } merge(array,low,high,mid); } gap = gap*2; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
海量数据排序问题
概念
内部排序:数据在内存上
外部排序:排序过程需要在磁盘等外部存储进行的排序
前提: 内存有1G，需要排序的数据有100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序过程
- 先把文件切分成200份，每个512 M
- 分别对512M排序，因为内存已经可以放的下，所以任意排序方式都可以
- 200份文件进行2路归并，同时对200份有序文件做归并过程，最终结果就有序了
-
相关阅读:
前端二维码图片解析图片识别/网络图片解析成链接/图片网络链接转本地链接(Js/Vue/Jquery)
小小博客项目（servlet实战演练）
web前端高级学习：深入探索与实战进阶
海量数据插入的各种方案试验
webm格式怎么转换成mp4？
多态的使用以及多态底层的实现（上）
Linux文件内容查看相关指令
huggingface_hub v0.17 现已发布
InetAddress.getLocalHost() 执行很慢？
Python爬取小说（requests和BeautifulSoup）
- 原文地址：https://blog.csdn.net/xy199931/article/details/127934078
