-
【数据结构】七大排序
**内部排序：**数据全部放在内存中的排序**外部排序：**如果数据量比较大，内存中放不下，不能在内外存之间进行数据的移动，需要放在硬盘上进行排序，这样的排序称为外部排序；
学习排序要熟练的掌握每一种排序的时间复杂度，稳定性，这样在场景中才可以运用自如；
💐1. 插入排序
🌼1.1 直接插入排序
遍历集合中的每一个元素，每一个元素都作为一个关键码与前面的元素作比较，如果小于前面的元素，前面的元素就向后移动，直到遇见比关键码大的元素，就插入在该元素后一个位置，这也会使得每一个数值作为关键码时，前面的元素都是已经排好序的；
直接插入排序特性：
-
元素集合越接近有序，直接插入排序时间效率就越高(因为，如果前面都是13456已经排序好的，忽然遇见一个2，那么前面需要移动的元素就会更多)
-
时间复杂度：
最好的情况是O(n),数组本来就是有序的 例如 1 2 3 4 5
最坏情况是O(n^2),数组是逆序的 例如 5 4 3 2 1
-
空间复杂度：O(1)
-
稳定性：稳定
这里提到了稳定性，下面来解释一下什么是稳定性：
稳定性：假设在一个序列中，出现了相同的数据，经过排序之后，这些相同的数据之间的相对位置保持不变，比如，r[i] = r[j], 在排序之前，r[i] 在 r[j] 之前，排序之后，r[i] 仍然在 r[j] 之前，则这样的排序称为是稳定的，反之是不稳定的；而且一个稳定的排序是可以变成不稳定的，但是一个不稳定的排序是不可以变成稳定的；
代码实现
//直接插入排序 public void insert(int[] array) { //元素数量不能小于1 if(array.length < 1) { return; } //定义i遍历每一个元素 for(int i = 1; i<array.length; i++) { //定义j遍历i前面的元素 int j = i-1; //定义关键码key保存i对应的值 int key = array[i]; for(; j>=0; j--) { //符合条件进行移动 if(array[j] > key) {//如果这里变成>=就变成了不稳定的 array[j+1] = array[j]; }else { break; } } //最后将key插入 array[j+1] = key; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
🌼1.2 希尔排序
思想：希尔排序又称缩小增量法， 定义一个增量值，将集合中的数据按照这个增量值进行分组，每一组中元素之间的距离都是这个增量值，每一次缩小增量时都进行了预排序，最后增量值为1时，完成排序；
希尔排序特性：
-
希尔排序是对直接插入排序的优化
-
当gap > 1 时都是预排序，目的是为了让数组跟趋近有序，当gap == 1时，数组已经接近有序了，这样整体而言就可以达到优化效果；
-
希尔排序的时间复杂多每办法确定，因为gap的取值方法很多，导致很难去计算，一般都会对gap进行除2来缩小增量
-
稳定性：不稳定
代码实现：
//希尔排序 public void shellSort(int[] array) { //定义增量 int gap = array.length / 2; while(gap > 0) { for(int i = gap; i<array.length; i++) { int j = i - gap; int key = array[i]; for(; j>=0; j -= gap) { if(array[j] > key) { array[j+gap] = array[j]; }else{ break; } } array[j+gap] = key; } gap /= 2; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
💐2. 选择排序
🌼2.1 直接选择排序
思想：每一次从待排序的数据集合中取出最小的一个，然后与序列起始位置处的元素进行交换，直到全部待排序的元素排完；
代码实现：
//选择排序 public void selectSort(int[] array) { if(array.length < 1){ return; } for(int i = 0; i<array.length; i++) { //用来存放最小元素下标 int min = array[i]; //遍历待排序元素 for(int j = i; j < array.length; j++) { //符合条件更新最小值 if(array[j] < array[min]) { min = j; } } //交换 swap(array, i, min); } } private void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }- 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
🌼2.2 堆排序
堆排序，根据名字就可以了解到肯定是需要建堆的，而前面也已经讲过了建大(小)根堆的步骤，下面就直接利用现成的大根堆进行讲解；
如果要排升序建立大根堆，排降序建立小根堆，步骤如下：
-
先建立一个大根堆
-
交换第一个和n-i (i=1、2、3、4….)个节点，直到n-i=0时不用再交换
-
进行向下调整，重新构建大根堆结构
代码实现：
public void heapSort(int[] array) { //建立大根堆 buildHeap(array); //拿到最后一个节点的下标 int len = array.length-1; for(int i = len; i>0; i--) { //交换第一个和最后一个节点值 swap(array, 0, i); //向下调整 shiftDown(array, 0, i); } } //堆排序 //建立大根堆 public void buildHeap(int[] array) { int len = array.length; for(int parent = (len-2)/2; parent >= 0; parent--) { shiftDown(array, parent, len); } } //向下调整 private 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, parent, child); //保证子树的大根堆结构不会被破坏 parent = child; child = (2*parent)+1; }else { break; } } }- 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
堆排序特性：
- 时间复杂度：O(N*logn),因为每一个元素都需要遍历到，每一次与堆顶元素交换后也都需要进行向下调整；
- 空间复杂度：O(1)
- 稳定性：不稳定
💐3. 交换排序
思想：对序列中的两个值进行比较，根据比较结果来交换这两个值，特点是：升序(降序)较大(较小)的值向尾部移动，值较小(较大)的数据向首部移动;
🌼3.1 冒泡排序
代码实现:
//冒泡排序 public void bubbleSort(int[] array) { int len = array.length; boolean flag = true; for(int i = 0; i<len; i++) { for(int j = 0; j<len-i-1; j++) { if(array[j] > array[j+1]) { swap(array, j, j+1); //代码优化，定义一个flag flag = false; } } //如果flag是true，说明遍历一趟下来，没有进行交换，则表示序列此时已经有序了，就不用再遍历剩下的元素了 if(flag) { return; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
冒泡排序特性：
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
🌼3.2 快速排序
思想：从待排序的序列中任取一个元素作为基准值，然后遍历这个序列，让每个元素都与基准值比较，最后这个序列会根据基准分为两个左右子序列，左子序列中所有的值都比基准小，右子序列中所有的值都比基准大，然后再分别对两个子序列进行分割，最后序列就会变成有序
//快速排序 public void quick_sort(int[] array) { //定义左边界和右边界 int left = 0; int right = array.length-1; //进行快速排序 quickSort(array, left, right); } private void quickSort(int[] array, int left, int right) { //出口为左右边界相等时或右边界小于左边界 if(right - left <=1) { return; } //求基准，此时序列会分为左右两个子序列 //求基准的方法分为三种 int div = partion(array); //分割成功后，根据div分为左右两部分[left, div] 和 [div+1, right] //递归[left, div] quickSort(array, left, div); //递归[right, div+1] quickSort(array, div+1, right); }- 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
以上就是快速排序的模板，有点类似与二叉树的遍历，重点就是求基准的方法，下面介绍三种求基准的方法；
- Hoare法
代码实现：
private int hoare(int[] array, int left, int right) { //记录基准值 int key = array[left]; //记录基准值下标 int pos = left; while(left < right){ //寻找比基准值小的元素 while(left < right && array[right] >= key) { right--; } //寻找比基准值大的元素 while(left < right && array[left] <= key) { left++; } //交换 swap(array, left, right); } //根据基准分割成两个子序列 swap(array, left, pos); return left; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
-
挖坑法
代码实现：
//挖坑法 private int digHole(int[] array, int left, int right) { //存储基准值 int key = array[left]; while(left < right) { //寻找比基准小的元素 while(left < right && array[right] >= key) { right--; } //将left坑填上 array[left] = array[right]; //寻找比基准值大的元素 while(left < right && array[left] <= key) { left++; } //将right坑填上 array[right] = array[left]; } array[left] = key; return left; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
-
前后指针法
代码实现
private int twoPointer(int[] array, int left, int right) { int pre = left; int cur = pre+1; while(cur < array.length){ if(array[cur]<array[left] && array[++pre] != array[cur]) { swap(array, cur, pre); } cur++; } swap(array, left, pre); return pre; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
注意点：
如果利用快速排序的方法对十万个有序的数据进行排序，就造成了栈溢出，因为，如果本来就是升序的话，这颗二叉树就是一颗单支树，而采用快速排序时，是要进行递归的，每一次递归都是需要在栈上开辟空间的，造成了时间复杂度是 O(n^2), 空间复杂度是 O(n), 所以就会遭成栈溢出：
🌼3.2.1 快速排序优化
下面介绍对快速排序进行优化，为了防止栈溢出，就要减少递归次数, 如果要减少递归次数就要降低树的高度，步骤为：
- 利用三数取中法找key
private void quickSort(int[] array, int left, int right) { //出口为左右边界相等时或右边界小于左边界 if(right - left <=1) { return; } //三数取中 int mid = midOfThree(array, left, right); //和第一个交换 swap(array, left, mid); //求基准，此时序列会分为左右两个子序列 //求基准的方法分为三种 int div = hoare(array, left, right); //int div = digHole(array, left, right); //int div = twoPointer(array, left, right); //分割成功后，根据div分为左右两部分[left, div] 和 [div+1, right] //递归[left, div] quickSort(array, left, div); //递归[right, div+1] quickSort(array, div+1, right); } private int midOfThree(int[] array, int left, int right) { //找中间值 int mid = (right- left)/2+left; //查找第二大数字 if(array[left] < array[right]) { //情况1： 5 3 9 if(array[mid] < array[left]) { return left; }else if(array[mid] > array[right]) { //情况2：3 9 5 return right; }else { return mid; } }else { //情况1：5 9 3 if(array[mid] > array[left]) { return left; }else if(array[mid] < array[right]) { //情况2：9 3 5 return right; }else { return mid; } } }- 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
虽然利用三数取中法采用了降低树的高度，但是很可能还会造成栈溢出，但是如果在其他的编译器上可能就能跑过，一个原因是IDEA默认的栈空间比较小，解决方法是可以修改IDEA默认的栈空间大小：
另一个原因是对于三数取中后代码还可以进行优化：
上述三数取中法是防止出现单支树而导致栈溢出情况，从而通过降低树的高度进行解决，但是例如一下这种情况：
2.当递归到小区间时可以采用插入排序
当递归到小区间时，序列已经趋于有序了，而插入排序在序列趋于有序的情况下效率最高，所以在递归到小区间时，可以采用插入排序；
if(right - left + 1 <= 15) { //采用插入排序 insertOfRange(array, left, right); return; } public void insertOfRange(int[] array, int start, int end) { //定义i遍历每一个元素 //对区间内的元素进行插入排序 for(int i = start+1; i<= end; i++) { //定义j遍历i前面的元素 int j = i-1; //定义关键码key保存i对应的值 int key = array[i]; for(; j>=0; j--) { //符合条件进行移动 if(array[j] > key) { array[j+1] = array[j]; }else { break; } } //最后将key插入 array[j+1] = key; } }- 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
🌼3.2.2 快速排序非递归
代码：
public void quickSortNor(int[] array, int left, int right) { Stack<Integer> stack = new Stack<>(); //寻找一次基准 int pivot = digHole(array, left, right); //判断左边区间是否只有一个元素 if(pivot-1 > left){ //表示左区间不止一个元素 stack.push(left); stack.push(pivot-1); } if(pivot+1 < right) { //表示右区间不止一个元素 stack.push(pivot+1); stack.push(right); } //弹出栈中元素 while(!stack.isEmpty()) { //弹出左边界和右边界 right = stack.pop(); left = stack.pop(); //再次找基准 pivot = digHole(array, left, right); //判断左边区间是否只有一个元素 if(pivot-1 > left){ //表示左区间不止一个元素 stack.push(left); stack.push(pivot-1); } if(pivot+1 < right) { //表示右区间不止一个元素 stack.push(pivot+1); stack.push(right); } } }- 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
快速排序特性：
- 时间复杂度：O(n*logn)，因为快排对每一个元素都要操作，因为每一个元素都需要logn的时间复杂度，所以n个元素就是n *logn
- 空间复杂度:O(logn)
- 稳定性：不稳定
💐4. 归并排序
🌼4.1 基本思想
归并排序它是运用了分支算法的思想：分而治之，将一个序列分割成两份，对每一份再进行分割，一直分割到不能再分割，再进行合并；请看图解：
代码示例：
//归并排序 public void mergeSort(int[] array, int left, int right) { //递归出口 if(left >= right) { return; } //求中间位置元素 int mid = (right - left) / 2 + left; //递归左序列 mergeSort(array, left, mid); //递归右序列 mergeSort(array, mid+1, right); //合并两个序列，使序列有序 merge(array, left, right, mid); } private void merge(int[] array, int left, int right, int mid){ //申请一个数组用来存放合并后的元素 int[] tmp = new int[right-left+1]; //定义两个序列的首位置 int start1 = left; int start2 = mid+1; //记录新数组中待存放元素的下标 int index = 0; //合并序列中的元素 while(start1 <= mid && start2 <= right){ if(array[start1] < array[start2]) { tmp[index++] = array[start1++]; }else { tmp[index++] = array[start2++]; } } //检查哪一个序列没有遍历完 while(start1 <= mid) { tmp[index++] = array[start1++]; } while(start2 <= right) { tmp[index++] = array[start2++]; } //将tmp的元素再移动到array中 for(int i = 0; i<tmp.length; i++) { //i+left 定位到当前的序列的首位置，因为序列被分割后，每一个子序列的首位置都不一样 array[i+left] = 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
归并排序特性：
- 时间复杂度：O(n* logn)
- 空间复杂度：O(n)，因为需要常见新数组
- 稳定性：稳定
💐6. 海量数据进行排序
问题：如果有1G的内存，但是要对100G的的数据进行排序，应该怎么办？
解答：
因为100G的数据在内存中放不下，所以要利用外部排序，就像归并排序
外部排序：在磁盘等外部存储上进行的排序
1、将100G数据分为200份小文件，每个文件都是512M
2.将每一份文件都放进内存中进行排序
3、进行二路归并，合并200份文件
-
-
相关阅读:
Redis特性与应用场景
CI/CD最佳实践
价值几十亿美金的名字，Microsoft Windows的由来
基于OpenCV的灰度图的图片相似度计算
【CentOS 7】CentOS 7极致指南：高级部署PyCharm 2022.3.3专业版，实现定制化配置与无缝桌面集成
【C++】二叉搜索树
阿里云安全中心需要购买吗？功能及价格告诉你值不值！
陕西Biotin-LC_CAS:72040-64-3_N-生物素氨基己酸供应商价格
浅谈“文件与文件流”的区别
底层原理分析：探究SpringBoot底层对异常的处理机制
- 原文地址：https://blog.csdn.net/Shine0115/article/details/132898815
