排序算法

1. 插入排序

• 思想： 假设左边的已经排好序，要加入的数值需要从右边开始逐个比较。如果小于下一个要比较的值arr[j-1]，那么交换arr[j-1]到后面一个位置。如果大于或等于（即不小于）下一个要比较的值arr[j-1]，那么要插入的值位置应该在arr[j]。

• java实现

package Sort;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        int[] arr= {5,3,8,6,4};
        ToInsertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void ToInsertSort(int[] arr) {
        if(arr==null || arr.length==0)
            return;
        
        for(int i=1;i<arr.length;i++) { //假设最左边的已经排序好
            int temp=arr[i];            //这个位置可能被占用
            
        
            int j=i;
            while(j>0&&arr[j-1]>temp) {
                arr[j]=arr[j-1];
                j--;
            }
            
            arr[j]=temp;
        }
    }

}

• 复杂度

1. 时间上，最坏，1+2+ ... +(n-1)=n*(n-1)/2；最好，n
2. 空间上，n

2. 选择排序

• 思想：插入排序的改进。考虑到插入排序在序列基本有序的条件下，效率更高。选择增量序列，进行k趟排序。

package Sort;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] arr= {5,3,8,6,4,9,10,5,6};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void shellSort(int[] arr) {
        if(arr==null || arr.length==0)
            return;
        
        int d=arr.length/2;
        for(;d>=1;d=d/2) {
            shellInsert(arr,d);
        }
    }
    
    private static void shellInsert(int[] arr,int d) {
        //进行插入排序
        for(int i=d;i<arr.length;i++) {    //假设d位置之前的已经排好序
            int temp=arr[i];
            int j=i;
            while(j>d-1&&arr[j-d]>temp) {
                arr[j]=arr[j-d];
                j-=d;  //竞争j-d  -->j-d位置
            }
        arr[j]=temp;
        }
    }

}

• 复杂度

1. 时间上，最坏，不好算，是o(n^2 )；最好，log(n)*n；平均，n^1.3
2. 空间上，n

3. 选择排序

• 思想：选择出最小值的下标，进行交换。

package Sort;

import java.util.Arrays;

public class SelectSort {

    public static void main(String[] args) {
        int[] arr= {5,3,8,6,4,9,10,5,6};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void selectSort(int[] arr) {
        if(arr==null || arr.length==0)
            return;
        
        for(int i=0;i<arr.length-1;i++) {
            int minindex=i;
            for(int j=i+1;j<arr.length;j++) {
                if(arr[minindex]>arr[j])
                    minindex=j;
            }
            
            if(minindex!=i)
                swap(arr,minindex,i);
        }
    }
    
    private static void swap(int[] arr,int i,int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    } 
}

• 复杂度

1. 时间上，最坏和最好都是1+2+3+ ... +n-1=n(n-1)/2
2. 空间上，n。辅助空间o(1)

4. 冒泡排序

• 思想：比较相邻的两个元素，仍后根据结果决定是否交换位置。比选择排序要差，交换次数太多。不过有一点优于选择排序：可以根据某个指标判断是否提前完成排序。

package Sort;

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr= {5,3,8,6,4,9,10,5,6};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void bubbleSort(int[] arr) {
        if(arr==null || arr.length==0)
            return;
        
        int flag=0;
        for(int i=0;i<arr.length-1;i++) {
            if(flag==1)
                break;
            
            flag=1;
            for(int j=arr.length-1;j>i;j--) {
                if(arr[j]<arr[j-1]) {
                    swap(arr,j,j-1);
                    flag=0;
                }
            }
        }
    }
    
    private static void swap(int[] arr,int i,int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    } 

}

• 复杂度

1. 时间上，最坏o(n^2) ，最好o(n)。
2. 空间上，n。辅助空间o(1)

5. 归并排序

• 思想：分而治之，后合并。分到只有一个数为止，然后合并。

package Sort;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] arr= {5,3,8,6,4,9,10,5,6};
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void mergeSort(int[] arr,int left,int right) {
        if(arr==null || arr.length==0)
            return;
        
        if(left>=right)
            return;
        
        int mid=(left+right)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }
    
    private static void merge(int[] arr,int left,int mid,int right) {
        int[] temp=new int[right-left+1];
        int i=left;
        int j=mid+1;
        int k=0;
        while(i<=mid&&j<=right) {
            if(arr[i]<arr[j]) 
                temp[k++]=arr[i++];
            else
                temp[k++]=arr[j++];
        }
        
        while(i<=mid)
            temp[k++]=arr[i++];
        while(j<=right)
            temp[k++]=arr[j++];
        
        for(int p=0;p<temp.length;p++)
            arr[left+p]=temp[p];
    }
}

• 复杂度

1. 时间上，nlog(n)。
2. 空间上，n+n。辅助空间o(n)

