常见排序算法详解：插入、希尔、选择、冒泡、堆、快速、归并及计数

时间复杂度 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;
        }elseif(array[left]<array[mid]){
            return left;
        }else{
            return mid;
        }
    }else{//right 大判断中间值
        if(array[left]>array[mid]){
            return left;
        }elseif(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;
        }elseif(array[left]<array[mid]){
            return left;
        }else{
            return mid;
        }
    }else{//right 大判断中间值
        if(array[left]>array[mid]){
            return left;
        }elseif(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=partitionPit(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;
        }elseif(array[left]<array[mid]){
            return left;
        }else{
            return mid;
        }
    }else{//right 大判断中间值
        if(array[left]>array[mid]){
            return left;
        }elseif(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));
}