图文并茂的排序算法

概述：

本文给出常见的几种排序算法的原理以及java实现，包括常见的简单排序和高级排序算法，以及其他常用的算法知识。

• 简单排序：冒泡排序、选择排序、插入排序
• 高级排序：快速排序、归并排序、希尔排序

冒泡排序（Bubble Sort）

冒泡排序须知： 作为最简单的排序算法之一，冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。。。冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。

原理:

1. 从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。
2. 指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。
3. 依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。
4. 依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。
5. 重复上述过程，没排完一轮，比较次数就减少一次。

例子:

待排序数据：7, 6, 9, 8, 5,1

第一轮排序过程： 指针先指向7，7和6比较，6<7，交换6和7的位置，结果为：6,7,9,8,5,1 指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6,7,9,8,5,1 指针指向第三个元素9，比较9和8，8<9，交换8和9的位置，结果为：6,7,8,9,5,1 指针指向第四个元素9，比较9和5，5<9，交换5和9，结果为：6,7,8,5,9,1 指针指向第五个元素9，比较9和1，1<9，交换1和9的位置，结果为6,7,8,5,1,9 第一轮排序结束后，最大的数字9被移到了最右边。

进行第二轮排序，过程同上，只是由于最大的9已经放在最右边了，因此不用在比较9了，少了一次比较，第二轮结束的结果为：6,7,5,1,8,9 第三轮结果：6,5,1,7,8,9 第四轮比较结果：5,1,6,7,8,9 第五轮比较结果：1,5,6,7,8,9

最终排序结果为：1,5,6,7,8,9，由上可知N个数据排序，需要进行N-1轮排序；第i轮排序需要的比较次数为N-i次。

冒泡排序动图演示：

编码思路：

需要两层循环，第一层循环end表示排序的轮数（没循环一次总次数就会减一，最后一个数不用参与循环），第二层循环i表示需要比较的数据个数（上面剩余的有效数据个数）

代码实现：

public class BubbleSortDemo {

