排序(Java数据结构)
1. 排序的概念及引用
1.1 排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。(所有的排序都是默认从小到大排序)
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序(内存)：数据元素全部放在内存中的排序。
外部排序(磁盘)：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序运用
1.3 常见的排序算法
2. 常见排序算法的实现
2.1 插入排序
2.1.1基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想.
2.1.2 直接插入排序
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
如上看不懂,比如说:
如上有一组牌,这组牌无序,这里数组的第一个元素我们认为是有序的,因为没人和他比,所以这里我们要排序的话是从我们待排序的第二张牌开始进行比较的.这里15是第二张牌,就和前面已经有序的27进行比较.
这里吧0下标定义成27,1下标定义成i,这里再额外定义一个tmp,然后把15放到tmp里面,然后让27和15比较,如果从小到大排序,27大,27就往后走(走到15的下标1的位置),这里j走到0下标前面,然后15在试图和j下标上的元素比较,发现j下标没有元素,然后15走到0下标位置.在这个基础上i往后走到2下标,而j等于i的前一个,j走到1下标,然后再把2下标的9放到tmp里面,而前面15,27都是有序的,而27比9大,27往后走到2下标位置,然后j往前走走到0下标,而15又比9大,15往后走到1下标,j在往前走到0下标前面,发现没有元素了,此时把9往回放,到0下标位置,然后i往后走到3下标,j走到i的前一个位置,此时,后面元素比较如上同理.
如下是一半的逻辑图:
逻辑:
1.假设这组数据的第一个元素是有序的,从第二个元素开始,依次和前面的元素进行比较,找到合适的位置,就进行插入.
代码如下:
public class Sort { //直接插入排序 public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i-1; //j往回走 for (; j >= 0 ; j--) { //这里加不加等号 和稳定有关系 // 但是：本身就是一个稳定的排序 可以实现为不稳定的排序 // 但是 本身就是一个不稳定的排序 是不可能变成一个稳定的排序的 if(array[j] > tmp) { array[j+1] = array[j]; }else { //array[j+1] = tmp; break; } } array[j+1] = tmp; } } } * 时间复杂度： * 最坏情况下：O(n^2) * 最好情况下：O(n) 当数据越有序 排序越快 * 适用于：待排序序列 已经基本上趋于有序了！ * 空间复杂度： * O(1) * 稳定性： * 稳定的结果:
就是直接插入排序,比如给的是5,4,3,2,1,他每次都有回退 ,所以他的效率就会大大的降低,所以为了应对这种情况则对直接插入排序进行优化,优化完就是希尔排序,下面我们来看下:
2.1.3 希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的 了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对 比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中 给出的希尔排序的时间复杂度都不固定
数据结构(C语言版)》--- 严蔚敏
《数据结构-用面向对象方法与C++描述》--- 殷人昆
代码如下:
public class Sort { //希尔排序 public static void shellSort(int[] array) { int gap = array.length; while (gap > 1) { gap /= 2; shell(array,gap); } } /** * 对每组进行插入排序 * @param array * @param gap */ public static void shell(int[] array,int gap) { for (int i = gap; i < array.length; i++) {//这里面如果写i+gap,则只比较了红色部分,蓝色部分没有比较 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; } } }结果:
参考:
如何测很多数据(一个数组里面有很多数据该怎么测):
这里先给一个数组,大小为10000,这里我们初始化一下这个数组(initOrder是逆序有序的)
代码如下:
import java.util.Arrays; import java.util.Random; //2023.10.11(11.30) public class Text { //初始化逆序 public static void initOrder(int[] array) { for (int i = 0; i < array.length; i++) { array[i] = array.length-i;//array.length-i把数组初始化成一个逆序的情况 } } //初始化无序 public static void notOrder(int[] array) { Random random = new Random(); for (int i = 0; i < array.length; i++) { array[i] = random.nextInt(10000); } } //测试startTime所耗费的时间(直接排序) public static void testInsert(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length);//哟话之后互相不干扰 long startTime = System.currentTimeMillis(); Sort.insertSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("直接插入排序耗时："+(endTime-startTime)); } //测试startTime所耗费的时间(希尔排序) public static void testShellSort(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length); long startTime = System.currentTimeMillis(); Sort.shellSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("希尔排序耗时："+(endTime-startTime)); } public static void main(String[] args) { int[] array = new int[10_0000]; //利用initOrder和notOrder对比时间上的区别 //initOrder(array);//调用这个方法他里面都是有序的 notOrder(array);//调用这个方法他里面都是随机的 testInsert(array); testShellSort(array); }
2.2 选择排序
2.2.1基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2.2.2 直接选择排序:
1.在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素.
2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素 交换.
3.在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个 元素.
【直接选择排序的特性总结】
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
意思就是,如下第一幅图是一组待排序数据,现在要对他进行排序,逻辑是:现在有一个下标是i,一个下标是j,他的选择就是让j每次等于i+1,从后面一直走,会有一个下标minIndex,首先minIndex的值会有一个更新,minIndex里面会存一个i下标的值,比如下图是0,则mi里面会存0.然后15比27小,则minIndex里面会记录下1下标,然后j在往后走,到2下标,在让2下标里面的值和minIndex里面的值比较,这里9比15小,mi里面的1下标就替换成2下标,后面依次类推.直到走完,我们就得到了i后面最小的一个值是2下标的9,这里就让i下标的值和2下标的值交换,最后结果如下第二幅图.
完成上面步骤之后i进行加加,走到了1下标位置,j还是等于i+1,走到2下标位置,这里minIndex和上面一样,里面还是存放i所在的下标1,然后后面找到比15小的下标,记录下他的下标,让他和i交换,后面依次类推.
代码如下:
private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * 选择排序： * 时间复杂度：O(n^2) * 空间复杂度：O(1) * 稳定性：不稳定的排序 * @param array */ public static void selectSort(int[] array) { for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i+1; j < array.length; j++) { if(array[j] < array[minIndex]) { minIndex = j; } } swap(array,i,minIndex); } }结果:
参考:
代码:
public static void testSelectSort(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length); long startTime = System.currentTimeMillis(); Sort.selectSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("选择排序耗时："+(endTime-startTime)); }
选择排序的另一种方式(双向选择排序(时间复杂度没有变)):
这里有两个变量,一个是minIndex和maxIndex, 这里假设最小值和最大值都是0下标,然后在定义一个i,让27和0下标的15进行比较,此时minIndex里面的0下标还是不变,而maxIndex中的0下标则要变成1下标.i再往下走到2下标,9比0下标的值小,则minIndex的0下标要更新成2下标,而9没有27大,则maxIndex里面的1下标不变,后面以此类推.直到全部走完,这里在minIndex和maxIndex记录了最大和最小值,然后让最小的和0下标的交换,最大的和4下标交换.这一轮完成之后,让left加加,让right减减,i在等于left的下一个,minIndex和maxIndex又变成当前left的值,后面以此类推.
代码如下:
public static void selectSort2(int[] array) { int left = 0; int right = array.length-1; while (left < right) { int minIndex = left; int maxIndex = left; for (int i = left+1; i <= right ; i++) { if(array[i] < array[minIndex]) { minIndex = i; } if(array[i] > array[maxIndex]) { maxIndex = i; } } swap(array,minIndex,left); //防止 第一个是最大值 ，如果和最小的一换，最大值就跑到了原来最小值的位置 if(maxIndex == left) { maxIndex = minIndex; } swap(array,maxIndex,right); left++; right--; } }结果:
2.2.3 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
【直接选择排序的特性总结】
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
前一篇写的堆排序是自己实现的.
代码如下:
//堆排序的前提是创建大根堆 private static void createHeap(int[] array) { for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) { siftDown(array,parent,array.length);//alt+enter } } private static void siftDown(int[] array,int parent, int length) { int child = 2*parent + 1; while (child < length) { if(child+1 < length && array[child] < array[child+1]) { child++; } if(array[child] > array[parent]) { swap(array,child,parent); parent = child; child = 2*parent+1; }else { break; } } } /** * 时间复杂度：O(N*logN) * 空间复杂度：O(1) * 稳定性：不稳定的排序 * @param array */ public static void heapSort(int[] array) { createHeap(array); int end = array.length-1; while (end > 0) { swap(array,0,end); siftDown(array,0,end); end--; } }结果:
2.3 交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.3.1冒泡排序
【冒泡排序的特性总结】
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
代码:
/** * 时间复杂度：O(N^2) * 如果加了优化：最好情况下 可以达到O(n) * 空间复杂度：O(1) * 稳定性：稳定的排序 * * 优化： * 每一趟都需要判断 上一趟 有没有交换 * @param array */ public static void bubbleSort(int[] array) { //i代表的是趟数 for (int i = 0; i < array.length-1; i++) { boolean flg = false; //j来比较 每个数据的大小 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) { break; } } }
2.3.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
/**
* 快速排序-》
* 时间复杂度：
* 最好的情况下：O(N*logN)
* 最坏情况下：O(N^2) 逆序/有序
* 空间复杂度：
* 最好的情况下：O(logN)
* 最坏情况下：O(N) 逆序/有序
* 稳定性：不稳定
* @param array
*/
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
int pivot = partition(array,start,end);
quick(array,start,pivot-1);//左
quick(array,pivot+1,end);//右
}上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可 .
将区间按照基准值划分为左右两半部分的常见方式有：
1. Hoare版
https://developer.aliyun.com/article/1460788
如上链接作品中有动图解析,请参考.
如上是一组长度为10的数组,如上有一个left和right,这里要找一个基准,而这里面会以一个值作为基准.比如说,一般情况下Hoare会把左边的元素当成基准值,如上6.先让后面right往前走找到比6小的元素,如上图5,然后让left往前走找到比6大的元素,如上图7,然后让5和7交换位置.然后让right在7下标这个位置继续向前走找到比6小的元素是4,让left从3下标这个位置继续向前走走到比6大的元素9,然后让4和9交换.然后再让right从下标6的位置往前走找到比6小的元素3,left从下标4往前走找比6大的元素,结果left走了一步到下标5,此时left和right相遇了,相遇之后,让下标5上的3和下标1上的6进行交换.此时我们发现,6的左边全部比6小,6的右边全部比6大,如上第二幅图.
接下来开始递归(如上的left和right是形参),上面是形参相遇了.然后在让6的左边和右边再按照如上方式走,如上第三幅图,以0下标的3为基准.
如上第三副图走完之后,再把3的右边拿出来,继续上面的操作,如上第四幅图.直到把1单独拿出来,我们发现left和right相遇了,那证明这颗树一定是有序的,然后开始回退.左边结束了开始看右边.
这也意味着start<eed,当start>=eed的时候就可以结束了
全部代码如下:
/** * 快速排序-》 * 时间复杂度： * 最好的情况下：O(N*logN) * 最坏情况下：O(N^2) 逆序/有序 * 空间复杂度： * 最好的情况下：O(logN) * 最坏情况下：O(N) 逆序/有序 * 稳定性：不稳定 * @param array */ public static void quickSort(int[] array) { quick(array,0,array.length-1); } private static void quick(int[] array,int start,int end) { if(start >= end) { return; } int pivot = partition(array,start,end); quick(array,start,pivot-1);//左 quick(array,pivot+1,end);//右 } /** * 思考2个问题： * 1. array[right] >= tmp 等于号 * 2. 为什么从右边开始而不是从左边开始 * @param array * @param left * @param right * @return */ private static int partition(int[] array, int left, int right) { int tmp = array[left]; int i = left; while (left < right) { // 单独的循环 不能一直减到超过最左边的边界 while (left < right && array[right] >= tmp) { right--; } while (left < right && array[left] <= tmp) { left++; } swap(array,left,right); } swap(array,i,left); return left;//返回left或者right }
1.57.32
注意:快排数据少的情况下还可以,数据多了不行.
而且快排下数据一定不是逆序或者有序的,如果逆序或有序的情况下用逆序,会导致栈溢出.
如下图:
这跟递归层次有关系,递归越多,开辟的栈越多.
2. 挖坑法
https://developer.aliyun.com/article/1460788
如上链接作品中有动图解析,请参考.
就是和上面一样找基准,先把6拿出来,此时0下标空了,然后让right往前走找比6小的数据是7下标的5,然后让比6小的5移动到0下标上,此时7下标又变成空的了,然后让left往前走,找到比6大的元素是3下标的7,然后把7移动到7下标的位置.然后3下标位置空了,接着让right继续向前走遇到6下标的4,把4移动到3下标,后面依次类推,直到left和right相遇了,把6放到这个相遇的位置5下标即可.
此时的6就以挖坑法的方式花为基准了.虽然说6的左边都比6小,但是他的顺序不一样.
代码如下:
public static void quickSort(int[] array) { quick(array,0,array.length-1); } private static void quick(int[] array,int start,int end) { if(start >= end) { return; } int pivot = partition(array,start,end); quick(array,start,pivot-1);//左 quick(array,pivot+1,end);//右 } /** * 挖坑法 * @param array * @param left * @param right * @return */ private static int partitionHole(int[] array, int left, int right) { int tmp = array[left]; while (left < right) { // 单独的循环 不能一直减到超过最左边的边界 while (left < right && array[right] >= tmp) { right--; } array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } array[right] = array[left]; } array[left] = tmp; return left; }* 思考2个问题：
* 1. array[right] >= tmp 等于号 (一挖坑法为例,如果只有大于,有两个相等的会进入死循环,如下图:)
* 2. 为什么从右边开始而不是从左边开始(以Hoare为例,如果先走左边,有可能会出现相遇的是大的数据,最后把大的数据放到了最前面,此时就不会出现左边比6小,右边比6大的情况.
3. 前后指针
https://developer.aliyun.com/article/1460788
如上链接作品中有动图解析,请参考.
写法一：
private static int partition(int[] array, int left, int right) { int prev = left ; int cur = left+1; while (cur <= right) { if(array[cur] < array[left] && array[++prev] != array[cur]) { swap(array,cur,prev); } cur++; } swap(array,prev,left); return prev; }写法二：
private static int partition(int[] array, int left, int right) { int d = left + 1; int pivot = array[left]; for (int i = left + 1; i <= right; i++) { if (array[i] < pivot) { swap(array, i, d); d++; } } swap(array, d - 1, left); return d - 1; }上面两种写法一致.
上面三种方式,每次划分之后的前后顺序有可能是不一样.
上面三种方法找基准出来的顺序都不一样,如上指针法是51234,Hoare是31254,挖坑法51243.
6.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（A）
A: 34，56，25，65，86，99，72，66 B: 25，34，56，65，99，86，72，66
C: 34，56，25，65，66，99，86，72 D: 34，56，25，65，99，86，72，66这里我们怎么知道上面用上面三种那种方式呢?
挖坑法
2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较(C)次？（采用从后往前比较）
A: 3 B: 4 C: 5 D: 6
这里我们优化的出发点是减少递归的次数 ,那我们如何减少递归的次数呢?接着往下走:
2.3.2 快速排序优化
1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
什么是三数取中法呢?如下:比如说有如下一组数
比如用挖坑法,把1拿出去,让right从7位置往前走,ui直走到1位置和left相遇,我们上面说相遇的地方就是一个基准,但是这里有一个问题就是1的左边没有数,右边有,所以不能分割,那该怎么做呢?接着往下走:
这时候就有了一种方式,如下图,这里面有三个数据,一个1,一个7,还有一个中间位置4,我们记为m,这里我们在三个数据中选一个中位数4,让4作为基准,然后让他和1进行交换,换完之后把4拿出来,然后让r往前走找比4小的,然后和上面挖坑法一样交换,让l往前走找比4大的,没有找到我们发现r和l相遇了,然后我们发现4的左边全是比4小的,右边全是比4大的.然后把左边拿出来和上面一样进行递归.
(我们这里利用三树取中法,一定能降低树的高度.)
但是现在的问题是,我给你一组数据,我们怎么找l,r,还有中间数字m怎么确定?像第一幅图,就算找到了中间数字,那l,r又是什么关系呢?
我们最终想要看到的结果 :array[mid]<=array[left]<=array[right],意思就是,中间值最小,右值最大,左值剧中.现在给我们这三个数,我们怎么确定这三个数的中位数呢?比如说3,2,9,则中间数字是3.如果是3,5,9,中间数字就是5.(这里设mid为x,已知两个数的大小,第三个数加进来,那个数是中位数,跟第三个数有关系).
以下代码解决了树的高度问题,但没有解决栈溢出问题.
代码如下:
/** * 快速排序-》 * 时间复杂度： * 最好的情况下：O(N*logN) * 最坏情况下：O(N^2) 逆序/有序 * 空间复杂度： * 最好的情况下：O(logN) * 最坏情况下：O(N) 逆序/有序 * 稳定性：不稳定 * @param array */ public static void quickSort(int[] array) { quick(array,0,array.length-1); } /** * 求中位数的下标 * @param array * @param left * @param right * @return */ private static int middleNum(int[] array,int left,int right) { int mid = (left+right)/2; 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; } } } public static void insertSort(int[] array,int left,int right) { for (int i = left+1; i <= right; i++) { int tmp = array[i]; int j = i-1; for (; j >= left ; j--) { if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } private static void quick(int[] array,int start,int end) { if(start >= end) { return; } if(end - start + 1 <= 15) { //上面这个insertSort这个方法跟insertSort构成重载,这个重载指在这定位置进行插排,插排完之后走人,因为当区间越来越小的时候,数据越来越有序,而且还是个很小的区间,那排序自然就加快了 insertSort(array, start, end); return; } //1,2,3,4,5,6,7 int index=middleNum(array, start, end); swap(array, start, end); //换完:4,2,3,1,5,6,7 int pivot = partition(array,start,end); quick(array,start,pivot-1);//左 quick(array,pivot+1,end);//右 }结果:
手动把栈调大:
上面把快排递归讲完了,接下来我们看一下非递归的:
非递归会申请一个栈,还是如上这组数据,这里还是先找一个基准,还是6,把6拿出来,然后让r从后往前走,走到了7下标位置上的5比6小,然后把5放到0下标,l从前往后走,找到比6大的3下标7,把他放到7下标位置,后面以此类推,最后找完依次基准之后变成第二幅图.然后接下来把找完基准之后左边的0下标和4下标.右边的8下标和9下标放进栈,然后判断栈是否为空,不为空,弹出9,给r(r在9下标的位置),弹出6给l(l在6下标位置)(放的时候是先l后r,出来给的时候是先r后l)(10.13:43.27),在6到9下标范围之类调用一次pivot函数,又把6下标的9元素放到tmp,而9下标的8比9小,把他放到6下标位置,然后l从6下标往后走,找到比9大的数字是8下标的10,然后把10放到9下标位置,然后r从后往前走,走了一步l和r相遇了,相遇之后把9放到相遇的8下标元素,此时9的左边是6和7下标,把他们再放进战力,如图四,9的右边是10,一个数据,此时他不需要递归.所以我们想把数据往栈里面放它是有要求的,如果当前这个基准的左边或者右边只有一个元素,他是不需要把他放进栈里面的.但是这里的问题是我们怎么知道,他是不是只有一个元素,而不是两个元素呢?这里当privot+1=e,则说明有一个(比如说如上8+1=9).那怎么判断他有两个呢?假设这里有10个下标,此时pivot还在8下标位置,而pivot+1<e,则说明他有两个元素.
(pivot+1<e,说明右边有两个元素,pivot-1>s,说明左边有两个元素)
总结:
1.调用partition方法找到privot
2.左边有没有两个元素,如果有,把下标放进栈
3.右边和2一样
4.放进去之后判断栈是否为空,不空取(poll)出两个,第一个给r第二个给l,然后在进行上述1,调用partition,调用之后又有左边右边,所以这里他是一个循环(如上图),直到栈空,里面没有数对了,说明都比完了.
代码如下:
private static int partitionHole(int[] array, int left, int right) { int tmp = array[left]; while (left < right) { // 单独的循环 不能一直减到超过最左边的边界 while (left < right && array[right] >= tmp) { right--; } array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } array[right] = array[left]; } array[left] = tmp; return left; } public static void quickSortNor(int[] array) { int start = 0; int end = array.length-1; Stack<Integer> stack = new Stack<>(); int pivot = partitionHole(array,start,end); if(pivot > start+1) { stack.push(start); stack.push(pivot-1); } if(pivot+1 < end) { stack.push(pivot+1); stack.push(end); } while (!stack.isEmpty()) { end = stack.pop(); start = stack.pop(); pivot = partitionHole(array,start,end); if(pivot > start+1) { stack.push(start); stack.push(pivot-1); } if(pivot+1 < end) { stack.push(pivot+1); stack.push(end); } } }结果:
2.3.3 快速排序总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
2.4 归并排序
2.4.1 基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
https://blog.csdn.net/Hell_potato777/article/details/113698171
https://blog.csdn.net/Hell_potato777/article/details/113698171
如上作品中有动态图,请参考.
2.4.2 归并排序总结
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
归并排序的大思路是:先分解后合并
如上逻辑图,分解成10,6,7,1之后,再分解成10,6,先弄完10和6之后递归回去,再弄7,1.
(l<r说明有这棵树,l>r说明没有这棵树)
递归:
代码如下:
/** * 时间复杂度：O(N*logN) * 空间复杂度：O(logN) * 稳定性：稳定的排序 * 目前为止3个稳定的排序：直接插入排序、冒泡排序、归并排序 * @param array */ public static void mergeSort(int[] array) { mergeSortFun(array,0,array.length-1); } private static void mergeSortFun(int[] array,int start,int end) { if(start >= end) { return; } int mid = (start+end)/2; mergeSortFun(array,start,mid); mergeSortFun(array,mid+1,end); //合并 merge(array,start,mid,end); } private static void merge(int[] array, int left, int mid, int right) { int s1 = left;//可以不定义，这样写为了好理解 int e1 = mid;//可以不定义，这样写为了好理解 int s2 = mid+1; int e2 = right;//可以不定义，这样写为了好理解 //定义一个新的数组 int[] tmpArr = new int[right-left+1]; int k = 0;//tmpArr数组的下标 //同时满足 证明两个归并段 都有数据 while (s1 <= e1 && s2 <= e2) { if(array[s1] <= array[s2]) { tmpArr[k++] = array[s1++]; }else { tmpArr[k++] = array[s2++]; } } while (s1 <= e1) { tmpArr[k++] = array[s1++]; } while (s2 <= e2) { tmpArr[k++] = array[s2++]; } //把排好序的数据 拷贝回原来的数组array当中 for (int i = 0; i < tmpArr.length; i++) { array[i+left] = tmpArr[i]; } }结果;
耗时;
public static void testMergeSort(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length); long startTime = System.currentTimeMillis(); Sort.mergeSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("归并排序耗时："+(endTime-startTime)); }结果:
非递归:
非递归实现先让数据一个一个有序变成2个2个有序,再变成4个4个有序,再变成8个8个有序
(听回放:10.13:2.00)
代码如下:
private static void merge(int[] array, int left, int mid, int right) { int s1 = left;//可以不定义，这样写为了好理解 int e1 = mid;//可以不定义，这样写为了好理解 int s2 = mid+1; int e2 = right;//可以不定义，这样写为了好理解 //定义一个新的数组 int[] tmpArr = new int[right-left+1]; int k = 0;//tmpArr数组的下标 //同时满足 证明两个归并段 都有数据 while (s1 <= e1 && s2 <= e2) { if(array[s1] <= array[s2]) { tmpArr[k++] = array[s1++]; }else { tmpArr[k++] = array[s2++]; } } while (s1 <= e1) { tmpArr[k++] = array[s1++]; } while (s2 <= e2) { tmpArr[k++] = array[s2++]; } //把排好序的数据 拷贝回原来的数组array当中 for (int i = 0; i < tmpArr.length; i++) { array[i+left] = tmpArr[i]; } } /** * 非递归实现归并排序 * @param array */ public static void mergeSortNor(int[] array) { int gap = 1;//每组几个数据 while (gap < array.length) { for (int i = 0; i < array.length; i = i+gap*2) { int left = i; int mid = left+gap-1;//可能会越界 int right = mid+gap;//可能会越界 if(mid >= array.length) { mid = array.length-1; } if(right >= array.length) { right = array.length-1; } merge(array,left,mid,right); } gap*=2; } }上面把7个排序全部看完了.
2.4.3 海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
(10.13:2.16.29)
3. 排序算法复杂度及稳定性分析
所有代码:
import java.util.Stack; public class Sort { //希尔排序 public static void shellSort(int[] array) { int gap = array.length; while (gap > 1) { gap /= 2; shell(array,gap); } } /** * 对每组进行插入排序 * @param array * @param gap */ public static void shell(int[] array,int gap) { for (int i = gap; i < array.length; i++) {//这里面如果写i+gap,则只比较了红色部分,蓝色部分没有比较 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; } } //直接插入排序 public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i-1; //j往回走 for (; j >= 0 ; j--) { //这里加不加等号 和稳定有关系 // 但是：本身就是一个稳定的排序 可以实现为不稳定的排序 // 但是 本身就是一个不稳定的排序 是不可能变成一个稳定的排序的 if(array[j] > tmp) { array[j+1] = array[j]; }else { //array[j+1] = tmp; break; } } array[j+1] = tmp; } } private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * 选择排序： * 时间复杂度：O(n^2) * 空间复杂度：O(1) * 稳定性：不稳定的排序 * @param array */ public static void selectSort(int[] array) { for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i+1; j < array.length; j++) { if(array[j] < array[minIndex]) { minIndex = j; } } swap(array,i,minIndex); } } public static void selectSort2(int[] array) { int left = 0; int right = array.length-1; while (left < right) { int minIndex = left; int maxIndex = left; for (int i = left+1; i <= right ; i++) { if(array[i] < array[minIndex]) { minIndex = i; } if(array[i] > array[maxIndex]) { maxIndex = i; } } swap(array,minIndex,left); //防止 第一个是最大值 ，如果和最小的一换，最大值就跑到了原来最小值的位置 if(maxIndex == left) { maxIndex = minIndex; } swap(array,maxIndex,right); left++; right--; } } //堆排序的前提是创建大根堆 private static void createHeap(int[] array) { for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) { siftDown(array,parent,array.length);//alt+enter } } private static void siftDown(int[] array,int parent, int length) { int child = 2*parent + 1; while (child < length) { if(child+1 < length && array[child] < array[child+1]) { child++; } if(array[child] > array[parent]) { swap(array,child,parent); parent = child; child = 2*parent+1; }else { break; } } } /** * 时间复杂度：O(N*logN) * 空间复杂度：O(1) * 稳定性：不稳定的排序 * @param array */ public static void heapSort(int[] array) { createHeap(array); int end = array.length-1; while (end > 0) { swap(array,0,end); siftDown(array,0,end); end--; } } /** * 时间复杂度：O(N^2) * 如果加了优化：最好情况下 可以达到O(n) * 空间复杂度：O(1) * 稳定性：稳定的排序 * * 优化： * 每一趟都需要判断 上一趟 有没有交换 * @param array */ public static void bubbleSort(int[] array) { //i代表的是趟数 for (int i = 0; i < array.length-1; i++) { boolean flg = false; //j来比较 每个数据的大小 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) { break; } } } /** * 快速排序-》 * 时间复杂度： * 最好的情况下：O(N*logN) * 最坏情况下：O(N^2) 逆序/有序 * 空间复杂度： * 最好的情况下：O(logN) * 最坏情况下：O(N) 逆序/有序 * 稳定性：不稳定 * @param array */ public static void quickSort(int[] array) { quick(array,0,array.length-1); } /** * 求中位数的下标 * @param array * @param left * @param right * @return */ private static int middleNum(int[] array,int left,int right) { int mid = (left+right)/2; 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; } } } public static void insertSort(int[] array,int left,int right) { for (int i = left+1; i <= right; i++) { int tmp = array[i]; int j = i-1; for (; j >= left ; j--) { if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } private static void quick(int[] array,int start,int end) { if(start >= end) { return; } if(end - start + 1 <= 15) { insertSort(array, start, end); return; } //1,2,3,4,5,6,7 int index=middleNum(array, start, end); swap(array, start, end); //换完:4,2,3,1,5,6,7 int pivot = partition(array,start,end); quick(array,start,pivot-1);//左 quick(array,pivot+1,end);//右 } /** * 思考2个问题： * 1. array[right] >= tmp 等于号 * 2. 为什么从右边开始而不是从左边开始 * @param array * @param left * @param right * @return */ private static int partition(int[] array, int left, int right) { int tmp = array[left]; int i = left; while (left < right) { // 单独的循环 不能一直减到超过最左边的边界 while (left < right && array[right] >= tmp) { right--; } while (left < right && array[left] <= tmp) { left++; } swap(array,left,right); } swap(array,i,left); return left; } /** * 挖坑法 * @param array * @param left * @param right * @return */ private static int partitionHole(int[] array, int left, int right) { int tmp = array[left]; while (left < right) { // 单独的循环 不能一直减到超过最左边的边界 while (left < right && array[right] >= tmp) { right--; } array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } array[right] = array[left]; } array[left] = tmp; return left; } /** * 前后指针法： * 总结： * 1. Hoare * 2. 挖坑法 * 3. 前后指针法 * 这3种方式 每次划分之后的前后顺序 有可能是不一样的 * @param array * @param left * @param right * @return */ private static int partition1(int[] array, int left, int right) { int prev = left ; int cur = left+1; while (cur <= right) { if(array[cur] < array[left] && array[++prev] != array[cur]) { swap(array,cur,prev); } cur++; } swap(array,prev,left); return prev; } public static void quickSortNor(int[] array) { int start = 0; int end = array.length-1; Stack<Integer> stack = new Stack<>(); int pivot = partitionHole(array,start,end); if(pivot > start+1) { stack.push(start); stack.push(pivot-1); } if(pivot+1 < end) { stack.push(pivot+1); stack.push(end); } while (!stack.isEmpty()) { end = stack.pop(); start = stack.pop(); pivot = partitionHole(array,start,end); if(pivot > start+1) { stack.push(start); stack.push(pivot-1); } if(pivot+1 < end) { stack.push(pivot+1); stack.push(end); } } } /** * 时间复杂度：O(N*logN) * 空间复杂度：O(logN) * 稳定性：稳定的排序 * 目前为止3个稳定的排序：直接插入排序、冒泡排序、归并排序 * @param array */ public static void mergeSort(int[] array) { mergeSortFun(array,0,array.length-1); } private static void mergeSortFun(int[] array,int start,int end) { if(start >= end) { return; } int mid = (start+end)/2; mergeSortFun(array,start,mid); mergeSortFun(array,mid+1,end); //合并 merge(array,start,mid,end); } private static void merge(int[] array, int left, int mid, int right) { int s1 = left;//可以不定义，这样写为了好理解 int e1 = mid;//可以不定义，这样写为了好理解 int s2 = mid+1; int e2 = right;//可以不定义，这样写为了好理解 //定义一个新的数组 int[] tmpArr = new int[right-left+1]; int k = 0;//tmpArr数组的下标 //同时满足 证明两个归并段 都有数据 while (s1 <= e1 && s2 <= e2) { if(array[s1] <= array[s2]) { tmpArr[k++] = array[s1++]; }else { tmpArr[k++] = array[s2++]; } } while (s1 <= e1) { tmpArr[k++] = array[s1++]; } while (s2 <= e2) { tmpArr[k++] = array[s2++]; } //把排好序的数据 拷贝回原来的数组array当中 for (int i = 0; i < tmpArr.length; i++) { array[i+left] = tmpArr[i]; } } /** * 非递归实现归并排序 * @param array */ public static void mergeSortNor(int[] array) { int gap = 1;//每组几个数据 while (gap < array.length) { for (int i = 0; i < array.length; i = i+gap*2) { int left = i; int mid = left+gap-1;//可能会越界 int right = mid+gap;//可能会越界 if(mid >= array.length) { mid = array.length-1; } if(right >= array.length) { right = array.length-1; } merge(array,left,mid,right); } gap*=2; } } }测试:
import java.util.Arrays; import java.util.Random; //2023.10.11(11.30) public class Text { //初始化逆序 public static void initOrder(int[] array) { for (int i = 0; i < array.length; i++) { array[i] = array.length-i;//array.length-i把数组初始化成一个逆序的情况 } } //初始化无序 public static void notOrder(int[] array) { Random random = new Random(); for (int i = 0; i < array.length; i++) { array[i] = random.nextInt(10000); } } //测试startTime所耗费的时间(直接排序) public static void testInsert(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length);//哟话之后互相不干扰 long startTime = System.currentTimeMillis(); Sort.insertSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("直接插入排序耗时："+(endTime-startTime)); } //测试startTime所耗费的时间(希尔排序) public static void testShellSort(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length); long startTime = System.currentTimeMillis(); Sort.shellSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("希尔排序耗时："+(endTime-startTime)); } public static void testSelectSort(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length); long startTime = System.currentTimeMillis(); Sort.selectSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("选择排序耗时："+(endTime-startTime)); } public static void testQuickSort(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length); long startTime = System.currentTimeMillis(); Sort.quickSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("快速排序耗时："+(endTime-startTime)); } public static void testMergeSort(int[] array) { int[] tmpArray = Arrays.copyOf(array,array.length); long startTime = System.currentTimeMillis(); Sort.mergeSort(tmpArray); long endTime = System.currentTimeMillis(); System.out.println("归并排序耗时："+(endTime-startTime)); } public static void main(String[] args) { int[] array = new int[10_0000]; //利用initOrder和notOrder对比时间上的区别 //initOrder(array);//调用这个方法他里面都是有序的 notOrder(array);//调用这个方法他里面都是随机的 //testInsert(array); //testShellSort(array); testSelectSort(array); testQuickSort(array); testMergeSort(array); } public static void main1(String[] args) { int[] array = {100,1,3,15,61,17,8}; //Sort.insertSort(array); //Sort.shellSort(array); // Sort.selectSort2(array); //Sort.heapSort(array); // Sort.quickSortNor(array); Sort.mergeSort(array); System.out.println(Arrays.toString(array)); } }
4. 其他非基于比较排序（了解）
(10.13:2.37.24)
练习题:
1. 快速排序算法是基于()的一个排序算法。
A：分治法 B：贪心法 C：递归法 D：动态规划法
2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入
位置需比较()次？（采用从后往前比较）
A: 3 B: 4 C: 5 D: 6
3.以下排序方式中占用O(n)辅助存储空间的是()
A: 简单排序 B: 快速排序 C: 堆排序 D: 归并排序
4.下列排序算法中稳定且时间复杂度为O(n^2)的是()
A: 快速排序 B: 冒泡排序 C: 直接选择排序 D: 归并排序
5.关于排序，下面说法不正确的是()
A: 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B: 归并排序是一种稳定的排序,堆排序和快排均不稳定
C: 序列基本有序时，快排退化成 "冒泡排序"，直接插入排序最快
D: 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
6.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（）
A: 34，56，25，65，86，99，72，66 B: 25，34，56，65，99，86，72，66
C: 34，56，25，65，66，99，86，72 D: 34，56，25，65，99，86，72，66
1.A 2.C 3.D 4.B 5.D 6.A
(10.15:14.59)