八种排序算法及Java实现

1. 概述

排序算法分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存，具体分类如下图所示：

经常提及的八大排序算法指的就是内部排序的八种算法。

2. 冒泡排序

2.1 基本思想

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2.2 算法描述

冒泡排序算法的运作如下：

①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
③. 针对所有的元素重复以上的步骤，除了最后一个。
④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。

2.3 代码实现

/** * 冒泡排序 * Created by zhoujunfu on 2018/8/2. */
 * 冒泡排序
 * Created by zhoujunfu on 2018/8/2.
 */
public class BubbleSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        //外层：需要length-1次循环比较
        for (int i = 0; i < length - 1; i++) {
            //内层：每次循环需要两两比较的次数，每次比较后，都会将当前最大的数放到最后位置，所以每次比较次数递减一次
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }
}

2.4 算法效率

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1)。

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n2)	O(n)	O(n2)	O(1)

Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。

3. 快速排序

3.1 基本思想

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3.2 算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

①. 从数列中挑出一个元素，称为”基准”（pivot）。
②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

3.3 代码实现

①. 挖坑法
用伪代码描述如下：
（1）low = L; high = R; 将基准数挖出形成第一个坑a[low]。
（2）high–，由后向前找比它小的数，找到后挖出此数填前一个坑a[low]中。
（3）low++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[high]中。
（4）再重复执行②，③二步，直到low==high，将基准数填入a[low]中。
举例说明：
一个无序数组：[4, 3, 7, 5, 10, 9, 1, 6, 8, 2]

（1）.随便先挖个坑，就在第一个元素（基准元素）挖坑，挖出来的“萝卜”（第一个元素4）在“篮子”（临时变量）里备用。
挖完之后的数组是这样：[ 坑, 3, 7, 5, 10, 9, 1, 6, 8,2]
（2）．挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面。
填坑之后：[ 2, 3, 7, 5, 10, 9, 1, 6, 8,坑]
（3）．挖左坑填右坑：从左边开始，找个比“萝卜”（元素4）大的元素，挖出来，填到右边的坑里面。
填坑之后：[ 2, 3,坑, 5, 10, 9, 1, 6, 8, 7]
（4）．挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面。
填坑之后：[ 2, 3, 1, 5, 10, 9,坑, 6, 8, 7]
（5）．挖左坑填右坑：从左边开始，找个比“萝卜”（元素4）大的元素，挖出来，填到右边的坑里面。
填坑之后：[ 2, 3, 1,坑, 10, 9, 5, 6, 8, 7]
（6）．挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面，这一次找坑的过程中，找到了上一次挖的坑了，说明可以停了，用篮子里的的萝卜，把这个坑填了就行了，并且返回这个坑的位置，作为分而治之的中轴线。
填坑之后：[ 2, 3, 1, 4, 10, 9, 5, 6, 8, 7]

上面的步骤中，第2，4, 6其实都是一样的操作，3和5的操作也是一样的，代码如下：

/**   *  快速排序（挖坑法递归）   * @param arr   待排序数组   * @param low   左边界   * @param high  右边界   */
   *  快速排序（挖坑法递归）
   * @param arr   待排序数组
   * @param low   左边界
   * @param high  右边界
   */
  public static void sort(int arr[], int low, int high) {
      if (arr == null || arr.length <= 0) {
          return;
      }
      if (low >= high) {
          return;
      }

      int left = low;
      int right = high;
      int temp = arr[left]; //挖坑1：保存基准的值

      while (left < right) {
          while (left < right && arr[right] >= temp) {
              right--;
          }
          arr[left] = arr[right]; //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
          while (left < right && arr[left] <= temp) {
              left ++;
          }
          arr[right] = arr[left]; //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
      }
      arr[left] = temp; //基准值填补到坑3中，准备分治递归快排
      System.out.println("Sorting: " + Arrays.toString(arr));
      sort(arr, low, left-1);
      sort(arr, left + 1, high);
  }

②. 左右指针法
用伪代码描述如下：
（1）low = L; high = R; 选取a[low]作为关键字记录为key。
（2）high–，由后向前找比它小的数
（3）low++，由前向后找比它大的数
（4）交换第（2）、（3）步找到的数
（5）重复（2）、（3），一直往后找，直到left和right相遇，这时将key和a[low]交换位置。
代码如下：

/** * 快速排序 * Created by zhoujunfu on 2018/8/6. */
 * 快速排序
 * Created by zhoujunfu on 2018/8/6.
 */
public class QuickSort {
    /**     * 快速排序（左右指针法）     * @param arr 待排序数组     * @param low 左边界     * @param high 右边界     */
     * 快速排序（左右指针法）
     * @param arr 待排序数组
     * @param low 左边界
     * @param high 右边界
     */
    public static void sort2(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;

        int key = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, low, left);
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort2(arr, low, left - 1);
        sort2(arr, left + 1, high);
    }

    public static void swap(int arr[], int low, int high) {
        int tmp = arr[low];
        arr[low] = arr[high];
        arr[high] = tmp;
    }
}

