一,分类
主要的排序大致分为以下几类:
1,插入排序,又分为直接插入排序和希尔排序
2,选择排序,又分为选择排序和堆排序
3,交换排序,又分为冒泡排序和快速排序
4,归并排序
二,插入排序
1,直接插入排序
一个数组,定义两个变量i和j,i从数组的第二个元素开始往后遍历,直到数组结束。每次遍历把下标为i的值储存到临时变量tmp中。与此同时,j=i-1,j往前遍历,每一次下标j对应的值都与tmp进行比较,如果j的对应值大于tmp,则arr【j+1】=arr【j】,如果小于tmp的值,则直接跳出循环。因为如果遇到小于tmp的值,则这个值前面的数据肯定都小于tmp,这时就可以直接将tmp的值放入arr【j+1】里面。
public static void insertSort(int[] array){ for (int i = 1; i < array.length; i++) { int tmp=array[i]; int j = i-1; for (; j >=0 ; j--) { if (tmp<array[j]){ array[j+1]=array[j]; } else { break; } } array[j+1]=tmp; } }
简易图:
总结:
(1)对于直接插入排序,越有序,排序越快,所以如果一组数据趋于有序时,可以优先选择直接插入排序
(2)时间复杂度:O(n^2)
(3)空间复杂度:O(1)
(4)稳定性:稳定
注:稳定性指:
2,希尔排序
希尔排序时对直接插入排序的优化。其又称为缩小增量的排序,将数据分成不同的组,然后将每一组的数据进行直接插入排序,然后将组数不断减少,直到减少到一,每减少一次就排一次序。当组数多的时候每组的数据少,所以时间复杂度小,当组数小的时候,虽然数据比较多,但是数据是趋于有序的,所以直接插入排序的时间复杂度也较低,综上所述,这种方法的效率较高。
public static void shellSort(int[] array){ int gap= array.length; while (gap>1){ gap/=2; shell(array,gap); } } public static void shell(int []array,int gap){ for (int i = gap; i < array.length; i++) { int tmp=array[i]; int j = i-gap; for (; j >=0 ; j=j-gap) { if (tmp<array[j]){ array[j+gap]=array[j]; } else { break; } } array[j+gap]=tmp; } }
总结:
(1) 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算
时间复杂度(估算):O(n*log2(n))
(2)空间复杂度:O(1)
(3)稳定性:不稳定
三,选择排序
1,选择排序
定义i和j两个变量,i从0开始遍历整个数组,定义最小值的下标变量为minIndex,当 i 每等于一个值时,minIndex=i,j就从i+1开始向后遍历,遇到array[minIndex]>array[j],就将minIndex=j从而保证这是这次 j 遍历的数据中的最小值,直到 j 遍历完整个数组后,将下标为i的值与下标为minIndex的值进行交换。从而使i的位置是这次 j 遍历的数据中的最小值。然后i++,继续寻找第二小的值放到 i 的位置……
下图为i=0时的一次遍历:
private static void swap(int[]array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; } 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[minIndex]>array[j]){ minIndex=j; } } swap(array,i,minIndex); } }
当然我们也可以在 j 遍历的时候同时找到最小值和最大值的下标,但需要注意的是,第一次遍历之后就可以筛选出最大值和最小值,这时最小值放第一个,最大值放最后一个,第二次遍历的时候就不需要遍历头和尾了。因此每次遍历就可以挑出一对数据,最大值和最小值。所以下一次遍历就只需要从中间寻找最大值和最小值了,所以i只需要遍历一半的数据就可以完成整个排序。
public static void selectSort2(int[]array){ for (int i = 0; i < array.length/2; i++) { int minIndex= i; int maxIndex= i; for (int j = i+1; j < array.length-i; j++) { if (array[j]< array[minIndex]){ minIndex=j; } if (array[j]> array[maxIndex]){ maxIndex=j; } } swap(array,minIndex,i); if (maxIndex==0){ maxIndex=minIndex; } swap(array,maxIndex,array.length-1-i); } }
总结:
(1) 时间复杂度:O(n^2)
(2)空间复杂度:O(1)
(3)稳定性:不稳定
2,堆排序
堆排序时首先要调整成大根堆,因为大根堆下标为0的元素一定是最大的,所以可以将第一个元素和最后一个下标的元素交换,然后将第一个元素向下调整重新调整为大根堆,调整的终点是前一次调整的数组长度-1(已经选出了最大的元素,现在需要在剩余的元素中找到第二大的,所以向下调整大范围不包括已经排好序的数据),然后然后循环上述行为。使数组中的每一个元素都得到调整从而就可以得到顺序了。
延伸说明:
调整大根堆:我们需要求出最后一个子节点的父节点,然后向前遍历,将每一个父节点就进行向下调整。
向下调整:需要知道需要调整的父节点的下标和调整的范围(如果是建立大根堆,调整的范围就是到最后一个下标),知道父亲节点后求出左子节点,然后判断是否有右子节点,如果有那么判断array[child+1]与array[child]的大小关系,如果关系是大于,那么child++,这样保证child所指向的是较大的子孩子。然后将较大的子孩子和父节点的值进行比较,如果孩子节点大于父亲节点,那么两者交换,因为如果两者交换的话,会影响被交换为子节点的节点作为父亲节点时,与它自己的子节点的大小关系,所以交换后要parent=child; child=parent*2+1;然后再次重复循环上述操作,直到孩子节点是越界,则代表调整完毕。但如果父亲节点大于孩子节点就可以直接跳出循环了,因为父子节点之间不需要交换,而子节点以下的节点本身就是调整好的所以不需要再次调整,直接跳出循环即可。
public static void siftDown(int []array,int parent,int end){ int child=parent*2+1; while (child<end+1){ if (child+1<=end){ if (array[child+1]>array[child]){ child++; } } if (array[child]>array[parent]){ swap(array,child,parent); parent=child; child=parent*2+1; }else { break; } } } public static void createBigHeap(int[]array){ int child=array.length-1; int parent= (child-1)/2; while (parent>=0){ siftDown(array,parent,array.length-1); parent--; } } public static void heapSort(int []array){ //调整为大根堆 createBigHeap(array); int end= array.length-1; while (end>0){ swap(array,0,end); end--; siftDown(array,0,end); } }
总结:
(1) 时间复杂度:O(n*log2(n))
(2)空间复杂度:O(1)
(3)稳定性:不稳定
四,交换排序
1,冒泡排序
我们已经很熟悉就不过多赘述了
public static void bubbleSort(int[] array){ for (int i = 0; i < array.length-1; i++) { boolean flg=false; for (int j = 0; j < array.length-1-i; j++) { if (array[j]> array[j+1]){ swap(array,j,j+1); flg=true; } } //在优化情况下,时间复杂度为0(n) if (flg==false){ break; } } }
总结:
(1)时间复杂度:O(n^2)
(2)空间复杂度:O(1)
(3)稳定性:稳定
2 ,快速排序:
快排运用的是二叉树的逻辑,我们首先将要排序的数组的首元素作为标准,然后定义变量left和right,right先进行遍历,遇到比标准小的停止,然后left开始向右遍历,遇到比标准大的停下来然后,left和right对应的值相互交换,之后right继续向后遍历,重复之前的操作,直到right和left相遇,然后将标准呢的值与相遇对应的值进行交换,同时获得了right和left相遇的小标,然后进行递归,先递归相遇点左边了,不过这次传入的排序的范围是从开始到相遇点,再递归右边的,传入的范围是相遇点+1到结尾。
Hoare法:
public 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; }
找到par的下标还有另一种方法:
挖坑法:
private static int partition2(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]; } //left和right相遇了 array[left]=tmp; return left; }
public static void quick(int []array,int start,int end){ if (start>=end){ return; } int par=partition(array,start,end); quick(array,start,par-1); quick(array,par+1,end); } public static void quickSort(int[]array){ quick(array,0,array.length-1); }
优化:
因为找到的相遇点是数组的中间的值那么,时间复杂度是整个数组的长的乘以二叉树的高度,但是如果二叉树是单支二叉树,那么树的高度就是n,时间复杂度就成了n^2,所以我们用三树取中法。即找到要排列的数组的第一个和最后一个,和中间的数,然后找到三个数中间大的那个放到数组的首位
private static int midThreeNum(int[]array,int left,int right) { int mid = (left + right) / 2; if (array[left] < array[right]) { if (array[left] > array[mid]) { 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 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 >=0 ; j--) { if (tmp<array[j]){ array[j+1]=array[j]; } else { break; } } array[j+1]=tmp; } }
完整的代码:
public 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; } private static int midThreeNum(int[]array,int left,int right) { int mid = (left + right) / 2; if (array[left] < array[right]) { if (array[left] > array[mid]) { 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 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 >=0 ; j--) { if (tmp<array[j]){ array[j+1]=array[j]; } else { break; } } array[j+1]=tmp; } } public static void quick(int []array,int start,int end){ if (start>=end) { return; } if((end-start)<10){ insertSort(array,start,end); return; } int mid=midThreeNum(array,start,end); swap(array,mid,start); int par=partition(array,start,end); quick(array,start,par-1); quick(array,par+1,end); } public static void quickSort(int[]array){ quick(array,0,array.length-1); }
快速排序的非递归:
这里主要运用到了栈。首先我们,初始化left和right变量,通过partition找到par,然后如果left+1<par则代表,par和left下标之间最少有一个值,这时,将left和par-1的值放到栈中(这里入栈相当于标记了还没有呈现出有序的区间左右坐标),如果不符合该条件,则说明par和left之间没有其他值,left就是par左边的值,因为par左边都是比par对应的值小的,右边都是比par对应的值大的,此时说明left和par是呈现出一个有序的状态,所以不用入栈。如果par<right-1,把par+1和right放入栈中。之后把栈中弹出一个赋值到right中,弹出一个赋值到left中,重复如果left+1>par,则将left和par-1的值放到栈中,如果par<right-1,把par+1和right放入栈中。重复这个步骤直到栈中为空,此时整个数组呈现出有序的状态。
public static void quickSortNor(int []array){ Stack<Integer> stack=new Stack<>(); int left=0; int right=array.length-1; int par=partition(array,left,right); if (left+1<par){ stack.push(left); stack.push(par-1); } if (right-1>par){ stack.push(par+1); stack.push(right); } while (!stack.isEmpty()){ right=stack.pop(); left=stack.pop(); par=partition(array,left,right); if (left+1<par){ stack.push(left); stack.push(par-1); } if (right-1>par){ stack.push(par+1); stack.push(right); } } }
总结:
(1)时间复杂度:O(n*log2(n))
(2)空间复杂度:O(log2(n))
(3)稳定性:不稳定
五,归并排序
先将数组不断对半分,分成一个为一组,然后将两组归并为一组,归并时要进行排序。以下图红框框住的为例,初始化变量s1,e1,s2,e2分别为两组数据的首尾,然后将两组数据的第一个进行比较,小的放入临时数组中,然后加加,再次进行比较。直到将这四个数据全部放到tmp中。
private static void merge(int []array,int left,int mid,int right){ int b1=left; int e1=mid; int b2=mid+1; int e2=right; int index=0; int[] tmp=new int[right-left+1]; while (b1<=e1&&b2<=e2){ if (array[b1]<=array[b2]){ tmp[index]=array[b1]; index++; b1++; } else { tmp[index]=array[b2]; index++; b2++; } } while (b1<=e1){ tmp[index++]=array[b1++]; } while (b2<=e2){ tmp[index++]=array[b2++]; } for (int i = 0; i < tmp.length; i++) { array[i+left]=tmp[i]; } } public static void mergeSortFun(int[]array,int left,int right){ if (left>=right){ return; } int mid=(left+right)/2; mergeSortFun(array,left,mid); mergeSortFun(array,mid+1,right); merge(array,left,mid,right); } public static void mergeSort(int [] array){ mergeSortFun(array,0,array.length-1); }
非递归:
首先是一组一个数据,每两组进行重新比较排序,遍历完整个数组。然后一组两个数据,每两组进行重新比较排序,遍历整个数组,循环上述步骤,直到每一组的数据等于整个数组的长度为止。此时,数组就排好了
public static void mergeSortNor(int[]array){ int gap=1; while (gap<array.length) { for (int i = 0; i < array.length; i = i + 2 * gap) { int left = i; int mid = i + gap - 1; if (mid >= array.length) { mid = array.length - 1; } int right = mid + gap; if (right >= array.length) { right = array.length - 1; } merge(array, left, mid, right); } gap *= 2; } }
总结:
(1)时间复杂度:O(n*log2(n))
(2)空间复杂度:O(n)
(3)稳定性:稳定
海量数据排序:
例如有100G的文件,但内存只有1G,因为内存中无法将所有数据全部放下,所以我们可以将数据平分成200份 每一份有512MB,这时现将每份文件放到内存里面排好序,然后再放回磁盘,然后将两份文件归并排序,最终就有序了
六,其他
1,基数排序
创立19个队列,下标为0-18的队列分别对应的-9到9的数字,然后找到数组中最大值和最小值,此时如果最小值为负数的话,要比较最大值和最小值取负数的大小关系。从而找到整个数组中,位数最大的数字。这里的位数决定的以下操作要循环的次数。然后遍历数组,根据元素个位数的值将元素放到对应的数列中,例如:个位数为9,将139放到9对应的下标19的队列中。然后根据顺序将把队列中的数据重新放回数组中,这个时是根据根据个位数的大小进行排序的,然后位数减一(等价于maxVal/=10),因为下一次要找的是十位对应的值,所以 ret*=10,遍历数组时每个数据除ret就是对应位上的数值。
不同数位对应的队列的下标表:
public static void radixSort(int []array){ //1,创立19个队列,下标为0-18的队列分别对应的-9到9的数字 Queue<Integer>[] queues=new Queue[19]; //2,选出来最大值位数 int maxVal=array[0]; int minVal=array[0]; for (int i = 0; i < array.length; i++) { if (maxVal<array[i]){ maxVal=array[i]; } if (minVal>array[i]){ minVal=array[i]; } } if (minVal<0&&maxVal<-minVal){ maxVal=-minVal; } //3,遍历最大数位次 int ret=1; while (maxVal>0){ //4,遍历数组的每一位,根据该值对应位次的数字,将该值储存到对应的下标中 for (int i = 0; i < array.length; i++) { int tmp; if(array[i]<=0){ tmp=9-((-array[i]/ret)%10); }else { tmp=9+((array[i]/ret)%10); } if (queues[tmp]==null){ queues[tmp]=new LinkedList<>(); } queues[tmp].offer(array[i]); } //5,将将列队中的数据以顺序的方式取出,重新放回数组中 int j=0; for (int i = 0; i < queues.length; i++) { while (queues[i]!=null&&!queues[i].isEmpty()){ array[j]=queues[i].poll(); j++; } } //6,最大的位数减一 maxVal/=10; ret*=10; } }
2,计数排序
适用于数组数据位于集中区域内。首先找到数据的最大和最小值,从而确定创建数组的大小(该数组实现的功能是数组中的每一个值都有一个对应的空间,对应的空间记录的是这个值的个数),因为数组的下标是以0开始的所以每个数据减去最小值就是对应的下标。遍历array数组,找到每个值对应的下标,数组中下标对应的值加加。此时,count数组的下标+最小值,是原数组中每一个数据的值,而下标对应的数字,则是原数组中每一个数据的值的个数。遍历count数组,根据count数组的下标,和下标对应的值,将原数组数据从小到大重新放回array数组中。
public static void countSort(int[]array){ int maxVal=array[0]; int minVal=array[0]; for (int i = 0; i < array.length; i++) { if (maxVal<array[i]){ maxVal=array[i]; } if (minVal>array[i]){ minVal=array[i]; } } int[]count=new int[maxVal-minVal+1]; for (int i = 0; i < array.length; i++) { count[array[i]-minVal]++; } int j=0; for (int i = 0; i < count.length; i++) { while (count[i]>0) { array[j] = i + minVal; j++; count[i]--; } } }
总结:
(1)时间复杂度:O(n*数据范围)
(2)空间复杂度:O(1)
(3)稳定性:稳定
注:计数排序稳定,但是上述的实现方法不稳定!!!
标签:right,java,int,length,详解,数组,array,排序,left From: https://blog.csdn.net/2302_81705247/article/details/140238321