Java 实现常见内排序

一、内排序

1、排序基本概念

（1）什么是排序？
　　排序指将一个数据元素集合或者序列按照某种规则重新排列成一个有序的集合或者序列。分为内排序、外排序。排序算法的好坏直接影响程序的执行速度以及存储空间的占有量。

（2）什么是内排序？外排序？
　　内排序：指待排序的序列完全存放在内存中所进行的排序过程（不适合大量数据排序）。
　　外排序：指大数据的排序，待排序的数据无法一次性读取到内存中，内存与外存需进行多次数据交换，以达到排序的目的。

（3）什么是稳定排序？
　　稳定排序指的是相等的数据经过某种排序算法排序后，仍能保证它们的相对顺序与未排序之前相同。
　　比如一个序列 a1 a2 a3 a4 a5，且 a1 < a2 = a3 < a4 < a5。
　　若经过某种排序算法后，结果仍为 a1 < a2 = a3 < a4 < a5，那么该排序算法是稳定的。
　　若经过某种排序算法后，结果为 a1 < a3 = a2 < a4 < a5，那么该排序算法是不稳定的。

2、内排序分类

（1）按种类划分：
　　插入排序：直接插入排序、希尔排序。
　　选择排序：选择排序、堆排序。
　　交换排序：冒泡排序、快速排序。
　　归并排序：归并排序。

（2）按稳定排序划分：
　　稳定排序：冒泡排序、归并排序、直接插入排序。
　　非稳定排序：快速排序、希尔排序、堆排序、选择排序。

（3）比较：

排序算法        最好时间        平均时间        最坏时间       　　 空间复杂度        稳定性

直接插入排序     O(n)           O(n^2)         O(n^2)        　　  O(1)           稳定

希尔排序        O(n)           O(nlogn)       O(n^s) (1<s<2)      O(1)          不稳定

选择排序        O(n^2)         O(n^2)         O(n^2)              O(1)          不稳定

堆排序         O(nlogn)        O(nlogn)       O(nlogn)            O(1)          不稳定

冒泡排序        O(n)           O(n^2)         O(n^2)              O(1)           稳定

快速排序        O(nlogn)       O(nlogn)       O(n^2)              O(logn)        不稳定

归并排序        O(nlogn)       O(nlogn)       O(nlogn)            O(n)           稳定

二、内排序 -- 稳定排序

1、冒泡排序（Bubble Sort）

（1）基本原理：（以升序为例）
　　对于给定n个数据，从第一个数据开始，与相邻的数据比对，若当前数据大于后面数据，则交换位置，否则不交换位置，然后接着从相邻位置处开始与后一位置的数据比较，直至到最后一个数据，经一次冒泡过程后，n个数据中最大的数在第n位置上。同理，接下来的冒泡是对前 n-1 个数据进行比较。

（2）举例：

【给数据 {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】

第一次冒泡：

    Step1: 比较 38 和 65, 38 < 65, 不交换位置。当前数据顺序 38 65 97 76 13 27 49

    Step2: 比较 65 和 97, 65 < 97, 不交换位置。当前数据顺序 38 65 97 76 13 27 49

    Step3: 比较 97 和 76, 97 > 76, 交换位置。当前数据顺序 38 65 76 97 13 27 49

    Step4: 比较 97 和 13, 97 > 13, 交换位置。当前数据顺序 38 65 76 13 97 27 49

    Step5: 比较 97 和 27, 97 > 27, 交换位置。当前数据顺序 38 65 76 13 27 97 49

    Step6: 比较 97 和 49, 97 > 49, 交换位置。当前数据顺序 38 65 76 13 27 49 97

经过第一次冒泡，得到最大的数 97，且在最右侧。

接下来只需同理在 除了 97 这个数据的集合中选出最大值即可。

第二次冒泡：

    当前数据顺序 38 65 13 27 49 76 97

第三次冒泡：

    当前数据顺序 38 13 27 49 65 76 97

第四次冒泡：

    当前数据顺序 13 27 38 49 65 76 97

第五次冒泡：

    当前数据顺序 13 27 38 49 65 76 97

第六次冒泡：

    当前数据顺序 13 27 38 49 65 76 97

（3）代码：

【src/sort/BubbleSort.java】

package sort;

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {

        int[] arrays = new int[] {38, 65, 97, 76, 13, 27, 49};

        System.out.println("=================从小到大排列====================");

        System.out.println("冒泡排序前：" + Arrays.toString(arrays));

        bubbleSort(arrays,false);

        System.out.println("冒泡排序后：" + Arrays.toString(arrays));

        System.out.println("================================================");

        System.out.println("=================数据有序时，最小时间复杂度 O(n)====================");

        System.out.println("冒泡排序前：" + Arrays.toString(arrays));

        bubbleSort(arrays,false);

        System.out.println("冒泡排序后：" + Arrays.toString(arrays));

        System.out.println("================================================");

        System.out.println("=================从大到小排列====================");

        System.out.println("冒泡排序前：" + Arrays.toString(arrays));

        bubbleSort(arrays,true);

        System.out.println("冒泡排序后：" + Arrays.toString(arrays));

        System.out.println("================================================");

    }

    /**

     * 冒泡排序，此方法用于 将数组排序，从小到大（或从大到小）输出。

     * 交换规则未采用第三方变量，是采用 A = A + B; B = A - B; A = A - B; 的形式。

     * @param arrays 待排序的数组

     * @param reverse 冒泡规则。 true（表示从大到小排序），false（表示从小到大排序）

     */

    public static void bubbleSort(int[] arrays, boolean reverse) {

        // 用于判断当前数组是否有序，true表示无序，需要进行排序，false表示有序，不用排序

        boolean sortFlag = false;

        // 第一个循环用于定义执行冒泡的次数， n 个数据需执行 n-1 次冒泡

        for(int i = 0; i < arrays.length - 1; i++) {

            // 第二个循环用于定义每次冒泡时比较的次数，第 i 次冒泡，需比较 n - i 次

            for(int j = 0; j < arrays.length - 1 - i; j++) {

                if (!reverse) {

                    // 比较数据，将大的数据向后移动

                    if (arrays[j] > arrays[j+1]) {

                        arrays[j] += arrays[j+1];

                        arrays[j+1] = arrays[j] - arrays[j+1];

                        arrays[j] -= arrays[j+1];

                        // 发生数据比较时，设标志为 true，即当前数据需要进行排序操作

                        sortFlag = true;

                    }

                } else {

                    // 比较数据，将小的数据向后移动

                    if (arrays[j] < arrays[j+1]) {

                        arrays[j] += arrays[j+1];

                        arrays[j+1] = arrays[j] - arrays[j+1];

                        arrays[j] -= arrays[j+1];

                        sortFlag = true;

                    }

                }

            }

            System.out.println("第" + (i + 1) + "次冒泡：" + Arrays.toString(arrays));

            // 当排序标志为 false时，即第一次冒泡确认数据不需要排序，直接退出循环，不进行接下来的冒泡操作

            if (!sortFlag) {

                break;

            }

        }

    }

}

