算法：排序

一、引言

练好基本功，面试中经常考察的排序算法有快速排序、归并排序、插入排序、冒泡排序、堆排序和计数排序等。学习排序算法时需要关注以下几点：

时间复杂度
空间复杂度
排序算法的稳定性
算法适用的场景

二、快速排序

快排基本思路是找一个基准元素 pivot，把数组分成 2 部分（这 2 部分都不包括pivot），再分别递归快排这 2 个子数组。平均时间复杂度 O(NlogN),空间复杂度O(logN)。

相同大小的元素在比较过程中会改变相对顺序（比如最右边的先交换到左边），所以快排是不稳定排序。

/**
 * 快速排序，先找到 pivot 元素在数组中排序后的最终位置；再对 pivot 左边区间和右边区间的子数组继续进行快速排序
 * @param arr
 * @param start
 * @param end
 */
public void quicksort(int[] arr, int start, int end) {
    if(start >= end) return;
    int left = start, right = end;
    int pivot = arr[left];
    while(left < right) {
        while(left < right && arr[right] >= pivot) {
            --right;
        }

        if(left < right) {
            arr[left] = arr[right];
        }
        while(left < right && arr[left] <= pivot) {
            ++left;
        }

        if(left < right) {
            arr[right] = arr[left];
        }
    }
    arr[left] = pivot;

    quicksort(arr, start, left -1);
    quicksort(arr, left + 1, end);
}

三、归并排序

/**
 * 归并排序 2：内存只分配一次
 * @param arr：原数组
 * @param temp：临时数组，和原数组大小一致
 * @param left：待排序数组左边界。需要指定的原因是递归调用需要修改待排序子数组边界
 * @param right：待排序数组右边界
 */
public void mergeSort2(int[] arr, int[] temp, int left, int right) {
    if(left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort2(arr, temp, left, mid);
    mergeSort2(arr, temp, mid + 1, right);

    merge2(arr, temp, left, mid, right);
}

/**
 * 合并数组，对应归并数组 2。temp 数组 k 位置也可以从 0 开始，只要保证来回复制时位置一致即可（程序没有并发）
 * @param arr：原始数组
 * @param temp：临时数组
 * @param start：左子数组开始位置
 * @param mid：二分的中间位置，并归入左子数组右边界
 * @param end：右子数组结束位置
 */
private void merge2(int[] arr, int[] temp, int start, int mid, int end) {
    int i = start, j = mid + 1, k = start;
    while(i <= mid && j <= end) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while(i <= mid) temp[k++] = arr[i++];
    while(j <= end) temp[k++] = arr[j++];

    // 原始数组从临时数组中还原
    System.arraycopy(temp, start, arr, start, end - start + 1);
}

四、Java 中 Arrays.sort使用的排序算法

数据量大用快速排序或者归并排序，数据量小用插入排序。

五、总结

一般基于比较和交换的排序算法平均时间复杂度到 O(Nlog(N))已经不错了，插入、选择和冒泡等排序算法平均时间复杂度为O(N^2)。还有一种更牛的基于计数的时间复杂度为O(N+K)，K为数的范围，当然这种需要待排序的数在一定范围内。具体算法时间或者空间复杂度以及稳定性可以参考下面的维基百科。
维基百科