常见排序算法

算法

我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法大体可分为两种：

• 比较排序
  时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
• 非比较排序
  时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

1、冒泡排序(Bubble Sort)

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

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。冒泡排序的代码如下：

/**
 * 冒泡排序算法：平均o(n^2) 稳定 相邻两个比较，最大或最小的移到最右边
 *      
 * @author xiaoyue
 * @created @2018年3月6日-下午7:16:01
 *
 */
public class BubbleSort {
    public static void main(String[] args) {
        int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大冒泡排序
        int size = A.length;
        for (int i = 0; i < size - 1; i++) {// 每次最大元素就像气泡一样"浮"到数组的最后
            for (int j = 0; j < size - 1 - i; j++) { //依次比较相邻的两个元素,使较大的那个向后移
                if (A[j] > A[j + 1]) { // 如果条件改成A[j] >= A[j + 1],则变为不稳定的排序算法
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < size; i++) {
            System.out.print(A[i] + ", ");
        }
    }
}

2、选择排序(Selection Sort)

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

public static void main(String[] args) {
        int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 从小到大选择排序
        int size = A.length;
        for (int i = 0; i < size - 1; i++) {//循环比对次数，除了最后一个数
            int min = i;
            for (int j = i + 1; j < size; j++) {//选择用来比对的数，从当前下一位到最后一位
                if (A[j] < A[min]) {
                    min = j;
                }
            }
            if (min != i) { //放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
                int temp = A[i];
                A[i] = A[min];
                A[min] = temp;
            }
        }
        for (int i = 0; i < size; i++) {
            System.out.print(A[i] + ", ");
        }
    }

3、插入排序(Insertion Sort)

具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

public static void main(String[] args) {
        int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序
        int size = A.length;
        for (int i = 1; i < size; i++) {
            int get = A[i];// 右手抓到一张扑克牌
            int j = i - 1;// 拿在左手上的牌总是排序好的
            while (j >= 0 && A[j] > get) {// 将抓到的牌与手牌从右向左进行比较
                A[j + 1] = A[j];// 如果该手牌比抓到的牌大，就将其右移
                j--;
            }
            A[j + 1] = get;// 直到该手牌比抓到的牌小(或二者相等)，将抓到的牌插入到该手牌右边
                           //(相等元素的相对次序未变，所以插入排序是稳定的)
        }
        for (int i = 0; i < size; i++) {
            System.out.print(A[i] + ", ");
        }
    }

4、快速排序(Quick Sort)

快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：

1. 从序列中挑出一个元素，作为"基准"(pivot).
2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
3. 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

public static void main(String[] args) {
    int a[] = { 49, 37, 65, 97, 76, 13, 27, 49, 78 };
    int low = 0;
    int high = a.length-1;
    quickSort(a, low, high);
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i]+" ");
    }
}
private static void quickSort(int[] a, int low, int high) {
    int i = low,j = high;
    if (i > j) {
        return;
    }
    while (i < j) {
        while (i<j && a[j]>=a[low]) {//从后往前找小于基准数的位置
            j--;
        }
        while (i<j && a[i]<=a[low]) {//从前往后找大于基准数的位置
            i++;
        }
        if (i < j) {//注意，i,j不能相遇或交叉
            swap(a,i,j);
        }
    }
    swap(a, low, j);
    quickSort(a, low, j-1);
    quickSort(a, j+1, high);
}

Arrays.sort()

Java系统提供的Arrays.sort函数。对于基础类型，底层使用快速排序。对于非基础类型，底层使用归并排序。请问是为什么？

答：这是考虑到排序算法的稳定性。对于基础类型，相同值是无差别的，排序前后相同值的相对位置并不重要，所以选择更为高效的快速排序，尽管它是不稳定的排序算法；而对于非基础类型，排序前后相等实例的相对位置不宜改变，所以选择稳定的归并排序。

参考资料

常用排序算法总结(一)