七大基于比较的排序方法 1.插入排序：直接插入排序；希尔排序
2.选择排序：选择排序；堆排序
3.交换排序：冒泡排序；快速排序
4.归并排序：归并排序
这是关于以上排序方法的时间复杂度，空间复杂度，稳定性的总结：
以下为代码实现冒泡排序，插入排序，选择排序，堆排序，希尔排序，测试用例从完全有序，逆序，随机产生，完全相等四个方面测试过了，没有问题，有需要的可以参考参考~
import java.util.Arrays; import java.util.Random; public class Main { //冒泡排序 //时间复杂度：最好：O（n）最坏：O（n^2) //空间复杂度:O(1) //稳定性：稳定 //[无序][有序] public static void bubbleSort(long[] array){ for(int i=0;i<array.length-1;i++){ boolean flag=true; for(int j=0;j<array.length-i-1;j++){ if(array[j]>array[j+1]){ swap(array,j,j+1); flag=false; } } if(flag){ break; } } } private static void swap(long[] array,int i,int j){ long t=array[i]; array[i]=array[j]; array[j]=t; } //插入排序 //时间复杂度：O(n^2) //空间复杂度:O(1) //稳定性:稳定 public static void insertSort(long[] array){ for(int i=0;i<array.length-1;i++){ long key=array[i+1]; int j; for( j=i;j>=0;j++){ if(key<array[j]){ array[j+1]=array[j]; }else{ break; } } array[j+1]=key; } } //选择排序 //时间复杂度： //空间复杂度： //稳定性：不稳定 public static void selectSort(long[] array){ for(int i=0;i<array.length-1;i++){ int maxIndex=0; for(int j=1;j<array.length-i;j++){ if(array[j]>array[maxIndex]){ maxIndex=j; } } swap(array,maxIndex,array.length-i-1); } } //堆排序 //时间复杂度：O（nlog(n)) //空间复杂度:O(1) //稳定性:不稳定 public static void heapSort(long[] array){ //建大堆 升序 createHeap(array,array.length); for(int i=0;i<array.length+1;i++){ swap(array,0,array.length-i-1); adjustDown(array,array.length-i-1,0); } } public static void createHeap(long[] array,int size){ for(int i=(size-2)/2;i>=0;i++){ adjustDown(array,size,i); } } private static void adjustDown(long[] array,int size,int index){ while(2*index+1<size){ int maxIndex=2*index+1; if(maxIndex+1<size&&array[maxIndex]<array[maxIndex+1]){ maxIndex++; } if(array[index]>=array[maxIndex]){ break; } swap(array,maxIndex,index); index=maxIndex; } } //希尔排序 //时间复杂度：O(n） O(n^2) //空间复杂度：O(1) //稳定性：不稳定 public static void shellSort(long[] array){ int gap=array.length/2; while(true){ insertSortGap(array,gap); if(gap==1){ break; } gap/=2; } } private static void insertSortGap(long[] array,int gap){ for(int i=gap;i<array.length;i++){ long key=array[i]; int j; for(j=i-gap;j>=0;j=j-gap){ if(key<array[j]){ array[j+1]=array[j]; }else{ break; } } } }谢谢各位小可爱的观看~ 一起加油，一起学习everyday~
