数据结构（Java实现）-排序

---

排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

---

插入排序
基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

一个本身就稳定的排序 可以实现为不稳定
但是一个本身就不稳定的排序 不可能实现为稳定的排序

---

希尔排序( 缩小增量排序 )
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。我们就记为n^1.3
4. 稳定性：不稳定

---

选择排序
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

---

选择排序的第二种写法

有两个疑点
1.

2.当left等于right时，说明当前下标的左边已经排号，当前下标的右边也已经排好，那么当前下标的值一定是中间值

【直接选择排序的特性总结】

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

---

堆排序
它是通过堆来进行选择数据。

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

---

冒泡排序

---

快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

---

Hoare版

---

挖坑法

---

快速排序优化：

三数取中法选key，目的：将待排序数组分开，不要只有左边或者只有右边

---

递归到小的子区间时，可以考虑使用插入排序。因为这时的区间元素已经趋近于有序

---

快速排序非递归形式
采用栈

---

快速排序总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

---

归并排序
基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

---

非递归形式实现归并排序

---

归并排序总结

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

---

海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程（磁盘IO读写），最终结果就有序了

---

排序算法复杂度及稳定性分析

---

其他非基于比较排序
计数排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
   

---

基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

---

桶排序

---

上述涉及的所有代码
Sort.java