    public static void main(String[] args) {
        int[] arr = {7, 6, 9, 8, 5,1};
        bubbleSort(arr);
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + ",");
        }
    }

    public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        
        // 每轮循环总次数减一
        for(int end = arr.length - 1; end > 0; end--) {
            // 循环和剩余的有效数据比较
            for(int i = 0; i < end; i++) {
                if(arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

什么时候最快（Best Cases）：O(n2) 当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊。。。。）

什么时候最慢（Worst Cases）： 当输入的数据是反序时（写一个for循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗。。。）

冒泡排序算法总结：

• N个元素需要排序N-1轮；
• 第i轮需要比较N-i次；
• N个元素排序，需要比较n（n-1）/2次；
• 冒泡排序的算法复杂度较高，为O（n2）

选择排序（Selection Sort）

选择排序是对冒泡排序的改进，它的比较次数与冒泡排序相同，但交换次数要小于冒泡排序。当数据量较大时，效率会有很大的提升，但时间复杂度仍为O(n*n)

选择排序须知： 在时间复杂度上表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

原理：

1. 从第一个元素开始，分别与后面的元素向比较，找到最小的元素与第一个元素交换位置；
2. 从第二个元素开始，分别与后面的元素相比较，找到剩余元素中最小的元素，与第二个元素交换；
3. 重复上述步骤，直到所有的元素都排成由小到大为止。

例子： 待比较数据：7, 6, 9, 8, 5,1

第一轮：此时指针指向第一个元素7，找出所有数据中最小的元素，即1，交换7和1的位置，排序后的数据为：1,6,9,8,5,7

第二轮：第一个元素已经为最小的元素，此时指针指向第二个元素6，找到6,9,8,5,7中最小的元素，即5，交换5和6的位置，排序后的结果为：1,5,9,8,6,7

第三轮：前两个元素为排好序的元素，此时指针指向第三个元素9，找到9,8,6,7中最小的元素，即6，交换6和9的位置，排序后的结果为：1,5,6,8,9,7 第四轮：前三个元素为排好序的元素，此时指针指向第四个元素8，找到8,9,7中最小的元素，即7，交换8和7的位置，排序后的结果为：1,5,6,7,9,8 第五轮：前四个元素为排好序的元素，此时指针指向第五个元素9，找到9,8中最小的元素，即8，交换9和8的位置，排序后的结果为：1,5,6,7,8,9 到此，全部排序完成。

分析：从上面的原理可以看出，与冒泡排序不同，选择排序每排完一轮都把最小的元素移到了最左面，然后下一轮排序的比较次数比上一轮减少一次，即第i轮排序需要比较N-i次。因此，和冒泡排序一样，N个数据比较大小，需要排序N-1轮，第i轮排序需要比较N-i次。

选择排序动图演示：

编码思路： 需要两次循环，第一层循环i表示每轮指针指向的位置，将最小值min初始化为第i个元素，第二层循环从j=i+1开始，分别与min比较，如果小于min，则更新min的值，内层循环结束后；交换min元素和第i个元素的位置。以此类推进行下一轮循环，直到i=length时停止循环。当i=length时，说明小的元素已经全部移到了左面，因此无需进行内层循环了。

代码实现：

public class SelectionSortDemo {
    public static void main(String[] args) {
        int[] arr = {7, 6, 9, 8, 5,1};

        selectionSort(arr);

        for(int i = 0; i<arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }

    public static void selectionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        for(int i = 0; i < arr.length -1; i++) {
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++) {
               minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }

            swap(arr, i, minIndex);

        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

选择排序算法总结：

• N个元素需要排序N-1轮；
• 第i轮需要比较N-i次；
• N个元素排序，需要比较n（n-1）/2次；
• 选择排序的算法复杂度仍为O（n*n）；
• 相比于冒泡排序，选择排序的交换次数大大减少，因此速度要快于冒泡`排序

插入排序

插入排序是简单排序中最快的排序算法，虽然时间复杂度仍然为O(n*n)，但是却比冒泡排序和选择排序快很多。

插入排序须知： 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。当然，如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌，那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。对于这种算法，得了懒癌的我就套用教科书上的一句经典的话吧：感兴趣的同学可以在课后自行研究。。。

原理：

1. 将指针指向某个元素，假设该元素左侧的元素全部有序，将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，遇到比其大的元素便将元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止；
2. 此时会出现一个空位，将该元素放入到空位中，此时该元素左侧的元素都比它小，右侧的元素都比它大；
3. 指针向后移动一位，重复上述过程。每操作一轮，左侧有序元素都增加一个，右侧无序元素都减少一个。

例子： 待比较数据：7, 6, 9, 8, 5,1

第一轮：指针指向第二个元素6，假设6左面的元素为有序的，将6抽离出来，形成7,,9,8,5,1，从7开始，6和7比较，发现7>6。将7右移，形成,7,9,8,5,1，6插入到7前面的空位，结果：6,7,9,8,5,1

第二轮：指针指向第三个元素9，此时其左面的元素6,7为有序的，将9抽离出来，形成6,7,_,8,5,1，从7开始，依次与9比较，发现9左侧的元素都比9小，于是无需移动，把9放到空位中，结果仍为：6,7,9,8,5,1

第三轮：指针指向第四个元素8，此时其左面的元素6,7,9为有序的，将8抽离出来，形成6,7,9,,5,1，从9开始，依次与8比较，发现8<9，将9向后移，形成6,7,,9,5,1，8插入到空位中，结果为：6,7,8,9,5,1

第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1。

第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9。

编码分析: 需要两层循环，第一层循环index表示上述例子中的指针，即遍历从坐标为1开始的每一个元素；第二层循环从leftindex=index-1开始，leftindex--向左遍历，将每一个元素与i处的元素比较，直到j处的元素小于i出的元素或者leftindex<0；遍历从i到j的每一个元素使其右移，最后将index处的元素放到leftindex处的空位处。

插入排序动图演示：

代码实现：

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {7, 6, 9, 8, 5,1};

        insertionSort(arr);

        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }

    public static void insertionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        for (int index = 1; index < arr.length; index++) {
            for(int leftindex = index -1; leftindex >= 0 && arr[leftindex] > arr[leftindex + 1]; leftindex--) {
                swap(arr, leftindex, leftindex + 1);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}