从学习数据结构开始，就接触了很多排序算法，但是并没有很好的做出总结，训练自己的熟悉写排序算法代码的能力。这篇文章是一个总结，也是一个对排序理解的深入。

1. 选择排序 ：

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序需要比对N-1轮，每轮在所有元素选择最小元素放在最左端，下边是动画演示图 ：

选择排序
选择排序java实现 ：

public class SelectionSort {
    /**
     * 调换数组a中，c和d位置的元素
     */
    public void swap(int[] a, int c , int d ){
        int temp = a[c];
        a[c] = a[d] ;
        a[d] = temp;
    }
    /**
     * 完成对数组a的选择排序
     * @param a
     */
    public void selectionSort(int [] a ){
        if(a.length < 2) return ;
        for (int i =0 ; i <= a.length -1 ; i++){
            int minNumIndex = i ;
            for (int j =i ; j <= a.length -1 ;j ++){
                minNumIndex = a[j] < a[minNumIndex] ? j : minNumIndex ;
            }
            swap(a ,i ,minNumIndex);
        }
    }
    public static void main(String[] args) {
        int [] demo = new int[]{7,2,5,4,9,1} ;
        new SelectionSort().selectionSort(demo);
        System.out.println(Arrays.toString(demo));
    }
}

2.冒泡排序 ：

冒泡排序（Bubble Sort），是一种较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
下图演示了冒泡排序的过程 ：

冒泡排序

不难看出，一轮的冒泡排序会将最大元素放到数组的最后边，所以需要N-1轮迭代，每次迭代确定了最后一个数的位置。下面是冒泡排序的java实现：

public class BubbleSort {
    /**
     * 调换数组a中，c和d位置的元素
     */
    public void swap(int[] a, int c , int d ){
        int temp = a[c];
        a[c] = a[d] ;
        a[d] = temp;
    }

    public void bubbleSort(int[] a){
        if (a.length < 2) return;
        for(int e=a.length -1 ; e>0 ; e--){
            for(int i=0 ;i < e ; i++){
                if(a[i] > a[i+1]){
                    swap(a , i, i+1);
                }
            }
        }
    }
    public static void main(String[] args) {
        int [] demo = new int[]{7,2,5,4,9,1} ;
        new BubbleSort().bubbleSort(demo);
        System.out.println(Arrays.toString(demo));
    }
}

3. 插入排序

前边介绍了冒泡和选择排序，这两种排序方式，不受数据集的影响（是否部分有序）， 插入排序相比这两种方式有了改进，在最好的情况只需要比较N次（待排序数组已经有序），在最坏的情况下，也需要比较O(N^2)次。
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。插入排序在最好情况只需要比较N次，在最坏条件需要比较N^2次。
下面动图演示了插入排序的过程：

插入排序
下面简单解释一下，插入排序迭代N轮（当然是N-1，第1个数不用排）。 第1轮让 a[0]有序，第2轮让<a[0]，a[1]>有序，第三轮让 <a[0]，a[1]，a[2]>有序，依次类推。
算法的主要思想就是每轮将第i个元素，插入到前边已经有序的 i-1个元素中，让这i个元素都有序即可。
下面用java实现插入排序。

public class InsertionSort {
    public void insertionSort(int[] a){
        if (a ==null || a.length < 2 ) return;
        for(int i= 0 ; i< a.length ; i++ ){
            for( int j = i-1 ; j>=0 && a[j] > a[j+1] ; j--){
                ArrayUtils.intArraySwap(a, j, j+1);
            }
        }
    }

    public static void main(String[] args) {
        int [] demo = new int[]{7,2,5,4,9,1} ;
        new InsertionSort().insertionSort(demo);
        System.out.println(Arrays.toString(demo));
    }
}

在表示算法的时间复杂度时，O(logN) 不写底数就代表以2为底N的对数，如果底数是其他（例如3）需要写上。这是一个默认规定。

4.归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序采取递归的方式解决，而且有二分法思想。 开始时，将数组在中间位置划分为左右两个数组，左右分别递归到只剩下一个元素的时候，完成递归条件的终止，同时，合并2个有序的数组为一个有序数组。
下图展示一次归并排序的向下执行过程 ：

递归执行过程

下动图展示了归并排序的过程 ：

归并排序
下面是归并排序的java代码实现 ：

public class MergeSort {

    /**
     * 实现归并排序
     * @param a
     * @param L
     * @param R
     */
    public void mergeSort(int[] a,int L,int R){
//        if(a == null || a.length < 1) return;
        if (L == R) return;
        //注意，这里不能是 (R-L)/2 而是 L + (R-L)/2
        int midIndex = L + (R - L)/2 ;
        mergeSort(a,L,midIndex);
        mergeSort(a,midIndex+1,R);
        process(a,L,midIndex,R) ;
    }
    //合并2个有序数组
    public void process(int[] a, int L, int midIndex, int R) {
        int i = L;
        int j =midIndex +1 ;
        //temp和k用来保存合并排序后的数据
        int[] temp = new int[R-L+1] ;
        int k = 0 ;
        while(i<=midIndex && j<=R){
            temp[k++] = a[i] > a[j] ? a[j++] : a[i++] ;
        }
        while (i<=midIndex){
            temp[k++] = a[i++] ;
        }
        while (j<=R){
            temp[k ++] = a[j++] ;
        }
        for(int p=0 ;p<temp.length ;p ++){
            a[L+p] = temp[p] ;
        }
    }

