八大排序

八大排序

目录

1.排序是什么？

2.排序的稳定性

 3.七大排序的时间复杂度与空间复杂度

4.选择排序

5.插入排序（O(n^2)） 类似于打牌（稳定）

6.希尔排序：缩小增量的排序（不稳定）

7.归并排序（和希尔排序很像）

8.快速排序（基于算法导论中的分区思想）重要

8.1随机化快排的问题：

8.2快排的非递归实现

8.3二路快排

8.4挖坑法分区方法代码（直到在纸上如何画图即可）

8.5三路快排 (了解)

9.堆排序（非常稳定）

10.冒泡排序（时间复杂度o(n^2)）

 11.面试题：海量数据的排序处理(常考)

题外话：设置注释

七大排序代码：

1.排序是什么？

排序就是一串记录，按照其中的某个或者某些关键字的大小，递增或递减的排列起来的操作。

2.排序的稳定性

两个相等的数据，如果经过排序，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

 为什么稳定性这么重要？

 3.七大排序的时间复杂度与空间复杂度

这里都是内部排序（一次性将所有待排序的数据放入内存中进行排序，基于元素之间的比较的排序）

而外部排序 ：依赖硬盘（外部存储器）进行的排序算法，桶排序、基数排序、基数排序（对于数据集合的要求非常高，只能在特定的场合下使用）。时间复杂度都是O(n)，应用场景非常局限，只能在特定的场景下去应用。内存放不下，需要外部存储。

器，称为海量排序算法。

4.选择排序

每次从无序区间中选择一个最大或最小值，存放在无需区间的最前或者最后的位置（此位置的元素已经有序） ，直到所有的数据都排序结束。

为什么选择排序不稳定？

选择排序的进阶版本

双向选择排序，一次排序过程中，同时选出最大值和最小值，放在无需区间的最后和最前。 

5.插入排序（O(n^2)） 类似于打牌（稳定）

思路：将集合分为俩个区间，i是当前已经便利的元素，一个已经排序的区间[0...i)，一个待排序的区间&#]。

每次从待排序区间找到一个元素，放入已排序的区间的合适位置，直到整个数组有序。

在近乎有序的数组下，插入排序的数组性能非常好，甚至优于nlog(n)的排序。

插入排序和选择排序最大的不同在于：当插入排序当前遍历的元素>前驱元素时，此时可以提前结束内层循环。

极端场景下，当集合是一个完全有序的集合，插入排序内层循环一次都不走，插入排序时间复杂度变为O(n)。

插入排序经常用作高阶排序算法的优化手段之一

了解：插入排序优化的手段：（用二分查找法）

折半插入排序：

首先：二分查找的前提是该集合必须是一个有序的集合。

而在插入排序中，我们每次都是在有序区间中找一个合适的插入位置，所以可以使用二分查找法来定位元素的插入位置。

这里注意这个公式为什么要这么写：（是为了防止溢出）

6.希尔排序：缩小增量的排序（不稳定）

 先选定一个整数（gap,gap一般都选数组长度的一半或者1/3）

将待排序的数组先按照gap分组，不同组之间使用插入排序，排序之后，再将gap/==2或者gap/=3,重复上述的流程，直到gap=1

当gap=1时，整个数组已经被调整的近乎有序，此时就是插入排序最好的场景，最后再在整个数据上进行一次插入排序。

插入排序和希尔排序，当gap=1时，公式完全一样。

希尔排序为什么要不断地向前比较，能否从零开始向后看gap步？

例:3-----2-----1

不断向后比较

2-----3-----1

2-----1-----3

这样的话，2就没办法换到合适的位置了 

7.归并排序（和希尔排序很像）

思想：将原数组不断拆分，一直拆到每个子数组只有一个元素，第一个阶段结束，归而为1这个阶段结束。

并：将相邻的两个数组合并为一个有序的数组，直到整个数据有序。

分：用的是递归

并：第一步：先创建一个大小为合并之后数组大小的临时数组aux，将数组的值拷贝过去。

第二步：如下

 为何合并过程需要创建一个新的aux数组？

防止在合并过程中，因为小元素要覆盖大的元素，丢失某些元素

归并排序是一个稳定的nlogN排序算法，此处的稳定指的是时间复杂度稳定（无论集合中的元素如何变化，归并排序的时间复杂度一直都是nlogN,不会退化为O(N^2)）且归并排序也是一个稳定性的排序算法（相等元素的先后顺序并不会发生改变）。