import java.util.Arrays;
import java.util.Stack;/*** Created with IntelliJ IDEA.* Description:* User: Home-pc* Date: 2023-08-26* Time: 12:04*/
public class Sort {@Overridepublic String toString() {return "Sort{}";}public static void insertSort(int[] array ){for (int i =1; i < array.length; i++) {int temp=array[i];//记录当前的元素，准备随时插入，同时放置元素被覆盖掉int j=i-1;for (; j>=0; j--) {if(array[j]>temp){//当前j下标的元素后移array[j+1]=array[j];}else{break;}}array[j+1]=temp;//没有j下标的元素大，插入它的后面}}//public  static  void shell(int[] array,int gap){for (int i =gap; i < array.length; i++) {//这里的i++，可以针对每一个分组int temp=array[i];//记录当前的元素，准备随时插入，同时放置元素被覆盖掉int j=i-gap;for (; j>=0; j-=gap) {if(array[j]>temp){//当前j下标的元素后移array[j+gap]=array[j];}else{break;}}array[j+gap]=temp;//没有j下标的元素大，插入它的后面}}public static void shellSort(int[] array){int gap=array.length;while(gap>1){gap/=2;shell(array,gap);//这里在最后一定会进行一次gap=1的插入排序}}//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);}}private static void swap(int[] array,int i,int j){int temp=array[i];array[i]=array[j];array[j]=temp;}//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(left==maxIndex){maxIndex=minIndex;}swap(array,maxIndex,right);left++;right--;}}//public static void heapSort(int[] array){createBigHeap(array);int end= array.length-1;while(end>0){swap(array,end,0);shiftDown(array,0,end);end--;}}private static void createBigHeap(int[] array){for (int i = (array.length-1-1)/2; i>=0; i--) {shiftDown(array,i, array.length);}}private static void shiftDown(int[] array,int parent,int len){int child=parent*2+1;while(child<len){if(child+1<len && array[child]<array[child+1]){child=child+1;}if(array[child]>array[parent]){swap(array,child,parent);parent=child;child=parent*2+1;}else{break;}}}//public  static  void bubbleSort(int[] arrary){for (int i = 0; i < arrary.length-1; i++) {boolean flag=false;for (int j = 0; j < arrary.length-1-i; j++) {if(arrary[j]>arrary[j+1]){swap(arrary,j,j+1);flag=true;}}if(!flag){break;}}}//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;}//直接插入排序优化if(end-start+1<=10){insertSortForQuick(array,start,end);return;}//三数取中优化int mid=threeNum(array,start,end);swap(array,mid,start);int pivot=parttion(array,start,end);//求出基准值，依次为中间值划分序列quick(array,start,pivot-1);//左数quick(array,pivot+1,end);//右数}public static void insertSortForQuick(int[] array,int left,int right ){for (int i =left+1; i <=right; i++) {int temp=array[i];//记录当前的元素，准备随时插入，同时放置元素被覆盖掉int j=i-1;for (; j>=left; j--) {if(array[j]>temp){//当前j下标的元素后移array[j+1]=array[j];}else{break;}}array[j+1]=temp;//没有j下标的元素大，插入它的后面}}private static int parttion1(int[] array,int left,int right){int i=left;int temp=array[left];//拿这个值和其它元素比较while(left<right){while(left<right && array[right]>=temp){//找到右边第一个比temp小的值right--;}while(left<right && array[left]<=temp){//找到左边第一个比temp大的值left++;}swap(array,left,right);//交换这两个值}swap(array,left,i);//交换某个中间值和temp的值，使得temp为真正的中间值return left;//返回这个中间位置的下标}//private static int parttion(int[] array,int left,int right){int temp=array[left];while(left<right){while(left<right && array[right]>=temp){right--;}array[left]=array[right];while(left<right && array[left]<=temp){left++;}array[right]=array[left];}array[right]=temp;return left;}//优化：三数取中private static int threeNum(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{if(array[mid]<array[right]){return right;}else if(array[mid]>array[left]){return  left;}else{return mid;}}}//非递归实现public static void quickSortByStack(int[] array){Stack<Integer> stack=new Stack<>();stack.push(array.length-1);//这里先push的右边，后push的左边stack.push(0);while(!stack.empty()){int left=stack.pop();int right=stack.pop();if(left>=right){//成立，说明该区间排序结束continue;}int index=parttion(array,left,right);stack.push(right);stack.push(index+1);stack.push(index-1);stack.push(left);}}//归并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;while(s1<=e1&&s2<=e2){//if(array[s1]<=array[s2]){//将s1放入数组中tmpArr[k++]=array[s1++];}else{tmpArr[k++]=array[s2++];}}while(s1<=e1){tmpArr[k++]=array[s1++];}while(s2<=e2){tmpArr[k++]=array[s2++];}for (int i = 0; i <k; i++) {array[i+left]=tmpArr[i];//tmpArr数组的首元素的下标不一定为0，但一定为left}}private static void mergeSortFunc(int[] array,int left,int right){if(left>=right){//最小拆分组的数量为1return;}int mid=(left+right)/2;mergeSortFunc(array,left,mid);mergeSortFunc(array,mid+1,right);//递归拆分至最小组，准备排序后合并merge(array,left,mid,right);}public static void mergeSort1(int[] array){mergeSortFunc(array,0,array.length-1);}//非递归归并public static void mergeSort(int[] array){int gap=1;while(gap<array.length){for (int i = 0; i <array.length; i+=gap*2) {int left=i;int mid=left+gap-1;int right=mid+gap;//mid和right可能越界，这里我们将其归置到一个数组中if(mid>=array.length){mid=array.length-1;}if(right>=array.length){right=array.length-1;}merge(array,left,mid,right);}gap*=2;}}//计数排序public static void countArray(int[] array){int maxVal=array[0];int minVal=array[0];for (int i = 0; i <array.length; i++) {//找到数组里的最大值和最小值if(array[i]<minVal){minVal=array[i];}if(array[i]>maxVal){maxVal=array[i];}}//建立一个计数的数组int range=maxVal-minVal+1;int[] count=new int[range];//遍历数组，做计数统计for (int i = 0; i <array.length; i++) {int val=array[i];count[val-minVal]++;}//遍历计数数组，并重写array数组的元素int index=0;for (int i = 0; i < count.length; i++) {int val=count[i];while(val!=0){array[index++]=i+minVal;val--;}}}
}

测试代码

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;import java.util.Arrays;
import java.util.Random;/*** Created with IntelliJ IDEA.* Description:* User: Home-pc* Date: 2023-08-26* Time: 13:48*/
public class TestSort {public static void notOrderArray(int[] array){Random random=new Random();for (int i = 0; i < array.length; i++) {array[i]=random.nextInt(100);}}public static void testShellSort(int[] array){array=Arrays.copyOf(array,array.length);Sort.shellSort(array);System.out.println(Arrays.toString(array));}public static void testSelectSort(int[] array){array=Arrays.copyOf(array,array.length);Sort.selectSort(array);System.out.println(Arrays.toString(array));}public static void testSelectSort2(int[] array){array=Arrays.copyOf(array,array.length);Sort.selectSort2(array);System.out.println(Arrays.toString(array));}public static void testheapSort(int[] array){array=Arrays.copyOf(array,array.length);Sort.heapSort(array);System.out.println(Arrays.toString(array));}public static void testbubbleSort(int[] array){array=Arrays.copyOf(array,array.length);Sort.bubbleSort(array);System.out.println(Arrays.toString(array));}public static void testquickSort(int[] array){array=Arrays.copyOf(array,array.length);//long startTime=System.currentTimeMillis();Sort.quickSort(array);//long endTime=System.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println("优化后排序时间"+(endTime-startTime));}public static void testquickSortByStack(int[] array){array=Arrays.copyOf(array,array.length);//long startTime=System.currentTimeMillis();Sort.quickSortByStack(array);//long endTime=System.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println("优化后排序时间"+(endTime-startTime));}public static void testmergeSort(int[] array){array=Arrays.copyOf(array,array.length);//long startTime=System.currentTimeMillis();Sort.mergeSort(array);//long endTime=System.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println("优化后排序时间"+(endTime-startTime));}public static void testcountArray(int[] array){array=Arrays.copyOf(array,array.length);//long startTime=System.currentTimeMillis();Sort.countArray(array);//long endTime=System.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println("优化后排序时间"+(endTime-startTime));}public static void main(String[] args) {int[] array=new int[30];notOrderArray(array);System.out.println(Arrays.toString(array));testShellSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testSelectSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testSelectSort2(array);notOrderArray(array);System.out.println(Arrays.toString(array));testheapSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testbubbleSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testquickSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testquickSortByStack(array);System.out.println("我是分割线");notOrderArray(array);System.out.println(Arrays.toString(array));testmergeSort(array);System.out.println("我是分割线");notOrderArray(array);System.out.println(Arrays.toString(array));testcountArray(array);}
}
***

---

---

---

---