    public static void main(String[] args) {
        int []arr = {9,8,7,6,5,4,3,2,1};
        new MergeSort().mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}

5.快速排序：

快速排序是O(nlogn)时间复杂度的排序算法。 快速排序的算法基础是“荷兰国旗问题” 。

荷兰国旗问题介绍 ：给定一个数组arr和一个数num，请把小于num是数放在数组的左边，等于num的数放在数组的中间，大于num是数放在数组的右边，要求额外空间为o(1),时间为o(n)。

这里边就涉及到了选择一个边界值的问题，根据选择边界值的方法衍生除了快速排序的多个版本，较低级版本，每次选择数组的最后一个值作为边界值来进行partition 。改进后的快速排序，每次从数组中随机选一个数字作为边界值来进行partition，下面看下partition的主要算法思想 ：

荷兰国旗问题算法
这里边涉及到了3个变量 ： 小于区域边界 、 大于区域边界 、中间的变量指针i。 下图是快速排序的演示 ：
快速排序演示
下面是快速排序的java代码实现 ：

public class QuickSort {
    public void quickSort(int[] a){
        if (a == null || a.length <2) return;
        quickSort(a, 0 ,a.length -1);
    }
    public void quickSort(int[] a,int L, int R){
        if(L < R){
            //在数组的L到R之间随机选取一个数字，并与最后一个数字交换（会使用最后一个数字来partition），作为待partition的分界值
            //Math.random()生成一个[0,1]之间的随机数字
            ArrayUtils.intArraySwap(a ,L + (int)Math.random() * (R-L+1) , R) ;
            //荷兰国旗问题，按照数组最后一个元素来partition ，将数组分为3个区域，区域1<最后一个元素; 区域2=最后一个元素;区域3大于最后一个元素
            //p数组有2个元素，p[0]是小于和等于区域的边界点 p[1]是等于和大于区域的边界点
            int[] p = partition(a,L,R) ;
            quickSort(a,L,p[0]-1);
            quickSort(a,p[0]+1,R);
        }
    }
    private int[] partition(int[] a, int L, int R) {
        //定义左右边界变量，图中的括号
        int less = L - 1 ;
        int more = R ;
        //L是移动游标，图中的i ，滑动比价的终止条件是 变量i右移与右边界左移相遇
        while (L < more){
            if(a[L] < a[R]){
                //如果a[i]<num，交换a[i]和小于区域边界的下一个，小于区域边界右移
                ArrayUtils.intArraySwap(a,++less,L++);
            }
            else if(a[L] > a[R]){
                //如果a[i]>num，交换a[i]和大于区域的前一个元素，大于区域向左移动一位
                ArrayUtils.intArraySwap(a,--more,L);
            }
            else{
                //如果a[i]==num的话，直接向后移动指针
                L ++ ;
            }
        }
        ArrayUtils.intArraySwap(a,more,R);
        return new int[]{less+1,more};
    }

    public static void main(String[] args) {
        int []arr = {9,8,7,6,5,4,3,2,1};
        new QuickSort().quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}

6.堆排序：

堆是一种很重要的数据结构，堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆中包含2个非常常用的操作，heapInsert 和 heapify 。

下面是堆排序的java代码实现 ：

public class HeapInsertion {
    
    //在index位置插入一个数字，并保证数据结构是一个堆，不使用额外空间，自身来做调换。
    public void heapInsert (int[] a ,int index){
        while(a[index] > a[(index-1)/2]){
            ArrayUtils.intArraySwap(a , index , (index-1)/2);
            index = (index - 1)/2 ;
        }
    }

    //堆化一个数组 ，index表示从哪个节点开始做堆化操作; heapsize是堆的大小,控制循环次数(heapsize >= left)
    public void heapify(int[] a, int index, int heapsize){
        int left = index*2+1;  //得到左孩子的位置
        while (left < heapsize){
            //获取2个孩子更大的那一个的节点的下标
            int larger = left + 1 < heapsize && a[left+1] > a[left]? left +1 : left ;
            //比较父节点和两个孩子中更大的孩子，更大的数给larger
            larger = a[larger] > a[index] ? larger : index ;
            if (larger == index){
                break;
            }
            ArrayUtils.intArraySwap(a,larger,index);
            index = larger ;
            left = index*2+1;
        }
    }

    /**
     * 快速排序的实现
     * @param a
     */
    public void heapSort(int[] a){
        if(a == null || a.length < 2) return;
        for(int i = 0; i< a.length ; i++){
            heapInsert(a, i);
        }
        int heapSize = a.length ;
        ArrayUtils.intArraySwap(a,0, --heapSize);
        while(heapSize > 0){
            heapify(a,0,heapSize);
            ArrayUtils.intArraySwap(a,0,--heapSize);
        }
    }

    public static void main(String[] args) {
        int []arr = {9,8,7,6,5,4,3,2,1};
        new HeapInsertion().heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}