从今天开始，更新的文章可能在排版上不那么正规了。

ok，先看看冒泡排序吧。

原理很简单哈，数组中两两比较，如果你是从小到大排序，就把大的往后移动。

说白了，两数个比较，如果前一个比后一个大，就交换两个的位置。

整个代码两层for循环嵌套。精华就下面这坨。

   // 不要紧张，这个numbers就是一个整数数组，里面装的数据是混乱的，我们准备把他排序。
   for(int i = 0; i < numbers.length - 1; i++){            //为啥 length - 1，因为-1次循环可以排完序了，你多循环一次没啥用。 
            for (int j = 0; j < numbers.length - i -1; j++) {   //为啥length - i - 1，-1跟上面一样，-i下面讲
                if(numbers[j] > numbers[j + 1]) {   //这里也不要紧张，通过异或运算（^）交换**整数**numbers[j]和**整数**numbers[j + 1]的值，不信你试试
                    numbers[j] ^= numbers[j+1];
                    numbers[j+1] ^= numbers[j];
                    numbers[j] ^= numbers[j+1];
                }
            }
        }

理解不了就死背代码吧。

算法里面有个叫稳定性的东西：
稳定 ：当a > b，就不会交换两个数的位置。
不稳定：当a > b, 可能发生两个数交换位置。
所以，冒泡是稳定的。

但是在时间方面比较慢。我测试10000个打乱的int数从小到大排序五次，花费时间分别为： 220ms 202ms 234ms 253ms 227ms

整个测试代码如下：

public static void main(String[] args) {
        int[] a = new int[10000];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int)(Math.random() * 10000);
        }
        //冒泡排序
        bubbleSort(a.clone());       //由于我测试多种排序使用同一初始数组，所以克隆一下。
    }

    //冒泡排序
    public static void bubbleSort(int[] numbers) {
        long start = System.currentTimeMillis();    //记录初始时间
        for(int i = 0; i < numbers.length - 1; i++){
            for (int j = 0; j < numbers.length - i -1; j++) {
                if(numbers[j] > numbers[j + 1]) {
                    numbers[j] ^= numbers[j+1];
                    numbers[j+1] ^= numbers[j];
                    numbers[j] ^= numbers[j+1];
                }
            }
        }
        long end = System.currentTimeMillis();   //记录结束时间
        System.out.println(Arrays.toString(numbers));
        System.out.println("冒泡排序时间:" + (end - start));
    }

ok， 下面再看看快速排序。

这个快速排序理论有点复杂。

看这个图哈（刚刚盗的）。

image

这个数组第一个数是6， ok，接下来注意， 从右往左 找到一个比6小的数，从左往右找到一个比6大的数，然后交换这个数的位置。如下：

快速排序

快速排序

依次这样，注意哈，必须每次都从右边开始找。知道从两边找的时候相遇。

快速排序

然后把最中间这个数和第一个数6做交换。

快速排序

快速排序

从中间的6为界限，把整个需要排序的数组分成两部分。左边为3， 1， 2， 5， 4； 右边是9， 7， 10， 8；

可以看出，已经把大于6和小于6的分开了，接下来嘛，把这两部分按之前的办法继续排就行。

当然，代码上需要使用到递归的方法。所以一开始啊就要设计好一个方法用来递归的调用。

递归方法设计如下：

//且看，这里传入了三个参数，第一个参数a 表示要排序的整个的数组，start表示从这个数组的排序起始位置，end则表示这个数组的排序结束位置。
private static void quickSort(int[] a, int start, int end){
        if(end < start)     //结束位置大于起始位置，表示排完了，方法直接结束。
            return ;
        int key = a[start];     //记录需要排序的的哥元素，比如之前我们说的6
        int i = start;          //记录排序起始位置和结束位置
        int j = end;
       //这个循环就是循环从右开始找比第一个数小的和从左开始找比第一个数大的做交换
        while(i < j) {
            //先从右找（必须）小于key的值，找到了就跳出循环
            while(a[j] >= key && i < j){
                j--;
            }
           // 再从左找大于key的值，找到就跳出循环
            while(a[i] <= key && i < j){
                i++;
            }
            // 从右找的满足条件的下标**大于**从左找到满足条件的下标，就交换两个数的值
            if(i < j) {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }
        }
        //交换最中间的数和第一个被选择的数
        a[start] = a[i];
        a[i] = key;
        //递归分出来的左部分
        quickSort(a, start, i - 1);
        //递归分出来的右部分
        quickSort(a, i + 1, end);
       //中间那个数就不参与排序了。
    }

我测试五组数据，花费时间如下：6ms，4ms，0ms，5ms，5ms