（4）输出结果

=================从小到大排列====================

冒泡排序前：[38, 65, 97, 76, 13, 27, 49]

第1次冒泡：[38, 65, 76, 13, 27, 49, 97]

第2次冒泡：[38, 65, 13, 27, 49, 76, 97]

第3次冒泡：[38, 13, 27, 49, 65, 76, 97]

第4次冒泡：[13, 27, 38, 49, 65, 76, 97]

第5次冒泡：[13, 27, 38, 49, 65, 76, 97]

第6次冒泡：[13, 27, 38, 49, 65, 76, 97]

冒泡排序后：[13, 27, 38, 49, 65, 76, 97]

================================================

=================数据有序时，最小时间复杂度 O(n)====================

冒泡排序前：[13, 27, 38, 49, 65, 76, 97]

第1次冒泡：[13, 27, 38, 49, 65, 76, 97]

冒泡排序后：[13, 27, 38, 49, 65, 76, 97]

================================================

=================从大到小排列====================

冒泡排序前：[13, 27, 38, 49, 65, 76, 97]

第1次冒泡：[27, 38, 49, 65, 76, 97, 13]

第2次冒泡：[38, 49, 65, 76, 97, 27, 13]

第3次冒泡：[49, 65, 76, 97, 38, 27, 13]

第4次冒泡：[65, 76, 97, 49, 38, 27, 13]

第5次冒泡：[76, 97, 65, 49, 38, 27, 13]

第6次冒泡：[97, 76, 65, 49, 38, 27, 13]

冒泡排序后：[97, 76, 65, 49, 38, 27, 13]

================================================

（5）分析：
　　分析上面的代码、数据。
　　若数据中出现相同的值，且相同值比较的过程中不会出现交换值的情况，故排序是稳定的。
　　当数据有序时，即排序前后数据顺序一致的情况。此时需要执行 1 次冒泡（用于确认是否需要进行排序），进行 n - 1 次比较，但是不会进行数据交换。此时为最好的情况，时间复杂度为 O(n-1)，即 O(n)。
　　当数据反序时，即排序前后数据顺序正好相反的情况。此时需要执行 n - 1 次冒泡，且第 i 次冒泡就得执行 n - i 次比较，然后执行数据交换操作。此时为最坏的情况，时间复杂度为 O(1 + 2 + ... + n - 1) = O(n(n-1)/2) ，即 O(n^2)。
　　至于空间复杂度，指的就是算法中所需要的辅助空间。如上述代码中，空间复杂度为0，若进行数据交换的代码采用第三方变量的形式，那么空间复杂度为 O(1)。

【空间复杂度为0：】

a = a + b;

b = a - b;

a = a - b;

【空间复杂度为1：】

t = a;

a = b;

b = t;

2、直接插入排序（Insertion Sort）

（1）基本原理：
　　对于给定的一组数据，初始时假设第一个元素为一个有序序列，其余元素为无序序列，从第二个数据开始，按照大小将该数据插入有序序列中，形成一个新有序序列，同理直至最后一个数据插入有序序列中。

（2）举例：