(递归类似于树结构，n不断的2/2/2/2，直到只剩下一个元素，这就是logN(树的高度)级别的样子)

递归的深度就是我们拆分数组所用的时间，就是树的高度，logN。

 public static void mergeSort(int []arr){mergeSortInternal(arr,0,arr.length-1);}//在]进行归并排序private static void mergeSortInternal(int[] arr, int l, int r) {if(l>=r){//当前数组只剩下一个元素，归过程就结束了return;}int mid=l+((r-1)>>1);//将原数组拆分为左右俩个小区间，分别递归进行归并排序mergeSortInternal(arr,l,mid);mergeSortInternal(arr,mid+1,r);//merge操作merge(arr,l,mid,r);}

而o(n)来自于合并两个子数组的过程merge,就是一个数组的遍历

综上为非常稳定的nlogN。 

归并排序的两点优化：

1.当左右两个子区间走完子函数后，左右两个区间已经有序了

如果此时arr[mid]<arr[mid+1]

arr[mid]已经是左区间的最大值

arr[mid+1]已经是右区间的最小值

=>整个区间已经有序了，每必要在执行merge过程，只有左右俩个区间还有先后顺序不同时，才merge。

2.在小区间上，我们可以直接使用插入排序来优化，没必要一直拆分到1位置

r-1<=15,使用插入排序性能很好的。

可以减少归并的递归次数 。

8.快速排序（基于算法导论中的分区思想）重要

改进：

 随机选择的代码：

8.1随机化快排的问题：

当待排序的集合中出现大量重复问题时，就会导致某个分区的元素过多（相等的元素全在一个区间中），造成递归过程中，递归树严重不平衡，快排倒退为O(n^2)。

解决办法，把相同的元素均衡在俩个区间。（二路快排）

什么是栈溢出？

 

几数取中，一般都是三数取中，在arr[left],arr[mid],arr[right]中选择一个中间值作为基准

2，3都能避免递归过程中在接近有序的数组上，快速排序分区严重不平衡的问题

8.2有大量重复数据的数组上，快排仍然会退化。

原因：极端情况，当100w个元素全都是一个值的时候，分区之后，<v的元素就没有，全都在>=v的集合中，二叉树又退化成了单支树。

8.2快排的非递归实现

代码如下：