测试代码如下：

  public static void main(String[] args) {
        int[] a = new int[10000];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int)(Math.random() * 10000);
        }
        System.out.println(Arrays.toString(a));
        //快速排序
        quickSort(a.clone());
    }

    //快速排序
    private static void quickSort(int[] numbers){
        long start = System.currentTimeMillis();
        quickSort(numbers, 0, numbers.length - 1);
        long end = System.currentTimeMillis();
        System.out.println(Arrays.toString(numbers));
        System.out.println("快速排序时间:" + (end - start));
    }

    //被递归的方法
    private static void quickSort(int[] a, int start, int end){
        if(end < start)
            return ;
        int key = a[start];
        int i = start;
        int j = end;
        while(i < j) {
            while(a[j] >= key && i < j){
                j--;
            }
            while(a[i] <= key && i < j){
                i++;
            }
            if(i < j) {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }
        }
        a[start] = a[i];
        a[i] = key;
        quickSort(a, start, i - 1);
        quickSort(a, i + 1, end);
    }

但你应该可以看出，快速排序不是稳定的，并且算法上复杂一点。

接下来look下插入排序。

原理呢，也很简单，首先把需要排序的数组看成一个有序表和一个无序表。比如：

数组a = {10，2，8，6，13，57，22，19，4}

先把10这一个元素看成是有序表，2到后边的4堪称无序表。

我们每次从无序表中取一个元素放到有序表去排序，知道排完。

核心代码如下：

       //从第二个开始排，所以i = 1,注意这里**不能length - 1**
       for (int i = 1; i < a.length; i++) {
            //从右向左去比较，如果小于前面的就交换，类似冒泡排序哈
            for(int j = i - 1; j >= 0; j--) {
                if(a[j] > a[j + 1]) {
                    a[j] ^= a[j+1];
                    a[j+1] ^= a[j];
                    a[j] ^= a[j+1];
                }
            }
        }

测试五组数据，花费时间如下： 180ms， 185ms，165ms，181ms，168ms

效率比冒泡快一点。同时它是稳定的。

继续。looklook归并排序。

归并排序基于分治法 。别问我，我也不知道啥是分治法。

原理就是一直划分一直划分，划分出很多个小序列，各自排序，然后再合并排序。

举个栗子

原数组 ： 6 3 5 8 1 7 2 4

第一次划分： 6 3 5 8 | 1 7 2 4

第二次划分： 6 3 | 5 8 | 1 7 | 2 4

第三次划分： 6 | 3 | 5 | 8 | 1 | 7 | 2 | 4

划分到第三次发现所有的小序列都是有序的了。接下来慢慢合并小序列。

第一次合并： 3 6 | 5 | 8 | 1 | 7 | 2 | 4 //这里只把第一个和第二个排了序。

第二次合并： 3 6 | 5 8 | 1 | 7 | 2 | 4 //只把第三个和第四个排了序。

第三次合并： 3 5 6 8 | 1 | 7 | 2 | 4 //前面四个排序完成，后面四个亦是如此

我们细说下第三次合并是什么回事。

在第二次合并的时候，3和6是一组，5和8是一组，首先去第一组的第一个和第二组的第一个比较将最小的结果放在新的数组中，这里最小的就是3，放到新数组的的第一个，接下来比较第一组的第二个和第二组的第一个比较，也就是6和5比较，最小的是5，把5放到新数组的第二个位置，再把第一组的第二个和第二组的第二个比较，依次进行直到合并完成。

直接分析代码吧。

//这个方法需要传三个参数，a为需要排序的数组，start是需要排序的初始位置，end是需要排序的终止位置。
private static void mergeSort(int[] a, int start, int end){
        //先判断是否有需要排序的元素
        if(start == end)
            return;
        //找到整个区间的最中间的下标值。
        int middle = start + ((end - start) >> 1);
        //对划分的左部分递归
        mergeSort(a, start, middle);
        //对划分的右部分递归
        mergeSort(a, middle+1, end);
        //真正在排序的方法
        merge(a, start, middle, end);
    }

    //这个方法在执行排序功能 ，middle为start和end最中间的下标值
    private static void merge(int[] a, int start, int middle, int end) {
        //初始化一个用于存放排序后元素的数组
        int[] temp = new int[end - start + 1];
        int i = 0;
        //左部分第一个值的下标
        int p1 = start;
        //右部分第一个值的下标
        int p2 = middle + 1;
        //当p1和p2在有效范围内，选择最小的值放在新数组中
        while (p1 <= middle && p2 <= end) {
            temp[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
        }
        //下面两个while循环只会执行一个（左部分和右部分只有一个会剩下元素）
        //这个循环将左部分剩下的元素加入新数组
        while (p1 <= middle)
            temp[i++] = a[p1++];
       //这个循环将右部分剩下的元素加入新数组
        while (p2 <= end)
            temp[i++] = a[p2++];

        //将新数组中排好序的数组复制到原数组
        for (i = 0; i < temp.length; i++)
            a[start +i] = temp[i];
    }

老规矩，测试五组数据；时间如下：5ms 5ms 5ms 5ms 5ms

归并排序在数据量很大时，效率高于快速排序。归并排序是稳定的。归并排序会产生辅助数组，会消耗更多内存。

jdk为我们提供两个方法用于排序，一个是Arrays下的sort方法，另一个是Collections下的sort方法（灰常好使）。

Arrasy.sort()方法支持传入int[]，byte[]，short[]，long[]，float[]，double[]，char[]，Object[]，T；Collections.sort只能传入List<T>；

这里我们重点说Arrays.sort()。

点进去发现如下：

   public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

继续往里面进。

稍有点长，怕吓着各位，先不粘贴源码。且听我分析。

先看第一步

       //right - left代表整个数组的长度 ，QUICKSORT_THRESHOLD 为一个int值 286
      if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }

就是说当需要排序的数组长度小于286就调用sort这个方法。

我们这里先往下看大于286的情况,等下后边再看sort这个方法。

       // Check if the array is nearly sorted
        for (int k = left; k < right; run[count] = k) {
            if (a[k] < a[k + 1]) { // ascending
                while (++k <= right && a[k - 1] <= a[k]);
            } else if (a[k] > a[k + 1]) { // descending
                while (++k <= right && a[k - 1] >= a[k]);
                for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                    int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                }
            } else { // equal
                for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        sort(a, left, right, true);
                        return;
                    }
                }
            }

            //MAX_RUN_COUNT = 67
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);
                return;
            }
        }

这段代码在判断数组是否具备结构，实际逻辑是分组排序，每降序为一个组，像1,9,8,7,6,8。9到6是降序，为一个组，然后把降序的一组排成升序：1,6,7,8,9,8。然后最后的8后面继续往后面找。。。

每遇到这样一个降序组，++count，当count大于MAX_RUN_COUNT（67），被判断为这个数组不具备结构（也就是这数据时而升时而降），和之前小于286一样，调用了sort方法。

这里我们先继续看小于67的情况。

// Check special cases
        // Implementation note: variable "right" is increased by 1.
        if (run[count] == right++) { // The last run contains one element
            run[++count] = right;
        } else if (count == 1) { // The array is already sorted
            return;
        }

        // Determine alternation base for merge
        byte odd = 0;
        for (int n = 1; (n <<= 1) < count; odd ^= 1);

        // Use or create temporary array b for merging
        int[] b;                 // temp array; alternates with a
        int ao, bo;              // array offsets from 'left'
        int blen = right - left; // space needed for b
        if (work == null || workLen < blen || workBase + blen > work.length) {
            work = new int[blen];
            workBase = 0;
        }
        if (odd == 0) {
            System.arraycopy(a, left, work, workBase, blen);
            b = a;
            bo = 0;
            a = work;
            ao = workBase - left;
        } else {
            b = work;
            ao = 0;
            bo = workBase - left;
        }

        // Merging
        for (int last; count > 1; count = last) {
            for (int k = (last = 0) + 2; k <= count; k += 2) {
                int hi = run[k], mi = run[k - 1];
                for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                        b[i + bo] = a[p++ + ao];
                    } else {
                        b[i + bo] = a[q++ + ao];
                    }
                }
                run[++last] = hi;
            }
            if ((count & 1) != 0) {
                for (int i = right, lo = run[count - 1]; --i >= lo;
                    b[i + bo] = a[i + ao]
                );
                run[++last] = right;
            }
            int[] t = a; a = b; b = t;
            int o = ao; ao = bo; bo = o;
        }

大概通过注释能看出来是进行了归并排序。此处理解的比较模糊，后边有时间进行补全。

下面看看sort方法：

int length = right - left + 1;

        // 先判断数组的长度是否小于INSERTION_SORT_THRESHOLD = 47
        if (length < INSERTION_SORT_THRESHOLD) {
            if (leftmost) {        //leftmost这个参数前面传进入就为true
                //这里执行了插入排序
                for (int i = left, j = i; i < right; j = ++i) {
                    int ai = a[i + 1];
                    while (ai < a[j]) {
                        a[j + 1] = a[j];
                        if (j-- == left) {
                            break;
                        }
                    }
                    a[j + 1] = ai;
                }
            } 

数组长度大于47时代码有点多，不粘贴，大致说下；

大于47时采用快速排序的方法：
1.从数列中挑出五个元素，称为 “基准”（pivot）；
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

---

Arrays.sort（）这个static方法针对 数组的特性采用了不同的排序方法。所以使用这个方法排序效率上可能会比我们自己去写排序算法高一点。