【给数据 {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】

第一次插入：

    将原序列分为 {38} 、{65, 97, 76, 13, 27, 49}两个序列，

    将无序序列第一个数 （65） 插入到有序序列中。

    得 {38, 65}、 {97, 76, 13, 27, 49} 两个序列。

同理

第二次插入（97）：

    得 {38, 65, 97}、{76, 13, 27, 49} 

第三次插入（76）：

    得 {38, 65, 76, 97}、{13, 27, 49}

第四次插入（13）：

    得 {13, 38, 65, 76, 97}、{27, 49}

第五次插入（27）：

    得：{13, 27, 38, 65, 76, 97}、{49}

第六次插入（49）：

    得： {13, 27, 38, 49, 65, 76, 97}

（3）代码：

【src/sort/InsertionSort.java】

package sort;

import java.util.Arrays;

public class InsertionSort {

    public static void main(String[] args) {

        int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49};

        System.out.println("=================从小到大排列====================");

        System.out.println("直接插入排序前：" + Arrays.toString(arrays));

        insertionSort(arrays, false);

        System.out.println("直接插入排序后：" + Arrays.toString(arrays));

        System.out.println("================================================");

        System.out.println("=================数据有序时，最小时间复杂度 O(n)====================");

        System.out.println("直接插入排序前：" + Arrays.toString(arrays));

        insertionSort(arrays, false);

        System.out.println("直接插入排序后：" + Arrays.toString(arrays));

        System.out.println("================================================");

        System.out.println("=================从大到小排列====================");

        System.out.println("直接插入排序前：" + Arrays.toString(arrays));

        insertionSort(arrays, true);

        System.out.println("直接插入排序后：" + Arrays.toString(arrays));

        System.out.println("================================================");

    }

    /**

     * 直接插入排序，此方法用于 将数组排序，从小到大（或从大到小）输出。

     * @param arrays 待排序的数组

     * @param reverse 插入规则。 true（表示从大到小排序），false（表示从小到大排序）

     */

    public static void insertionSort(int[] arrays, boolean reverse) {

        // 第一个循环用于定义执行直接插入的次数， n 个数据需执行 n-1 次插入

        for(int i = 1; i <= arrays.length - 1; i++) {

            int temp = arrays[i];

            int j = i;

            if (!reverse) {

                if (temp < arrays[j-1]) {

                    // 第二个循环用于定义直接插入的位置

                    while(j > 0 && temp < arrays[j-1]) {

                        arrays[j] = arrays[j-1];

                        j--;

                    }

                    // 直接插入的真正操作

                    arrays[j] = temp;

                }

            } else {

                if (temp > arrays[j-1]) {

                    while(j > 0 && temp > arrays[j-1]) {

                        arrays[j] = arrays[j-1];

                        j--;

                    }

                    arrays[j] = temp;

                }

            }

            System.out.println("第" + i + "次插入：" + Arrays.toString(arrays));

        }

    }

}

（4）结果：

=================从小到大排列====================

直接插入排序前：[38, 65, 97, 76, 13, 27, 49]

第1次插入：[38, 65, 97, 76, 13, 27, 49]

第2次插入：[38, 65, 97, 76, 13, 27, 49]

第3次插入：[38, 65, 76, 97, 13, 27, 49]

第4次插入：[13, 38, 65, 76, 97, 27, 49]

第5次插入：[13, 27, 38, 65, 76, 97, 49]

第6次插入：[13, 27, 38, 49, 65, 76, 97]

直接插入排序后：[13, 27, 38, 49, 65, 76, 97]

================================================

=================数据有序时，最小时间复杂度 O(n)====================

直接插入排序前：[13, 27, 38, 49, 65, 76, 97]

第1次插入：[13, 27, 38, 49, 65, 76, 97]

第2次插入：[13, 27, 38, 49, 65, 76, 97]

第3次插入：[13, 27, 38, 49, 65, 76, 97]

第4次插入：[13, 27, 38, 49, 65, 76, 97]

第5次插入：[13, 27, 38, 49, 65, 76, 97]

第6次插入：[13, 27, 38, 49, 65, 76, 97]

直接插入排序后：[13, 27, 38, 49, 65, 76, 97]

================================================

=================从大到小排列====================

直接插入排序前：[13, 27, 38, 49, 65, 76, 97]

第1次插入：[27, 13, 38, 49, 65, 76, 97]

第2次插入：[38, 27, 13, 49, 65, 76, 97]

第3次插入：[49, 38, 27, 13, 65, 76, 97]

第4次插入：[65, 49, 38, 27, 13, 76, 97]

第5次插入：[76, 65, 49, 38, 27, 13, 97]

第6次插入：[97, 76, 65, 49, 38, 27, 13]

直接插入排序后：[97, 76, 65, 49, 38, 27, 13]

================================================

（5）分析：
　　分析上面的代码、数据。
　　若数据中出现相同的值，且相同值比较的过程中不会出现交换值的情况，故排序是稳定的。
　　当数据有序时，即排序前后数据顺序一致的情况。此时需要执行 n - 1 次插入操作，但是不会进行数据的交换。此时为最好的情况，时间复杂度为 O(n-1)，即 O(n)。
　　当数据反序时，即排序前后数据顺序正好相反的情况。此时需要执行 n - 1 次插入操作，且第 i 次插入需要进行 i 次数据比较。此时为最坏的情况，时间复杂度为 O(1 + 2 + ... + n - 1) = O(n(n-1)/2) ，即 O(n^2)。
　　上述代码，采用第三方变量用于保存交换的数据，故空间复杂度为 O(1)。

3、归并排序（Merge Sort）

（1）基本原理：
　　采用分治法，将数据序列分成足够小的子序列，并使每个子序列有序，最后将子序列合并成一个完整有序的序列，此处介绍2路归并。
　　分治法：就是把一个复杂的问题分解成两个或多个相似的子问题，然后根据需要将子问题分解成更小的子问题，直至子问题可以简单地解决，子问题的解的集合即为原问题的解。
2路归并：采用分治法，将一个数据序列分为两个子序列（子序列还可分为更小的子序列），并分别进行排序，最后将两个有序子序列合成一个有序序列。

（2）举例：