public static void quickSortNonRecursion(int[] arr){Deque<Integer> stack=new ArrayDeque<>();//栈中保存当前集合的开始位置和中止位置int l=0;int r=arr.length-1;stack.push(r);stack.push(l);while(!stack.isEmpty()){//栈不为空，说明子区间还没有处理完毕int left=stack.pop();int right=stack.pop();if(left>=right){//区间只有一个元素continue;}int p=partition(arr,left,right);//依次将右区间的开始和结束位置入栈stack.push(right);stack.push(p+1);//再将左侧区间的开始和结束位置入栈stack.push(p-1);stack.push(left);}}

8.3二路快排

思路：将相等的元素均分到两个子区间

private static int partition2(int[] arr, int l, int r) {int randomIndex&#Int(l,r);swap(arr,l,randomIndex);int v=arr[l];//arr[l+1..i]<=v//[l+1..l+1)=0int i=l+1;//]>=v//(r..r]=0;int j=r;while(true){//i从前向后扫描，碰到第一个>=v的元素停止while(i<=j&&arr[i]<v){i++;}//j从后向前扫描，碰到第一个<=v的元素停止while(i<=j&&arr[i]>v) {j--;}if(i>=j){break;}swap(arr,i,j);i++;j--;}//j落在最后一个<=v的元素身上swap(arr,l,j);return j;}

8.4挖坑法分区方法代码（直到在纸上如何画图即可）

这种方法没有元素交换，只有赋值，理论上会快一点。

这个思路主要用在笔试选择题。

注意：挖坑法必须要先从后向前扫描，再从前向后扫描。

 如果是从前向后扫描，就会有问题，会把大的值换到最前面去

结果：

8.5三路快排 (了解)

在一次分区函数的操作中，把所有相等的元素都放在最终位置，只需要在大于v和小于v的子区间上进行快排，所有相等的元素就不再处理了。

9.堆排序（非常稳定）

思想：以最大堆为例，依次取出最大值，可得到降序数组，无法在原数组上进行排序，还得创建一个和当前数组相同的堆，堆的时间复杂度为o(n)。

10.冒泡排序（时间复杂度o(n^2)）

冒泡排序代码：

 11.面试题：海量数据的排序处理(常考)

假设现在待排序的数据有100G，但是内存只有1GB，如何排序这100GB的数据呢？

12 几种快排总结

快速排序是不稳定的。

nlogn,n是插入排序的insertionSort()方法，logn是递归函数的调用次数（树的高度）。

 

题外话：设置注释

 

七大排序代码：

package sort;import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import urrent.ThreadLocalRandom;public class SevenSort {public static final ThreadLocalRandom random=ThreadLocalRandom.current();/** 选择排序,时间复杂度o(n)* */public static void selectionSort(int [] arr){//最开始无序区[0...n],有序区间为[]//当无序区间只剩下一个元素时，整个集合已经有序。所以length-1for(int i=0;i<arr.length-1;i++){//min变量存储了当前的最小值索引int min =1;//从剩下的元素中选择最小值for(int j=i+1;j<arr.length;j++){if(arr[j]<arr[min]){min=j;}}//min索引一定对应了当前无序区间中找到的最小值索引，换到无序区间的最前面swap(arr,min,i);}}/** 进阶版选择排序* */public static void selectionSortOP(int []arr) {int low = 0;int high = arr.length - 1;//当low=high的时候，无序区间只剩一个元素while (low < high) {int min = low;int max = low;for (int i = low + 1; i <= high; i++) {//这个循环找当前区间的最小值if (arr[i] < arr[min]) {min = i;}//这个循环找当前区间的最大值if (arr[i] > arr[max]) {max = i;}}//min索引现在一定是当前区间的最小值索引，与low交换位置swap(arr, low, min);if (max == low) {//最大值已经被换到min的位置max = min;}//最大值落在了high的位置swap(arr, max, high);low += 1;high -= 1;}}/** 直接插入排序* 每次从无序区间中拿第一个值插入到已经排序区间的合适位置，直到整个数组有序。*已排序区间[0..i)* 待排序区间[i...n]* */public static void insertionSort(int [] arr) {for (int i = 1; i < arr.length; i++) {//待排序区间的第一个元素arr[i]//从待排序区间的第一个元素向前看，找到合适的插入位置//               for (int j = i; j >0; j--) {
//                    //arr[j-1]已排序区间的最后一个元素
//                    if(arr[j]>=arr[j-1]){
//                        //相等也不交换，保证稳定性
//                        //此时说明arr[j]>已排序区间的最大值，说明arr[j]已经有序了
//                        //直接下次循环
//                        break;
//                    }else{
//                        swap(arr,j,j-1);
//                    }
//                }//更简单的写法,和上面一样for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {swap(arr, j, j - 1);}}}/** 折半查找法* */public static void insertionSortBS(int [] arr){//有序区间[0..i)//无序区间[i...n]for (int i = 1; i < arr.length ; i++) {//val当前无序区间中的一个值int val=arr[i];int left=0;int right=i;while(left<right){//找有序区间的中间元素int mid=left+((right-left)>>1);if(val<arr[mid]){right=mid;}else {//val>=arr[mid]left=mid+1;}}//搬移i的元素for (int j=i;j>left;j--){arr[j]=arr[j-1];}//left就是val插入的位置arr[left]=val;}}/** 希尔排序* */public static void shellSort(int [] arr){int gap= arr.length >>1;while(gap>1){//预处理阶段insertionSortByGap(arr,gap);gap=gap>>1;}//此时gap等于1，整个集合已经接近有序，只需要全集合来一次插入排序即可insertionSort(arr);}/**按gap分组进行插入排序* */private static void insertionSortByGap(int[] arr, int gap) {for (int i = gap; i < arr.length ; i++) {//不断向前扫描相同的gap的元素//j-gap从j位置开始向前还有相同步数的元素for (int j = i; j-gap>=0&&arr[j]<arr[j-gap] ; j-=gap) {swap(arr,j,j-gap);}}}/** 递归排序* */public static void mergeSort(int []arr){mergeSortInternal(arr,0,arr.length-1);}//在]进行归并排序,整个arr经过函数后就是一个有序的数组private static void mergeSortInternal(int[] arr, int l, int r) {if(l>=r){//当前数组只剩下一个元素，归过程就结束了return;}int mid=l+((r-1)>>1);//将原数组拆分为左右俩个小区间，分别递归进行归并排序//走完这个函数之后id]已经有序mergeSortInternal(arr,l,mid);mergeSortInternal(arr,mid+1,r);//只有左右俩个区间还有先后顺序不同时，才merge。//merge操作if(arr[mid]>arr[mid]+1) {merge(arr, l, mid, r);}}/** 合并俩个子数组id]和arr[mid&#]* 为一个大的有序数组* */public static void merge(int[] arr,int l,int mid,int r){if(r-l<=15){//小区间直接插入排序insertionSort(arr,l,r);return;}//先创建一个临时数组int[] aux =new int[r-l+1];//将arr元素拷贝到aux上for (int i = 0; i < aux.length; i++) {//新数组与原数组差了l个偏移量arr[i] = arr[i + l];}//i 表示左侧小数组的开始索引//j 表示右侧小数组的开始索引int i=1;int j=mid+1;//原地进行arr数组的合并,k表示当前合并原数组的索引下标for (int k = l; k <=r ; k++) {if(i>mid){//左侧期间已经处理完毕，只需要将右侧区间的值拷贝到原数组即可arr[k]=aux[j-1];j++;}else if(j>r){//右侧区间已经处理完毕，只需要将左侧区间的值拷贝到原数组即可arr[k]=aux[i-1];}else if(aux[i-1]<=aux[j-1]){//此时左侧区间的元素值较小，相等元素放在左区间保持稳定性arr[k]=aux[i-1];i++;}else{//右侧区间的元素较小arr[k]=aux[j-1];j++;}}}
/*
* 在]使用插入排序
* */private static void insertionSort(int[] arr, int l, int r) {for (int i = l+1; i <=r; i++) {for (int j=i;j<l&&arr[j]<arr[j-1];j--){swap(arr,j,j-1);}}}
/*
*归并排序的迭代写法(了解)
* */public static void mergeSortNonRecursion(int[] arr){//最外层循环表示每次合并的子数组的个数for (int sz = 0; sz < arr.length; sz+=sz) {//内层循环的遍历i表示每次合并开始的索引//i+sz就是右区间的开始索引，i<arrlength说明还存在右区间for (int i=0;i+sz<arr.length;i+=sz+sz){merge(arr,i,i+sz-1,Math.min(i+sz+sz-1,arr.length-1));}}}/**快速排序递归实现* */public static void quickSort(int []arr){quickSortInternal(arr,0,arr.length-1);}//在]上使用插入排序private static void quickSortInternal(int[] arr, int l, int r) {//优化后if(r-l<=15){insertionSort(arr,l,r);return;}//优化前//if(l>=r){// return;// }//先获取分区点//所谓分区点就是经过分区函数后，某个元素落在了最终位置//分区点左侧全都是小于该元素的区间，分区点右侧全都是>=该元素的区间int p=partition(arr,l,r);//递归重复在左区间和右区间重复上述流程quickSortInternal(arr, l, p-1);quickSortInternal(arr, p+1, r);}//在]上的分区函数，返回分区点的索引private static int partition(int[] arr, int l, int r) {//随机在当前数组中选一个数int randomIndex&#Int(l,r);swap(arr,l,randomIndex);int v=arr[l];//arr[l+1,j]<v,arr[j+1,i)>=v//i表示当前正在扫描的元素int j=l;for (int i = l+1; i <=r ; i++) {if(arr[i]<v){swap(arr,j+1,i);j++;}}//把基准值和最后一个小于v的元素做交换swap(arr,l,j);return v;}/** 快排的非递归实现(借助栈或者队列)* */public static void quickSortNonRecursion(int[] arr){Deque<Integer> stack=new ArrayDeque<>();//栈中保存当前集合的开始位置和中止位置int l=0;int r=arr.length-1;//先入右后入左，所以先出左后出右stack.push(r);stack.push(l);while(!stack.isEmpty()){//栈不为空，说明子区间还没有处理完毕int left=stack.pop();int right=stack.pop();if(left>=right){//区间只有一个元素continue;}int p=partition(arr,left,right);//依次将右区间的开始和结束位置入栈stack.push(right);stack.push(p+1);//再将左侧区间的开始和结束位置入栈stack.push(p-1);stack.push(left);}}/**双路快排* */public static void quickSort2(int []arr){quickSortInternal2(arr,0,arr.length-1);}private static void quickSortInternal2(int[] arr, int l, int r) {if(r-l<=16){insertionSort(arr,l,r);return;}int p=partition2(arr,l,r);quickSortInternal2(arr,l,p-1);quickSortInternal(arr,p+1,r);}
/*
* 二路开排的分区
* */private static int partition2(int[] arr, int l, int r) {int randomIndex&#Int(l,r);swap(arr,l,randomIndex);int v=arr[l];//arr[l+1..i]<=v//[l+1..l+1)=0int i=l+1;//]>=v//(r..r]=0;int j=r;while(true){//i从前向后扫描，碰到第一个>=v的元素停止while(i<=j&&arr[i]<v){i++;}//j从后向前扫描，碰到第一个<=v的元素停止while(i<=j&&arr[i]>v) {j--;}if(i>=j){break;}swap(arr,i,j);i++;j--;}//j落在最后一个<=v的元素身上swap(arr,l,j);return j;}/** 三路快排* */public static void quickSort3(int[]arr){quickSortInternal3(arr,0,arr.length-1);}public static void quickSortInternal3(int[] arr,int l,int r){if(r-l<=15){insertionSort(arr,l,r);return;}int randomIndex &#Int(l,r);swap(arr,l,randomIndex);int v=arr[l];//这些变量的取值一定满足区间定义//arr[l+1..lt]<v//lt指向最后一个<v的元素int lt=l;//arr[lt+1..i)//i-1是最后一个等于v的元素int i=lt+1;//]>v//gt是第一个>v的元素int gt=r+1;//i从前向后扫描和gt重合时，所有元素就处理完毕while(i<gt){if(arr[i]<v){//arr[l+1..lt]<v//arr[lt+1..i]==vswap(arr,i,lt+1);i++;lt++;}else if(arr[i]>v){//交换到gt-1swap(arr,i,gt-1);gt--;//此处i不++，交换来的gt-1还没有处理}else{//此时arr[i]=vi++;}}//lt落在最后一个<v的索引处swap(arr,l,lt);//arr[l..lt-1]<vquickSortInternal3(arr,r,lt-1);//]>vquickSortInternal3(arr,gt,r);}/** 堆排序* */public static void heapSort(int []arr){for (int i =(arr.length-1-1)/2; i >=0 ; i--) {siftDown(arr,i,arr.length);}//此时数组已经被调整为最大堆for(int i=arr.length-1;i>0;i--){//arr[0]栈顶元素，为当前堆的最大值swap(arr,0,i);siftDown(arr,0,i);}}/** 冒泡排序* */public static void bubbleSort(int []arr){for (int i = 0; i < arr.length; i++) {boolean isSwaped =false;for(int j=0;j< arr.length-1-i;j++){if(arr[j]>arr[j+1]){swap(arr,j,i+1);isSwaped=true;}}}}/*元素下沉操作* *///length数组长度public static void siftDown(int[] arr,int i,int length){while(2*i+1<length){int j=(i<<1)+1;if (j + 1 < length && arr[j+1]>arr[j]) {j=j+1;}//j是左右子树的最大值if(arr[i]>arr[j]){//下沉结束break;}else{swap(arr,i,j);}}}private static void swap(int []arr,int i,int j){int temp =arr[i];arr[i]=arr[j];arr[j]=temp;}//普通测试public static void main(String[] args){int []arr={9,2,5,7,5,4,3,6};selectionSort(arr);System.out.String(arr));}/* //运行测试代码public static void main(String [] args ) {int n = 10000;int[] arr = new int[n];ThreadLocalRandom random = ThreadLocalRandom.current();for (int i = 0; i < n; i++) {arr[i] = Int(0, Integer.MAX_VALUE);}int [] arr1 &#pyOf(arr,n);//当前的系统时间long start =System.nanoTime();heapSort(arr1);long end =System.nanoTime();if(isSorted(arr1)){System.out.println("冒泡排序共耗时："+(end-start)/1000000+"ms");}}*//* int[] arr ={7,4,5,3,2,1,9,10,8,6};heapSort(arr);System.out.String(arr));*//*//性能测试代码public static boolean isSorted(int []arr){for(int i=0;i<arr.length-1;i++){if(arr[i]>arr[i+1]){System.out.println("sort error");return false;}}return true;}*/}