6. 快速排序

• 思想：分而治之。每次确定出来一个pivot（基准）。它左边的数都比pivot小，右边都大。这样pivot的位置就确定了。递归下去。有归并的味道。不过，归并是后期发力。快速一开始就会确定一个位置。

package Sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr= {5,3,8,6,4,9,10,5,6};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void quickSort(int[] arr,int left,int right) {
        if(arr==null || arr.length==0)
            return;
        
        if(left>=right)
            return;
        
        int pivot=partition(arr,left,right);
        quickSort(arr,left,pivot-1);
        quickSort(arr,pivot+1,right);
    }
    
    private static int partition(int[] arr,int left,int right) {
        int pivot=left;
        int pivotKey=arr[left];
        
        while(left<right) {
            while(left<right&&arr[right]>=pivotKey)
                right--;
            while(left<right&&arr[left]<=pivotKey)
                left++;
            
            swap(arr,left,right);
        }
        
        if(left!=pivot)
            swap(arr,left,pivot);
        
        return left;
    }
    
    private static void swap(int[] arr,int i,int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    } 
}

• 复杂度

1. 时间上，平均nlog(n)。
2. 空间上，n。辅助空间o(1)

7. 堆排序

• 思想：首先，调整数组到满足堆性质。大顶堆，即数组第1个数最大。然后交换首末数。这样最后面的数最大。调整堆。

package Sort;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr= {5,3,8,6,4,9,10,5,6};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void heapSort(int[] arr) {
        for(int i=arr.length/2-1;i>=0;i--) {   //下标为arr.length/2-1，才开始有子叶
            heapAdjust(arr,i,arr.length-1);
        }
        
        for(int i=arr.length-1;i>0;i--) {
            int temp=arr[0];
            arr[0]=arr[i];
            arr[i]=temp;
            
            heapAdjust(arr,0,i-1);
        }
        
    }
    
    private static void heapAdjust(int[] arr,int start,int end) {
        int temp=arr[start];
        int i=2*start+1;
        while(i<=end) {  //子节点是2*i+1  2*i+1
            if(i<end&&arr[i]<arr[i+1])
                i++;
            
            if(temp>=arr[i])    //满足堆性质
                break;
            
            arr[start]=arr[i];
            start=i;            //开启下一轮,确定下标i位置是否满足性质
            i=2*start+1;
        }
        arr[start]=temp;
    }

}

• 复杂度

1. 时间上，o(nlog(n))。
2. 空间上，n。辅助空间o(1)

8. 基数排序

• 思想：借助多关键字排序思想对单逻辑关键字进行排序的方法。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。

package Sort;
import java.util.*;

public class RadixSort {

    public static void main(String[] args) {
        int max=100;
        int min=1;
        int[] arr = new int[10];
        Random random = new Random(47);
        for (int i=0; i<10; i++) {
            int s = random.nextInt(max)%(max-min+1) + min;
            arr[i]=s;
            //System.out.println(s);
        }
        //int[] arr= {5,3,8,6,4,9,10,5,6,12,123};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void radixSort(int[] arr) {
        if(arr==null || arr.length==0)
            return;
        
        int arrMax=getMax(arr);
        int maxBit = (arrMax+"").length();
        for(int i=1;i<=maxBit;i++) {
            List<List<Integer>> buf=distribute(arr,i,maxBit);
            collect(arr,buf);
        }
    }
    
    public static void collect(int[] arr,List<List<Integer>> buf) {
        int k=0;
        for(List<Integer> bucket:buf) {
            for(int ele:bucket) {
                arr[k++]=ele;
            }
        }
    }
    
    public static List<List<Integer>> distribute(int[] arr,int bit,int maxBit){
        List<List<Integer>> buf = new ArrayList<List<Integer>>();
        for(int i=1;i<=10;i++)
            buf.add(new LinkedList<Integer>()); 
        
        for(int i=0; i<arr.length; i++) {
            buf.get(getNBit(arr[i], bit)).add(arr[i]);
        }
        return buf;
    }
    
    public static int getNBit(int x, int n) {
        String sx = x + "";
        if(sx.length() < n)
            return 0;
        else{
            return sx.charAt(sx.length()-n)-'0';
        }
    }

    public static int getMax(int[] arr) {
         int max=arr[0];
         for(int i=1;i<arr.length;i++){
              if(arr[i]>max){
                 max=arr[i];
              }
         }
         
        return max;
    }
}

• 复杂度

1. 时间上，o(d(n+rd))
2. 空间上，n+rd。辅助空间o(rd)

总结（来源“算法爱好者”）

在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序，只有最适合的排序。

下面就总结一下排序算法的各自的使用场景和适用场合。

1. 从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。

2. 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。

3. 基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。

4. 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。

5. 上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。