排序-java（详解）

一，分类

主要的排序大致分为以下几类：

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）稳定性：稳定

注：计数排序稳定，但是上述的实现方法不稳定！！！