【给数据 {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】

第一次划分：

    将原序列分为 A：{38, 65, 97, 76} 、B：{13, 27, 49} 两个子序列。

对序列 A 划分：

    分为 A1：{38， 65}， A2：{97， 76} 两个子序列。

再对 A1 划分：

    分为 A11：{38}、A12：{65} 两个子序列。

此时 A11、A12 已经足够小，可以合并成有序序列：

    A1：{38, 65}

对 A2 划分：

    分为 A21：{97}、A22：{76} 两个子序列。

此时 A21、A22 已经足够小，可以合并成有序序列：

    A2：{76, 97}

合并 A1、A2：

    A：{38, 65, 76, 97}

同理划分并合并 B：

    B：{13， 27， 49}

合并 A、B：

    {13, 27, 38, 49, 65, 76, 97}

形如：

                {38, 65, 97, 76, 13, 27, 49}

    划分：

            {38, 65, 97, 76}        {13, 27, 49}

          {38, 65}    {97, 76}     {13, 27}   {49}

         {38}  {65}  {97}  {76}   {13}  {27}   {49}

    合并：

         {38, 65}     {76, 97}   {13, 27}   {49}

             {38, 65, 76, 97}     {13, 27, 49}

                {13, 27, 38, 49, 65, 76, 97}

（3）代码：

【src/sort/MergeSort.java】

package sort;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {

        int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49};

        // 原序列

        System.out.println("====================原序列=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

        int[] result = mergeSort(arrays);

        // 归并排序后的序列

        System.out.println("==============归并排序后的序列===================");

        System.out.println(Arrays.toString(result));

        System.out.println("================================================");

    }

    /**

     * 用于划分序列

     * Arrays.copyOfRange(T[ ] original,int from,int to) 用于将一个原数组复制到一个新数组，数据范围为 from <= x < to。

     */

    public static int[] mergeSort(int[] arrays) {

        // 如果序列已经足够小，可以返回该序列并进行合并

        if (arrays.length < 2)

            return arrays;

        // 若序列还可划分，则继续划分

        int[] left = Arrays.copyOfRange(arrays, 0, (arrays.length + 1) / 2);

        int[] right = Arrays.copyOfRange(arrays, (arrays.length + 1) / 2, arrays.length);

        // 划分到最小序列后，得合并序列

        return merge(mergeSort(left), mergeSort(right));

    }

    /**

     * 用于合并序列。

     * Arrays.toString(T[]) 用于输出一个数组。

     */

    public static int[] merge(int[] left, int[] right) {

        // 用于保存合并后的序列

        int[] result = new int[left.length + right.length];

        // 循环将数据填入新数组中，index 用于表示新序列当前位置，i 表示 left 序列数据位置，j 表示 right 序列数据位置。

        for (int index = 0, i = 0, j = 0; index < result.length; index++) {

            if (i >= left.length) {

                // 如果 left 序列已经填入完毕，则新序列后面的数据将由 right 填充。

                result[index] = right[j++];

            } else if (j >= right.length) {

                // 如果 right 序列已经填入完毕，则新序列后面的数据将由 left 填充。

                result[index] = left[i++];

            } else if (left[i] > right[j]) {

                // 如果 left、right 数据均未填充完毕，则比较当前数据，将较小的数据填入

                result[index] = right[j++];

            } else {

                // 如果 left、right 数据均未填充完毕，则比较当前数据，将较大的数据填入

                result[index] = left[i++];

            }

        }

        // 划分后的 left 序列

        System.out.println("left:" + Arrays.toString(left));

        // 划分后的 right 序列

        System.out.println("right" + Arrays.toString(right));

        // 合并的 result 序列

        System.out.println("result" + Arrays.toString(result));

        System.out.println();

        return result;

    }

}

（4）结果：

====================原序列=====================

[38, 65, 97, 76, 13, 27, 49]

================================================

left:[38]

right[65]

result[38, 65]

left:[97]

right[76]

result[76, 97]

left:[38, 65]

right[76, 97]

result[38, 65, 76, 97]

left:[13]

right[27]

result[13, 27]

left:[13, 27]

right[49]

result[13, 27, 49]

left:[38, 65, 76, 97]

right[13, 27, 49]

result[13, 27, 38, 49, 65, 76, 97]

==============归并排序后的序列===================

[13, 27, 38, 49, 65, 76, 97]

================================================

（5）分析：
　　分析上面的代码、数据。
　　若数据中出现相同的值，且相同值比较的过程中不会出现交换值的情况，故排序是稳定的。
　　无论数据是否有序，都会进行划分操作余合并操作。划分操作最后形如二叉树，而二叉树的高度为 floor(logn) + 1，合并操作每层的操作均为 n，即时间复杂度为 O(n * ( floor(logn) + 1)) = O(nlogn)。即最好最坏的时间复杂度均为 O(nlogn)。

三、内排序 -- 非稳定排序

1、快速排序（Quick Sort）

（1）基本原理：
　　采用分治法，选择一个基准，通过一趟排序，将一组序列分成左右两个序列，且左边的序列均小于右边的序列，再分别对左右序列进行类似的排序，分成更小的左右序列，直至所有的序列有序。

注：
　　快速排序与归并排序的区别：
　　快速排序主旨是根据元素的值划分，大的序列为一组，小的序列为一组，然后对两个序列进行进一步的划分，最后直接合并序列即可得到有序的序列。即先排序、再递归细分序列。
　　归并排序主旨是根据元素的数量划分，比如 2n 个数对半切开（2路归并），下标为 0 ~ n 的数为一组，下标 n ~ 2n 的数为一组，然后对两个序列进行进一步的划分，最后需要两个序列相互比较后，合并成一个有序的序列。即先递归细分序列、再排序。

（2）举例：（双路快排）
　　双路快排：从序列的两端向中间挺近，建立两个区，一个小于等于区（左侧），一个大于等于区（右侧）。先从某一侧开始，比如从右侧开始，若出现值小于基准值，则需将值交换到左侧，并从左侧开始逼近。当左侧出现大于基准值，则需将值交换到右侧，并从右侧开始逼近。如此往复，直至左侧与右侧出现重合，此时重合点即为新的基准点。

