排序算法详解

虽然现在编程语言的库函数都提供了排序的功能，但经典的排序算法里应用了非常重要的算法思想，并且面试官也喜欢问它们。「排序算法」是非常好的学习材料。本篇文章将会举例列举个人认为比较基本和重要的排序算法。

算法概述

算法分类

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法复杂度

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• **空间复杂度：**是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

冒泡排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

	function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

public class Solution {
		//实现插入的方式：逐个交换到前面合适的位置
    public int[] sortArray(int[] nums) {
        int len = nums.length;
        // 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j - 1] > nums[j]) {
                    swap(nums, j - 1, j);
                } else {
                    break;
                }
            }
        }
        return nums;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

归并排序

所谓归并，就是将两个或两个以上的 有序 序列合并成一个新的有序序列的过程。

public class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        mergeSort(nums, 0, len - 1);
        return nums;
    }

    /**
     * 对数组 nums 的子区间 [left..right] 进行归并排序
     *
     * @param nums
     * @param left
     * @param right
     */
    private void mergeSort(int[] nums, int left, int right) {
        if (left == right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        mergeOfTwoSortedArray(nums, left, mid, right);
    }


    /**
     * 合并两个有序数组：先把值复制到临时数组，再合并回去
     *
     * @param nums
     * @param left
     * @param mid   [left, mid] 有序，[mid + 1, right] 有序
     * @param right
     */
    private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right) {
        // 每做一次合并，都 new 数组用于归并，开销大
        int len = right - left + 1;
        int[] temp = new int[len];

        for (int i = 0; i < len; i++) {
            temp[i] = nums[left + i];
        }

        // i 和 j 分别指向前有序数组和后有序数组的起始位置
        int i = 0;
        int j = mid - left + 1;
        for (int k = 0; k < len; k++) {
            // 先写 i 和 j 越界的情况（若i越界则让j归并回去,j++）
            if (i == mid + 1 - left) {
                nums[left + k] = temp[j];
                j++;
            } else if (j == right + 1 - left) {
                nums[left + k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                // 注意：这里必须写成 <=，否则归并排序就成了非稳定的排序
                nums[left + k] = temp[i];
                i++;
            } else {
                nums[left + k] = temp[j];
                j++;
            }
        }
    }
}

时间复杂度

空间复杂度

归并需要 O(N)这么多的辅助空间，递归调用的深度是 O(logN)，因此空间复杂度是 O(N + log N) =O(N)（计算复杂度的时候，两个加法项，保留较大的那个项）。

快速排序

快速排序和归并排序一样采用了分而治之的思想，基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

public class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        quickSort(nums, 0, len - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        // 注意：这里包括 > 的情况，与归并排序不同，请通过调试理解这件事情
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        // 循环不变量： lt 意即 less than
        // [left + 1, lt] < pivot，
        // [lt + 1, i) >= pivot
        int lt = left;
        // 注意，这里取等号
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                // 交换当前元素与 lt 的位置
                lt++;
                swap(nums, i, lt);
            }
        }
        // 最后这一步要记得交换到切分元素
        swap(nums, left, lt);
        return lt;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

扩展：O(n) 时间复杂度内求无序数组中的第 K 大元素

我们选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot，对数组 A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K，那 A[p]就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1]区间，我们再按照上面的思路递归地在 A[p+1…n-1]这个区间内查找。

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

/**
 * 下沉操作
 * @param {array} arr 待调整的堆 
 * @param {number} parentIndex 要下沉的父节点
 * @param {number} length 堆的有效大小
 */
function downAdjust(arr, parentIndex, length) {
    // temp保存父节点的值，用于最后赋值
    let temp = arr[parentIndex]
    let childrenIndex = 2 * parentIndex + 1
    while(childrenIndex < length) {
        // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
        // 这里其实是比较左、右子树的大小，选择更大的
        if (childrenIndex + 1 < length && arr[childrenIndex + 1] > arr[childrenIndex]) {
            childrenIndex++
        }
        // 如果父节点大于任何一个孩子得值，则直接跳出
        if (temp >= arr[childrenIndex]) {
            break
        }
        // 当左、右子树比父节点更大，进行交换
        arr[parentIndex] = arr[childrenIndex]
        parentIndex = childrenIndex
        childrenIndex = 2 * childrenIndex + 1
    }
    arr[parentIndex] = temp
}

/**
 * 堆排序(升序)
 * @param {array} arr 待调整的堆 
 */
function heapSort(arr) {
    // 把无序数组构建成最大堆, 这里-2,是因为从索引0开始、另外就是叶子节点【最后一层是不需要堆化的】
    for(let i = (arr.length - 2)/2; i >= 0; i--) {
        downAdjust(arr, i, arr.length)
    }
   
    // 循环删除堆顶元素，并且移到集合尾部，调整堆产生新的堆顶
    for(let i = arr.length - 1; i > 0; i--) {
        // 交换最后一个元素与第一个元素
        let temp = arr[i]
        arr[i] = arr[0]
        arr[0] = temp
        // 下沉调整最大堆
        downAdjust(arr, 0, i)
    }
    return arr
}
// test case
console.log(heapSort([4, 4, 6, 5, 3, 2, 8, 1]))