3.4 算法效率

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlogn)	O(nlogn)	O(n2)	O(1)

Tips: 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定。

4. 直接插入排序

4.1 基本思想

直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。

4.2 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
①. 从第一个元素开始，该元素可以认为已经被排序
②. 取出下一个元素，在已经排序的元素序列中从后向前扫描
③. 如果该元素（已排序）大于新元素，将该元素移到下一位置
④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤. 将新元素插入到该位置后
⑥. 重复步骤②~⑤

4.3 代码实现

提供两种写法，一种是移位法，一种是交换法，其中移位法是完全按照以上算法描述实，交换法不需求额外的保存待插入数据，通过不停的向前交换带插入数据，直到找到比它小的值，也就是待插入数据找到了自己的位置。
①. 移位法：

public static void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        for (int i = 1; i < a.length; i++) {
            int j = i - 1;
            int temp = a[i]; // 先取出待插入数据保存，因为向后移位过程中会把覆盖掉待插入数
            while (j >= 0 && a[j] > a[i]) { // 如果待是比待插入数据大，就后移
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = temp; // 找到比待插入数据小的位置，将待插入数据插入
        }
    }

②. 交换法：

public static void sort2(int[] arr) {
      if (arr == null || arr.length == 0) {
          return;
      }

      for (int i = 1; i < arr.length; i ++) {
          int j = i - 1;
          while (j >= 0 && arr[j] > arr[i]) {
              arr[j + 1] = arr[j] + arr[j+1];      //只要大就交换操作
              arr[j] = arr[j + 1] - arr[j];
              arr[j + 1] = arr[j + 1] - arr[j];
              System.out.println("Sorting:  " + Arrays.toString(arr));
          }
      }
  }

4.4 算法效率

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n2)	O(n)	O(n2)	O(1)

5.希尔排序

希尔排序，也称递减增量排序算法，1959年Shell发明。是插入排序的一种高速而稳定的改进版本。
希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

5.1 基本思想

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。
可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。更好的步长序列取值可以参考维基百科。

5.2 算法描述

①. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
②. 按增量序列个数k，对序列进行k 趟排序；
③. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

在上面这幅图中：
初始时，有一个大小为 10 的无序序列。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。

5.3 代码实现

public class ShellSort {

    public static void sort(int[] arr) {
        int gap = arr.length / 2;
        for (;gap > 0; gap = gap/2) {
            for (int j = 0; (j + gap) < arr.length; j++) { //不断缩小gap，直到1为止
                for (int k = 0; (k + gap) < arr.length; k+=gap) { //使用当前gap进行组内插入排序
                    if (arr[k] > arr[k+gap]) { //交换操作
                        arr[k] = arr[k] + arr[k+gap];
                        arr[k+gap] = arr[k] - arr[k+gap];
                        arr[k] = arr[k] - arr[k+gap];
                        System.out.println("    Sorting:  " + Arrays.toString(arr));
                    }
                }
            }
        }
    }
}

5.4 算法效率

希尔排序第一个突破O(n²)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素，直接插入排序是稳定的；而希尔排序是不稳定的，希尔排序的时间复杂度和步长的选择有关，常用的是Shell增量排序，也就是N/2的序列，Shell增量序列不是最好的增量序列，其他还有Hibbard增量序列、Sedgewick 增量序列等，具体可以参考，希尔排序增量序列简介

6.选择排序

6.1 基本思想

在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

6.2 算法描述

①. 从待排序序列中，找到关键字最小的元素；
②. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
③. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。

6.3 代码实现

public class SelectSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j ++) { //选出之后待排序中值最小的位置
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                arr[min] = arr[i] + arr[min];
                arr[i] = arr[min] - arr[i];
                arr[min] = arr[min] - arr[i];
            }
        }
    }
}

6.4 算法效率

选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n2)	O(n2)	O(n2)	O(1)

7.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

7.1 基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

7.2 算法描述

采用递归法：
①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③. 重复步骤②，直到所有元素排序完毕

7.3 代码实现

/** * Created by zhoujunfu on 2018/8/10. */
 * Created by zhoujunfu on 2018/8/10.
 */
public class MergeSort {

    public static int[] sort(int [] a) {
        if (a.length <= 1) {
            return a;
        }
        int num = a.length >> 1;
        int[] left = Arrays.copyOfRange(a, 0, num);
        int[] right = Arrays.copyOfRange(a, num, a.length);
        return mergeTwoArray(sort(left), sort(right));
    }

    public static int[] mergeTwoArray(int[] a, int[] b) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[a.length + b.length];

        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }

        while (i < a.length) {
            result[k++] = a[i++];
        }
        while (j < b.length) {
            result[k++] = b[j++];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] b = {3, 1, 5, 4};
        System.out.println(Arrays.toString(sort(b)));
    }
}

7.4 算法效率

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlogn)	O(nlogn)	O(nlogn)	O(n)

从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn, 又每步都是一个普通的合并子数组的过程，时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。