排序算法概述

一、综述

二、选择排序

思想：

首先找到数组中最小的元素，其次将它和数组的第一个元素交换位置（如果第一个元素是最小元素就和自己交换位置）。再次，在剩余的元素中找到最小元素，将它和数组的第二个元素交换位置。如此往复直到整个数组排序。

时间复杂度：

• 对于长度为N的数组，选择排序需要大约N²/2次比较以及N次交换
• 运行时间和数组无关。无论数组是乱序、部分有序或者全部有序，该方法都会进行大约N²/2次比较以及N次交换
• 数据移动是最少的。这是其他算法所不能达到的。

实现

public static void selectSort(int[] array, int start) {
    for (int i = start; i < array.length; i++) {
        int minIndex = min(array, i);
        if (i != minIndex) {
            swap(array, i, minIndex);
        }
    }
}

三、插入排序

思想：

和选择排序一样，当前索引左边的所有元素都是有序的，但是她们的最终位置并不确定，为了给更小的元素腾出位置，他们可能会被移动。和选择排序不同的是，插入排序的时间复杂度取决于数组的初始顺序。对一个很大但其中的元素已经有序（或接近有序）的数组进行排序会比对随机顺序的数组或者逆序数组进行排序要快得多。

时间复杂度

• 对于随机无重复长度为N的数组，平均情况下需要N²/4次比较以及N²/4次交换。最坏情况下需要N²/2 次比较以及N²/2次交换。最好情况下需要N-1次比较以及0次交换。
• 插入排序需要交换元素的次数和原始数组中逆序对的数目相同。

适用情况

插入排序对部分有序的数组十分高效，也很适合小规模数组。

实现

public static void insert(int[] array) {
    for (int i = 1; i < array.length; i++) {
        if (array[i] < array[i - 1]) {
            int temp = array[i];
            int j = 0;
            for (j = i - 1; j >= 0 && array[j] > temp; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
        }
    }
}

四、希尔排序

思想：

基于插入排序进行改进，对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点从数组的一端移动到另一端。希尔排序为了加快速度改进了插入排序，交换不相邻元素以对数组局部进行排序，最终用插入排序对局部有序的数组进行排序。希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组成为h有序数组。换句话说一个h有序数组是h个相互独立的有序数组编织在一起形成的数组。

时间复杂度

• 希尔排序的时间复杂度达不到平方级别。
• 使用递增序列1,4,13,40,121（3h+1）的希尔排序所需比较次数不会超过N的若干倍乘以递增序列长度

适用情况

适用于大型数组，并且数组越大，优势越大。

实现

public static void shellSort(int[] array, int d) {
    for (int i = 0; i + d < array.length; i++) {
        if (array[i] > array[i + d]) {
            int temp = array[i + d];
            int j;
            for (j = i; j >= 0 && array[j] > temp; j -= d) {
                array[j + d] = array[j];
            }
            array[j + d] = temp;
        }
    }

    if (d != 1) {
        shellSort(array, d / 2);
    }
}

五、冒泡排序

思想

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

时间复杂度

实现

public class BubbleSort
{
    public void sort(int[] a)
    {
        int temp = 0;
        for (int i = a.length - 1; i > 0; --i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (a[j + 1] < a[j])
                {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }
}

六、归并排序

思想

将两个有序的数组归并成一个更大的数组。首先将数组分为两半分别进行排序，然后将结果归并起来。归并排序保证任意长度为N的数组排序所需时间复杂度和NlogN成正比，主要缺点是空间复杂度和长度N成正比。

时间复杂度

• 归并排序是一种渐进最优的基于比较的排序算法，时间复杂度和原始数组初始顺序无关，都为O(NlogN)，空间复杂度为O(N)。

实现

public static void merge(int[] array, int lo, int middle, int hi) {
    int i = lo;
    int j = middle + 1;

    int[] temp = new int[hi - lo + 1];
    for (int k = lo; k <= hi; k++) {
        temp[k - lo] = array[k];
    }

    int index = lo;
    while (i <= middle && j <= hi) {
        if (temp[i - lo] > temp[j - lo]) {
            array[index++] = temp[j - lo];
            j++;
        } else {
            array[index++] = temp[i - lo];
            i++;
        }
    }

    while (i <= middle) {
        array[index++] = temp[i - lo];
        i++;
    }

    while (j <= hi) {
        array[index++] = temp[j - lo];
        j++;
    }
}

public static void mergeSort(int[] array, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int mid = lo + (hi - lo) / 2;
    mergeSort(array, 0, mid);
    mergeSort(array, mid + 1, hi);
    merge(array, lo, mid, hi);
}

七、快速排序

思想

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立的排序。快速排序关键点在于实现切分方法，一般取a[low]为切分元素，然后我们先从右往左扫描数组，找到小于切分元素的元素，并和切分元素交换位置；之后在从左向右扫描元素，找到大于切分元素的元素，并和切分元素交换位置。如此继续我们便可以保证切分元素左边的元素都小于切分元素，切分元素右边的元素都大于切分元素。

时间复杂度

• 时间复杂度和数组初始顺序有关，对于随机顺序的数组来说，快速排序可以实现O(NlogN)，但对于有序数组而言，快速排序的时间复杂度为O(N^2)。
• 快速排序比较次数很少。

实现

public static void qSort(int[] array, int low, int hi) {
    if (low > hi) {
        return;
    }
    
    int key = array[low];
    int i = low;
    int j = hi;

    while (i < j) {
        while (i < j && array[j] >= key) {
            j--;
        }
        if (i < j) {
            swap(array, i, j);
        }

        while (i < j && array[i] <= key) {
            i++;
        }
        if (i < j) {
            swap(array, i, j);
        }
    }

    qSort(array, low, i - 1);

    qSort(array, i + 1, hi);
}