| 本章讲述数据结构中的六大排序算法 欢迎大佬们踊跃讨论，感谢大家支持！ 我的博客主页链接  |
六大排序算法
一.插入排序1.1 直接插入排序1.2 希尔排序 二.选择排序2.1 单向选择排序2.2双向选择排序2.3 堆排序 三.交换排序3.1 冒泡排序3.2 快速排序3.2.1 Hoare排序3.2.2 挖坑法3.2.3 前后指针法3.4 非递归快速排序 四.归并排序4.1 递归归并排序4.2非递归归并排序 五.计数排序六.测试运行时间代码
一.插入排序
1.1 直接插入排序
1.已知第一个元素如果不包含其他元素，没有元素可以比较，为有序。
2.我们可以直接从第二个元素i开始，创建一个对象tmp来接下标元素，如果比前一个元素小，前一个元素往后移动，tmp插入i-1下标
3.当元素大于或者等于时，则tmp直接放在i位置即可。
public static void insertSort(int[] array){ for(int i=1;i<array.length;i++){//由数组1下标开始进行比较 int tmp=array[i]; int j=i-1; for(;j>=0;j--){ if(tmp<array[j]){ array[j+1]=array[j];//将j放入j+1位置 }else{ //进入else则为有序，break跳出嵌套循环 break; } } //当嵌套的for循环一直在比较最小值tmp，知道为-1跳出循环，这里需要j+1 //当大于时候，因为i-1赋值给j，break跳出后j需要+1下标值得到tmp array[j+1]=tmp; } }时间复杂度:最坏情况时间复杂度为O(N*N)
最好情况时间复杂度为O(N)
空间复杂度O(1)
稳定排序
1.2 希尔排序
希尔排序又称缩小增量法。
希尔排序的思想，定义一个整数，将待排序数组元素长度分成多个组，每一个组进行插入排序，重复上述分组，此时为预排序。当到达1时，将所有记录好的元素在一组中进行排序。
每一次分组排序后都变为有序，每组数据由少变多，越来越有序。
划分为n/2组进行比较，根据n/2的距离来划分每一组的数量。
public static void shellSort(int[] array){ int gap=array.length; while(gap>1){ gap/=2;//将数组/2，有多组变少组直到为1 shell(array,gap); } } public static void shell(int[] arr,int gap){ //从gap开始遍历 for(int i=gap;i<arr.length;i++){ //获取gap下标的值 int tmp=arr[i]; 求i-gap个差距得到j值 int j=i-gap; for(;j>=0;j-=gap){ if(tmp<arr[j]){ arr[j+gap]=arr[j]; }else{ break; } } arr[j+gap]=tmp; } }时间复杂度O(N^1.25)
空间复杂度O(1)
二.选择排序
2.1 单向选择排序
单向选择排序通过定义minIndex值来获取最小的元素下标，然后与0下标进行交换
public static void selectSort2(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,minIndex,i); } }2.2双向选择排序
双向选择排序是我们通过定义起始位置和终点位置的下标作为条件，通过初始位置筛选最大值和最小值的下标，将最大值下标与尾部交换，最小值下标与初始位置交换，然后继续重复上述，知道筛选完成。
这里如果max的最大值为0下标的时候，max已经被 minIndex交换，maxIndex等于minIndex获取最大元素的下标值即可。
public static void selectSort(int[] array){ //起始位置和末尾的下标值 int left=0; int right=array.length-1; while(left<right){ //都从0下标开始比较 int maxIndex=left; int minIndex=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,left,minIndex); //如果0下标就是maxIndex的最大值，minIndex的位置就是maxIndex的最大值 if(maxIndex==left)maxIndex=minIndex; swap(array,right,maxIndex); left++; right--; } } 时间复杂度：O(N^2)
空间复杂度：O(1)
2.3 堆排序
堆序详情堆排序
//创建二叉堆 public static void createHeap(int[] array){ for(int parent=(array.length-1-1)/2;parent>=0;parent--){ siftDown(array,parent,array.length); } } private static void siftDown(int[] array,int parent,int size) { int child=2*parent+1; while(child<size){ if(child+1<size&&array[child]<array[child+1]){ //child是左右孩子的最大值 child=child+1; } if(array[child]>array[parent]){ //交换孩子与父亲 swap(array,child,parent); //调整父亲节点和孩子节点 parent=child; child=(2*parent)+1; }else{ break; } } } //根据创建好的大跟堆，通过最后一个下标与0下标交换后缩小堆的范围，直到称为有序数组 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*logN)
空间复杂度O(1)
三.交换排序
3.1 冒泡排序
冒泡排序是一种较为简单的排序算法，它循环需要排序的元素，依次比较相邻的两个元素，如果顺序错误就进行交换，直至没有元素交换，完成排序，若对数组n个元素进行比较，则需要比较n-1次，最后一个元素已经被前n-1个元素排序好。
排序一次将len-1最大值放到最后，直到有序
本代码中的flag来记录是否有序，如果有序，则直接跳出循环。
public static void bubbleSort(int[] array){ for(int i=0;i<array.length-1;i++){ boolean flag=false;//这里标记一下，每一趟中，给flag置为false，当每趟为有序后，则不进入if语句直接停止循环 for(int j=0;j<array.length-1-i;j++){ if(array[j]>array[j+1]){ swap(array,j,j+1); flag=true; } } if(!flag){ break; } } }时间复杂度：最好情况下：O(n)
最坏情况下：O(n^2)
空间复杂度:O(1)
稳定排序
3.2 快速排序
3.2.1 Hoare排序
1.首先设定一个分界值，通过该分界值将数组分成左右两部分。
2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
这里定义一个left为左，right为右，将任意左右位置两边定义一个基准值，根据基准值的大小，直到left为大于基准值数，right为小于基准值数停下，若定义左边为基准值则右边先走，同理右边为基准值左边先走。
//快速排序 public static void quickSort(int[] array){ //记录左起始位置和右边的结束位置进行递归 quick(array,0,array.length-1); }public static void inSert(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 int middleNum(int[] array, int left, int right) { int mid=(left+right)/2; if(array[left]>array[right]){ //说明left大 if(array[right]>array[mid]){ return right; } else if (array[left]<array[mid]) { return left; }else{ return mid; } }else{ //right大判断中间值 if(array[left]>array[mid]){ return left; }else if(array[right]<array[mid]){ return right; }else{ return mid; } } } private static void quick(int[] array, int left, int right) { if(left>=right)return ;//说明两个相遇或者走出范围 //当长度少时直接插入排序 if(right-left+1<=10){ inSert(array,left,right); return ; } int index = middleNum(array,left,right); System.out.println("index下标值:"+index); //用来交换left和right范围内元素且最终将首位元素与相遇值交换 swap(array,left,index); int pos=partitionPointer(array,left,right);//递归 quick(array,left,pos-1); quick(array,pos+1,right); } private static int partitionHoare(int[] array, int left, int right) { int record=left;//记录left最后交换 int tmp=array[left];//比较大小 while(left<right){ while(left<right&&array[right]>=tmp){//右边找到小于tmp right--; } while(left<right&&array[left]<=tmp){//左边找到大于tmp left++; } swap(array,left,right); } //这里left与right相遇 swap(array,record,left); return left; }时间复杂度：最坏情况下N*(logN)
最好情况下：O(N^2) 有序或者逆序情况下
空间复杂度:最好情况下O(logN)
最坏情况下：O(N) 有序或者逆序情况下
数据多时因递归可能容易栈溢出
3.2.2 挖坑法
1.由左或者右选出第一个坑位记录元素值，放入key中，创建left和right对数组遍历，当选左坑右走，右坑左走，直到right和left相遇后将记录的坑位元素值放入即可。
public static void quickSort(int[] array){ //记录左起始位置和右边的结束位置进行递归 quick(array,0,array.length-1); } public static void inSert(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 int middleNum(int[] array, int left, int right) { int mid=(left+right)/2; if(array[left]>array[right]){ //说明left大 if(array[right]>array[mid]){ return right; } else if (array[left]<array[mid]) { return left; }else{ return mid; } }else{ //right大判断中间值 if(array[left]>array[mid]){ return left; }else if(array[right]<array[mid]){ return right; }else{ return mid; } } } private static void quick(int[] array, int left, int right) { if(left>=right)return ;//说明两个相遇或者走出范围 if(right-left+1<=10){ inSert(array,left,right); return ; } int index = middleNum(array,left,right); System.out.println("index下标值:"+index); //用来交换left和right范围内元素且最终将首位元素与相遇值交换 swap(array,left,index); int pos=partitionPointer(array,left,right);//递归 quick(array,left,pos-1); quick(array,pos+1,right); } private static int partitionPit(int[] array, int left, int right) { int record=array[left];//记录起始坑位 while(left<right){ while(left<right&&array[right]>=record){//右边找到小于tmp right--; } //说明找到小于tmp的值 array[left]=array[right]; while(left<right&&array[left]<=record){//左边找到大于tmp left++; } //说明找到大于tmp的值 array[right]=array[left]; } //这里left与right相遇后将记录的首个坑填入 array[left]=record; return left; }3.2.3 前后指针法
cur指向起始位置+1，pre是cur的前一位
判断条件：如果cur找到基准值（最初位置key为5），前一项的条件满足后prev向后走不为cur（为cur则不交换），直到prev在前cur在后且cur<基准值
cur如果大于基准值，直到cur找到小于基准值的数或者走完，直到递归调整为升序。
public static void quickSort(int[] array){ //记录左起始位置和右边的结束位置进行递归 quick(array,0,array.length-1); }public static void inSert(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 int middleNum(int[] array, int left, int right) { int mid=(left+right)/2; if(array[left]>array[right]){ //说明left大 if(array[right]>array[mid]){ return right; } else if (array[left]<array[mid]) { return left; }else{ return mid; } }else{ //right大判断中间值 if(array[left]>array[mid]){ return left; }else if(array[right]<array[mid]){ return right; }else{ return mid; } } } private static void quick(int[] array, int left, int right) { if(left>=right)return ;//说明两个相遇或者走出范围 if(right-left+1<=10){ inSert(array,left,right); return ; } int index = middleNum(array,left,right); System.out.println("index下标值:"+index); //用来交换left和right范围内元素且最终将首位元素与相遇值交换 swap(array,left,index); int pos=partitionPointer(array,left,right);//递归 quick(array,left,pos-1); quick(array,pos+1,right); } private static int partitionPointer(int[] array, int left, int right) { //记录cur的前一项 int Prev=left; int cur=left+1; while(cur<=right){ //cur与起始位置比较只有小于才能进行交换且prev不为cur if(array[cur]<array[left]&&array[++Prev]!=array[cur]){ swap(array,cur,Prev); } cur++; } //交换最后记录的cur的值 swap(array,left,Prev); return Prev; }3.4 非递归快速排序
这里非递归排序的情况下，因为每次最左边的数我们需要申请一个栈来记录其区间值，出栈由区间值一步步缩小取值的范围并进行交换，重复上述即可。
public static void quickNor(int[] array){ quickSortNor(array,0,array.length-1); } private static void quickSortNor(int[] array, int left, int right) { Stack<Integer> stack=new Stack<>(); int pivot=partitionHoare(array,left,right); if(pivot>left+1){ 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=partitionHoare(array,left,right); if(pivot>left+1){ stack.push(left); stack.push(pivot-1); } if(pivot+1<right){ stack.push(pivot+1); stack.push(right); } }四.归并排序
4.1 递归归并排序
定义一个分界线mid来获取其中间值，递归左边和右边，每次进入方法进行排序
将左起始到中间值与中间值到右侧比较，创建一个数组来记录，排序后放到数组中，最后让原数组接收。
public static void mergeSort(int[] array){ mergeSortM(array,0,array.length-1); } private static void mergeSortM(int[] array, int left, int right) { //知道left和right相遇返回 if(left>=right)return ; int mid=(left+right)/2; //以中间值作为分区，递归左边和右边 mergeSortM(array,left,mid); mergeSortM(array,mid+1,right); //每次递归传入后进行排序 merge(array,left,mid,right); } private static void merge(int[] array, int left, int mid, int right) { int[] tmpArr=new int[right-left+1];//创建一个数组接收每一次递归的数组 int k=0; //记录左边的起始位置与右边起始位置 int s1=left; int s2=mid+1; while(s1<= mid &&s2<= right){ if(array[s1]<=array[s2]){ tmpArr[k++]=array[s1++]; }else{ tmpArr[k++]=array[s2++]; } } while(s1<= mid){ tmpArr[k++]=array[s1++]; } while(s2<= right){ tmpArr[k++]=array[s2++]; } for(int i=0;i<tmpArr.length;i++){ //这里的left跟随着mid改变，当递归右侧时，left为mid+1 array[i+left]=tmpArr[i]; } }}时间复杂度：O(N*logN)
空间复杂度:O(logN)
稳定排序
4.2非递归归并排序
以每组两个形式分开进行排序，在以每组四个形式排序持续，直到为有序数组。
定义一个gap来每组存储几个数据，通过i下标遍历将每组进行排序，而i下标遍历是以组的形式遍历的，这里直接i+gap*2。
这里left下标就是i，而mid下标是以gap第几组+left-1获取mid值，right值为mid+gap获取最后下标，这里注意可能mid和right会超出范围，如果超出范围，一定是最后一个下标
private static void merge(int[] array, int left, int mid, int right) { int[] tmpArr=new int[right-left+1];//创建一个数组接收每一次递归的数组 int k=0; //记录左边的起始位置与右边起始位置 int s1=left; int s2=mid+1; while(s1<= mid &&s2<= right){ if(array[s1]<=array[s2]){ tmpArr[k++]=array[s1++]; }else{ tmpArr[k++]=array[s2++]; } } while(s1<= mid){ tmpArr[k++]=array[s1++]; } while(s2<= right){ tmpArr[k++]=array[s2++]; } for(int i=0;i<tmpArr.length;i++){ array[i+left]=tmpArr[i]; } } public static void mergeNor(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; } }五.计数排序
计数排序是不需要对两个数值进行比较的排序，他应用于一个数组中指定的区间范围内。
取数组中最大值与最小值
最大值与最小值的差+1作为新的数组长度len不是指定范围内的话，会浪费很多空间。
创建一个临时数组大小为len来进行计数，将array[i]下标-最小值的差放入临时数组中，循环直到结束
临时数组中的计数i需要大于0才证明有计数最后将临时数组给到array数组中即可，之需要将i差值+最小值得到array下标的值即可。
private static void sortCount(int[] array) { int maxVal=array[0]; int minVal=array[0]; for (int i = 0; i < array.length; i++) { if(array[i]>maxVal)maxVal=array[i]; if(array[i]<minVal)minVal=array[i]; } int len=maxVal-minVal+1; int[] count=new int[len]; for(int i=0;i<array.length;i++){ count[array[i]-minVal]++; } int index=0; for(int i=0;i<count.length;i++){ while(count[i]>0){ array[index]=i+minVal; index++; count[i]--; } } }六.测试运行时间代码
// 有序 public static void order(int[] arr){ for(int i=0;i<arr.length;i++){ arr[i]=i; } } //逆序 public static void reverse(int[] arr){ for(int i=0;i<arr.length;i++){ arr[i]= arr.length-i; } } //无序 public static void disorder(int[] arr){ Random random=new Random(); for(int i=0;i<arr.length;i++){ arr[i]= random.nextInt(100); } } //测试 public static void testSort1(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.shellSort(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("希尔排序时间："+(endTime-startTime)); } public static void testSort2(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.inSert(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("插入排序时间："+(endTime-startTime)); } public static void testSort3(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.selectSort2(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("双向选择排序时间："+(endTime-startTime)); } public static void testSort4(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.bubbleSort(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("冒泡排序时间："+(endTime-startTime)); } public static void testSort5(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.heapSort(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("堆排序时间："+(endTime-startTime)); } public static void testSort6(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.quickSort(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("Hoare快速排序时间："+(endTime-startTime)); } public static void testSort7(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.quickSort(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("挖坑法快速排序时间："+(endTime-startTime)); } public static void testSort8(int[] arr){ int[] tmpArray= Arrays.copyOf(arr,arr.length); long startTime=System.currentTimeMillis();//开始结束记录 Sort.quickSort(tmpArray); long endTime=System.currentTimeMillis(); System.out.println("前后指针法快速排序时间："+(endTime-startTime)); }