【给数据 {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】

双路快排从两端向中间靠近，设两个值 start、end.

对于第一趟排序，首先选择第一个值作为基准，选 index = 38，start = 0, end = 7。

从右侧开始向中间逼近：

    38 < 49, 不用交换。end--

    38 > 37, 需要交换。此时序列为 {27, 65, 97, 76, 13, 27, 49}。start++

从左侧开始向中间逼近：

    38 < 65, 需要交换。此时序列为 {27, 65, 97, 76, 13, 65, 49}。end--

从右侧开始向中间逼近：

    38 > 13, 需要交换。此时序列为 {27, 13, 97, 76, 13, 65, 49}。start++

从左侧开始向中间逼近：

    38 < 97, 需要交换。此时序列为 {27, 13, 97, 76, 97, 65, 49}。end--

从右侧开始向中间逼近：

    38 < 76, 不用交换。end--

此时 start 与 end 重合，即出现新的基准点，将基准值交换到此处，序列为 {27, 13, 38, 76, 97, 65, 49}

同理对 {27, 13, 38}、{76, 97, 65, 49}进行排序。

最终得到序列 {13, 27, 38, 49, 65, 76, 97}

（3）代码：

【src/sort/QuickSort.java】

package sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {

        int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49};

        System.out.println("====================原序列=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

        quickSort(arrays, 0, arrays.length - 1);

        System.out.println("\n====================快速排序后=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

    }

    /**

     * 快速排序

     * @param arrays 待排序序列

     * @param start 序列头下标

     * @param end 序列尾下标

     */

    public static void quickSort(int[] arrays, int start, int end) {

        if (start < end) {

            // 进行一次排序，并得到新的基准下标

            int index = getIndex(arrays, start, end);

            // 对基准左侧进行排序

            if (index > start) {

                quickSort(arrays, start, index - 1);

            }

            // 对基准右侧进行排序

            if (index < end) {

                quickSort(arrays, index + 1, end);

            }

        }

    }

    /**

     * 双路快排，并获取基准下标

     * @param arrays 待排序的序列

     * @param start 序列头下标

     * @param end 序列尾下标

     * @return 返回基准下标

     */

    public static int getIndex(int[] arrays, int start, int end) {

        // 选取序列第一个值为基准

        int index = arrays[start];

        // 开始从两边向中间比较

        while (start < end) {

            // 从右侧向中间逼近

            while (start < end && arrays[end] >= index) {

                end--;

            }

            // 如果 arrays[end] < index，即右侧出现小于基准的值，则将该值交换到左侧，且左侧下标增1

            if (start < end) {

                arrays[start++] = arrays[end];

                // 打印右侧逼近过程

                System.out.println("\n====start====" + start + "====end====" + end + "====基准值====" + index);

                System.out.println(Arrays.toString(arrays));

            }

            // 从左侧向中间逼近

            while (start < end && arrays[start] <= index) {

                start++;

            }

            // 如果 arrays[start] > index，即左侧出现大于基准的数，将该值交换到右侧，且右侧下标减1

            if (start < end) {

                arrays[end--] = arrays[start];

                // 打印左侧逼近过程

                System.out.println("\n====start====" + start + "====end====" + end + "====基准值====" + index);

                System.out.println(Arrays.toString(arrays));

            }

        }

        // start >= end，即新基准下标出现，将基准值替换到中间

        arrays[start] = index;

        // 打印一次排序后的结果

        System.out.println("\n====一次排序后的序列====");

        System.out.println(Arrays.toString(arrays));

        // 返回新的基准下标

        return start;

    }

}

（4）结果：

====================原序列=====================

[38, 65, 97, 76, 13, 27, 49]

================================================

====start====1====end====5====基准值====38

[27, 65, 97, 76, 13, 27, 49]

====start====1====end====4====基准值====38

[27, 65, 97, 76, 13, 65, 49]

====start====2====end====4====基准值====38

[27, 13, 97, 76, 13, 65, 49]

====start====2====end====3====基准值====38

[27, 13, 97, 76, 97, 65, 49]

====一次排序后的序列====

[27, 13, 38, 76, 97, 65, 49]

====start====1====end====1====基准值====27

[13, 13, 38, 76, 97, 65, 49]

====一次排序后的序列====

[13, 27, 38, 76, 97, 65, 49]

====start====4====end====6====基准值====76

[13, 27, 38, 49, 97, 65, 49]

====start====4====end====5====基准值====76

[13, 27, 38, 49, 97, 65, 97]

====start====5====end====5====基准值====76

[13, 27, 38, 49, 65, 65, 97]

====一次排序后的序列====

[13, 27, 38, 49, 65, 76, 97]

====一次排序后的序列====

[13, 27, 38, 49, 65, 76, 97]

====================快速排序后=====================

[13, 27, 38, 49, 65, 76, 97]

================================================

（5）分析：
　　分析上面的代码、数据。

若数据中出现相同的值，比如：{38, 65, 97, 76, 13, 27, 13}

经过第一次快排，最后一位的 13 移到第一位，

此时，两个13的先后顺序已经发生了变化，即排序是非稳定的。

　　最优时，时间复杂度计算类似于归并排序，即 O(nlogn)。
　　最坏时，代码中出现双层循环，时间复杂度会退化成 O(n^2)。

2、选择排序（Selection Sort）

（1）基本原理：
　　简单直观的排序，给定一组序列，从序列中选出最小的值与第一个元素交换位置，从剩余元素中选出最小的值与第二个元素交换位置，同理，直至剩下最后一个数据。

（2）举例：

【给数据 {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】

第一次排序：

    最小值为 13，交换后得：{13, 65, 97, 76, 38, 27, 49}

第二次排序：

    最小值为 27，交换后得：{13, 27, 97, 76, 38, 65, 49}

第三次排序：

    最小值为 38，交换后得：{13, 27, 38, 76, 97, 65, 49}

第四次排序：

    最小值为 49，交换后得：{13, 27, 38, 49, 97, 65, 76}

第五次排序：

    最小值为 65，交换后得：{13, 27, 38, 49, 65, 97, 76}

第六次排序：

    最小值为 76，交换后得：{13, 27, 38, 49, 65, 76，97}

（3）代码：

【src/sort/SelectionSort.java】

package sort;

import java.util.Arrays;

public class SelectionSort {

    public static void main(String[] args) {

        int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49};

        System.out.println("====================原序列=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

        selectionSort(arrays);

        System.out.println("\n====================选择排序后=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

    }

    /**

     * 选择排序

     * @param arrays 待排序的序列

     */

    public static void selectionSort(int[] arrays) {

        // 第一个循环定义排序的次数

        for (int i = 0; i < arrays.length - 1; i++) {

            // 用于保存最小值的下标

            int min = i;

            // 第二个循环用于比较出最小值的位置

            for (int j = i + 1; j <= arrays.length - 1; j++) {

                // 找到最小值的下标

                if (arrays[min] > arrays[j]) {

                    min = j;

                }

            }

            // 交换值，第 i 次排序，最小值与第 i 个值交换

            swap(arrays, i, min);

            // 打印排序过程

            System.out.println("\n============第" + (i + 1) + "次排序=============");

            System.out.println(Arrays.toString(arrays));

        }

    }

    /**

     * 交换序列中的两个值

     * @param arrays 待排序的序列

     * @param oldIndex 交换值A

     * @param newIndex 交换值B

     */

    public static void swap(int[] arrays, int oldIndex, int newIndex) {

        arrays[oldIndex] += arrays[newIndex];

        arrays[newIndex] = arrays[oldIndex] - arrays[newIndex];

        arrays[oldIndex] -= arrays[newIndex];

    }

}

（4）结果：

====================原序列=====================

[38, 65, 97, 76, 13, 27, 49]

================================================

============第1次排序=============

[13, 65, 97, 76, 38, 27, 49]

============第2次排序=============

[13, 27, 97, 76, 38, 65, 49]

============第3次排序=============

[13, 27, 38, 76, 97, 65, 49]

============第4次排序=============

[13, 27, 38, 49, 97, 65, 76]

============第5次排序=============

[13, 27, 38, 49, 65, 97, 76]

============第6次排序=============

[13, 27, 38, 49, 65, 76, 97]

====================选择排序后=====================

[13, 27, 38, 49, 65, 76, 97]

================================================

（5）分析：
　　分析上面的代码、数据。
　　不管数据是否有序，其均会执行 n * n 次，即最坏、最好时间复杂度均为 O(n^2)。

若数据中出现相同的值，比如：{38, 65, 97, 38, 13, 27, 49}

第一次选择排序时选择最小值 13 与第一个值 38置换。

此时，两个 38 的先后顺序已经发生了变化，即排序是非稳定的。

3、希尔排序（Shell Sort）

（1）基本原理：
　　希尔排序又称缩小增量排序，其本质属于一种插入排序。将一个序列按照增量分成多个序列，子序列分别进行插入排序，待序列基本有序后（即增量变为1时），最后进行一个直接插入排序。

（2）举例：
　　常用增量为序列长度 / 2，直至为 1，即增量序列为 {序列长度 / 2, ... , 1}。
　　增量可以理解为步长，比如一个序列 {38, 65, 97, 76, 13, 27, 49} ，长度为 7，步长为 3，则可以将其分为序列：{38， 76， 49}、{65, 13}、{97, 27}。然后分别对子序列进行插入排序。

【给数据 {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】

增量序列为：{3, 1}

则第一次以 增量 3 划分序列为 {38， 76， 49}、{65, 13}、{97, 27}

对其进行插入排序得：{38, 49, 76}, {13, 65}, {27, 97}

即：{38, 13, 27, 49, 65, 97, 76}，此时增量 3 的插入排序执行完毕。

执行增量为 1 的插入排序，即直接插入排序，（参考上面的直接插入排序，此处省略步骤）

最后得到：{13, 27, 38, 49, 65, 76, 97}

（3）代码：

【src/sort/ShellSort.java】

package sort;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {

        int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49};

        System.out.println("====================原序列=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

        shellSort(arrays);

        System.out.println("\n====================希尔排序后=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

    }

    /**

     * 希尔排序

     * @param arrays 待排序的序列

     */

    public static void shellSort(int[] arrays) {

        // 设置增量，一般为 序列长度 / 2

        int interval = arrays.length/2;

        // 对每个增量进行插入排序

        while(interval > 0) {

            // 根据增量去定义执行插入排序的次数，与直接插入排序类似，直接插入排序步长为1，此处步长为 interval

            for (int i = interval, j, temp; i < arrays.length; i++) {

                // 用于保存当前待插入的值

                temp = arrays[i];

                // 每次向前减 interval，用于确定插入的位置

                j = i - interval;

                while(j >= 0 && arrays[j] > temp) {

                    // 找到该位置，并将值向后移

                    arrays[j + interval] = arrays[j];

                    j -= interval;

                }

                // 插入的真正操作

                arrays[j + interval] = temp;

                // 打印排序过程

                System.out.println("\n==========interval====" + interval + "==========");

                System.out.println(Arrays.toString(arrays));

            }

            // 增量每次递减

            interval /= 2;

        }

    }

}

（4）结果：

====================原序列=====================

[38, 65, 97, 76, 13, 27, 49]

================================================

==========interval====3==========

[38, 65, 97, 76, 13, 27, 49]

==========interval====3==========

[38, 13, 97, 76, 65, 27, 49]

==========interval====3==========

[38, 13, 27, 76, 65, 97, 49]

==========interval====3==========

[38, 13, 27, 49, 65, 97, 76]

==========interval====1==========

[13, 38, 27, 49, 65, 97, 76]

==========interval====1==========

[13, 27, 38, 49, 65, 97, 76]

==========interval====1==========

[13, 27, 38, 49, 65, 97, 76]

==========interval====1==========

[13, 27, 38, 49, 65, 97, 76]

==========interval====1==========

[13, 27, 38, 49, 65, 97, 76]

==========interval====1==========

[13, 27, 38, 49, 65, 76, 97]

====================希尔排序后=====================

[13, 27, 38, 49, 65, 76, 97]

================================================

（5）分析：
　　分析上面的代码、数据。

若数据中出现相同的值，比如：{38, 65, 27, 27, 13, 37, 49}

第一次希尔排序时，步长为 3， 27 与 38 交换，

此时，两个 27 的先后顺序已经发生了变化，即排序是非稳定的。

4、堆排序（Heap Sort）

（1）基本原理：
　　堆是一种树形结构，即完全二叉树。可分为最大堆、最小堆。最大堆指的是每个节点均大于其左右孩子节点（升序），最小堆指的是每个节点均小于其左右孩子节点（降序）。
　　以最大堆为例，先将序列初始化成一个堆，找到栈顶元素并与序列最后一个数据互换位置（初始化堆后，栈顶元素最大，将其放于序列末尾），接着对剩下的数据排成堆（重建堆），进行类似的操作，直至最后一个数据。

注：
　　完全二叉树的特点：若 n 个节点的完全二叉树从左到右编号（即 0 ~ n-1），
　　那么序号为 0 的节点为根节点。
　　对于第 i 个（i 从 1 开始计数）位置的节点，
　　　　其父节点的编号为 (i - 1) / 2.
　　　　其左孩子节点的编号为 2 * i + 1.
　　　　其右孩子节点的编号为 2 * i + 2.

（2）举例：

【给数据 {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】

以初始化堆为例：

结构为：

        38

     65    97

   76 13  27 49

调整初始化堆：

第一趟：比较节点 97，以及其孩子27， 49， 节点大于孩子，不用调整。

        38

     65    97

   76 13  27 49

即{38, 65, 97, 76, 13, 27, 49}

第二趟：比较节点 65，以及其孩子76， 13， 65 < 76，交换得

        38

     76    97

   65 13  27 49

即{38, 76, 97, 65, 13, 27, 49}

第三趟：由于出现交换，对交换后的点进行大顶堆化，此时比较节点65，没有孩子，不用调整。

        38

     76    97

   65 13  27 49

即{38, 76, 97, 65, 13, 27, 49}

第四趟：此时比较节点38，以及其孩子65,97， 38 <  97，交换，

此时堆序列为

       97

     76    38

   65 13  27 49

即{97, 76, 38, 65, 13, 27, 49}

第五趟：由于出现交换，对交换后的点进行大顶堆化，此时比较节点38，以及其孩子27,49， 38 < 49,交换，[97, 76, 49, 65, 13, 27, 38]

此时堆序列为

       97

     76    49

   65 13  27 38

即{97, 76, 49, 65, 13, 27, 38}

第六趟：此时比较节点38，没有孩子，不用调整。

此时堆序列为

       97

     76    49

   65 13  27 38

即{97, 76, 49, 65, 13, 27, 38}

至此，初始化堆完成。

交换根节点以及序列最大值，

此时堆序列为

       38

     76    49

   65 13  27 97

即{97, 76, 49, 65, 13, 27, 38}

同理：对除了97的元素进行堆排序。过程省略。。。

（3）代码：

【src/sort/HeapSort.java】

package sort;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {

        int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49};

        System.out.println("====================原序列=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

        buildMaxHeap(arrays);

        System.out.println("\n====================选择排序后=====================");

        System.out.println(Arrays.toString(arrays));

        System.out.println("================================================");

    }

    /**

     * 构建最大堆，初始化堆

     * @param arrays 待排序的序列

     */

    public static void buildMaxHeap(int[] arrays) {

        // 初始化堆，对每个父节点进行大堆化，调整位置

        for (int i = arrays.length / 2 - 1; i >= 0; i--) {

            // 调整父节点的位置

            adjustHeap(arrays, i, arrays.length);

        }

        // 循环将堆顶的值交换到序列末尾，并对剩余的数据进行大堆化调整

        for (int j = arrays.length - 1; j >= 0; j--) {

            // 将堆顶的值交换到序列末尾

            swap(arrays, 0, j);

            // 打印交换后的序列

            System.out.println("\n==调整最大堆==swap(" + arrays[0] + ", " + arrays[j] + ")====");

            System.out.println(Arrays.toString(arrays));

            // 将剩余数据进行大堆化

            adjustHeap(arrays, 0, j);

        }

    }

    /**

     * 调整节点的位置

     * @param arrays 待排序的序列

     * @param start 序列开始位置

     * @param length 序列的长度

     */

    public static void adjustHeap(int[] arrays, int start, int length) {

        // 保存最大值的位置，初始为父节点

        int maxIndex = start;

        // 保存父节点左孩子的位置

        int leftChildren = start * 2 + 1;

        // 保存父节点右孩子的位置

        int rightChildren = start * 2 + 2;

        // 如果左孩子存在，且大于父节点

        if (leftChildren < length && arrays[leftChildren] > arrays[maxIndex]) {

            // 记录左孩子的位置，更新最大值的位置

            maxIndex = leftChildren;

        }

        // 如果右孩子存在，且大于父节点

        if (rightChildren < length && arrays[rightChildren] > arrays[maxIndex]) {

            // 记录右孩子的位置，更新最大值的位置

            maxIndex = rightChildren;

        }

        // 如果最大值位置发生变化

        if (maxIndex != start) {

            // 交换父节点与最大值的位置

            swap(arrays, maxIndex, start);

            // 打印交换后的序列

            System.out.println("\n====swap(" + arrays[maxIndex] + ", " + arrays[start] + ")====");

            System.out.println(Arrays.toString(arrays));

            // 对新的最大值的位置进行大堆化调整

            adjustHeap(arrays, maxIndex, length);

        } else {

            // 打印无须交换的序列

            System.out.println("\n=======无须交换值======" + arrays[maxIndex]);

            System.out.println(Arrays.toString(arrays));

        }

    }

    /**

     * 交换序列中的两个值

     * @param arrays 待排序的序列

     * @param oldIndex 交换值A

     * @param newIndex 交换值B

     */

    public static void swap(int[] arrays, int oldIndex, int newIndex) {

        if (oldIndex != newIndex) {

            arrays[oldIndex] += arrays[newIndex];

            arrays[newIndex] = arrays[oldIndex] - arrays[newIndex];

            arrays[oldIndex] -= arrays[newIndex];

        }

    }

}

（4）结果：

====================原序列=====================

[38, 65, 97, 76, 13, 27, 49]

================================================

=======无须交换值======97

[38, 65, 97, 76, 13, 27, 49]

====swap(65, 76)====

[38, 76, 97, 65, 13, 27, 49]

=======无须交换值======65

[38, 76, 97, 65, 13, 27, 49]

====swap(38, 97)====

[97, 76, 38, 65, 13, 27, 49]

====swap(38, 49)====

[97, 76, 49, 65, 13, 27, 38]

=======无须交换值======38

[97, 76, 49, 65, 13, 27, 38]

==调整最大堆==swap(38, 97)====

[38, 76, 49, 65, 13, 27, 97]

====swap(38, 76)====

[76, 38, 49, 65, 13, 27, 97]

====swap(38, 65)====

[76, 65, 49, 38, 13, 27, 97]

=======无须交换值======38

[76, 65, 49, 38, 13, 27, 97]

==调整最大堆==swap(27, 76)====

[27, 65, 49, 38, 13, 76, 97]

====swap(27, 65)====

[65, 27, 49, 38, 13, 76, 97]

====swap(27, 38)====

[65, 38, 49, 27, 13, 76, 97]

=======无须交换值======27

[65, 38, 49, 27, 13, 76, 97]

==调整最大堆==swap(13, 65)====

[13, 38, 49, 27, 65, 76, 97]

====swap(13, 49)====

[49, 38, 13, 27, 65, 76, 97]

=======无须交换值======13

[49, 38, 13, 27, 65, 76, 97]

==调整最大堆==swap(27, 49)====

[27, 38, 13, 49, 65, 76, 97]

====swap(27, 38)====

[38, 27, 13, 49, 65, 76, 97]

=======无须交换值======27

[38, 27, 13, 49, 65, 76, 97]

==调整最大堆==swap(13, 38)====

[13, 27, 38, 49, 65, 76, 97]

====swap(13, 27)====

[27, 13, 38, 49, 65, 76, 97]

=======无须交换值======13

[27, 13, 38, 49, 65, 76, 97]

==调整最大堆==swap(13, 27)====

[13, 27, 38, 49, 65, 76, 97]

=======无须交换值======13

[13, 27, 38, 49, 65, 76, 97]

==调整最大堆==swap(13, 13)====

[13, 27, 38, 49, 65, 76, 97]

=======无须交换值======13

[13, 27, 38, 49, 65, 76, 97]

====================选择排序后=====================

[13, 27, 38, 49, 65, 76, 97]

================================================

（5）分析：
　　分析上面的代码、数据。

若数据中出现相同的值，比如：{38, 13, 13, 76, 36, 37, 49}

        38

     13    13

   76 36  27 49

此时进行初始化堆第一次时，13， 76， 36比较，交换 13， 76，得

        38

     76    13

   13 36  27 49

此时序列为：{38, 76, 13, 13, 36, 37, 49}，两个 13 的顺序已发生变化，故排序是非稳定的。

巴特西

Java 实现常见内排序

一、内排序

1、排序基本概念

2、内排序分类

二、内排序 -- 稳定排序

1、冒泡排序（Bubble Sort）

2、直接插入排序（Insertion Sort）

3、归并排序（Merge Sort）

三、内排序 -- 非稳定排序

1、快速排序（Quick Sort）

2、选择排序（Selection Sort）

3、希尔排序（Shell Sort）

4、堆排序（Heap Sort）

最新文章

热门文章

巴特西

Java 实现常见内排序

一、内排序

1、排序基本概念

2、内排序分类

二、内排序 -- 稳定排序

1、 冒泡排序（Bubble Sort）

2、 直接插入排序（Insertion Sort）

3、归并排序（Merge Sort）

三、内排序 -- 非稳定排序

1、快速排序（Quick Sort）

2、选择排序（Selection Sort）

3、希尔排序（Shell Sort）

4、堆排序（Heap Sort）

最新文章

热门文章

1、冒泡排序（Bubble Sort）

2、直接插入排序（Insertion Sort）