常见排序算法

常见排序算法

​ 算法与数据结构是我们计算机开发与学习中重要的基础，是每个开发者都应熟练掌握的内功，本篇博文主要记录一下常见的排序算法以及优化策略。

O(n^2)时间复杂度的简单排序算法

选择排序

​ 选择排序的思想很简单，遍历数组每次选出最大（最小）的值放置在合适的位置即可。

// 交换数组两个位置的元素
function swapArr (arr, m, n) {
    let temp = arr[m];
    arr[m] = arr[n];
    arr[n] = temp;
}

/**
 *  普通选择排序
 */
function selectSort (arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError('传入参数必须为数组！');
    }
    if (arr.length < 1) {
        return;
    }
    for (let m = 0; m < arr.length; m++) {
        let min = m;
        for (let n = m + 1; n < arr.length; n++) {
            if (arr[n] < arr[min]) {
                min = n;
            }
        }
        swapArr(arr, min, m);
    }
}

​ 对于选择排序而言，我们有一个简单的优化策略——每次遍历同时选出最大值的最小值。这个优化方案有一个需要注意的点，当我们每次遍历选出最大值和最小值后，需要进行两次交换，需要考虑修正的情况。（假设排序的最大值在当前最小值的位置，先交换了最小值，此时最大值的位置也交换了，需要处理~^~）

/**
 * 优化选择排序-每次选出最大值和最小值
 */
function selectSortAdvance (arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError('传入参数必须为数组！');
    }
    if (arr.length < 1) {
        return;
    }
    let leftIndex = 0;
    let rightIndex = arr.length - 1;
    while (leftIndex < rightIndex) {
        let min = leftIndex;
        let max = rightIndex;
        for (let n = leftIndex; n <= rightIndex; n++) {
            if (arr[min] > arr[n]) {
                min = n;
            }
            if (arr[max] < arr[n]) {
                max = n;
            }
        }
        // 考虑修正的情况，最大值在最小位置。
        swapArr(arr, min, leftIndex);
        if (max === leftIndex) {
            max = min;
        }
        swapArr(arr, max, rightIndex);
        leftIndex++;
        rightIndex--;
    }
}

冒泡排序

​ 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成 。

/**
 * 冒泡排序
 */
function bubbleSort (arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError('传入参数必须为数组！');
    }
    if (arr.length <= 1) {
        return;
    }
    for (let m = 0; m < arr.length; m++) {
        for (let n = 0; n < arr.length; n++) {
            if (arr[n] > arr[n + 1]) {
                swapArr(arr, n, n + 1);
            }
        }
    }
}

​ 对于此冒泡排序的实现，我们可以发现，每经过一次冒泡，最大值已经放置在了合适的位置，所以在内层的循环中可以不必考虑正确位置的比较。

/**
 *  优化的冒泡排序
 */
function bubbleSortAdvance (arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError('传入参数必须为数组');
    }
    if (arr.length <= 1) {
        return;
    }
    for (let m = 0; m < arr.length - 1; m++) {
        for (let n = 0; n < arr.length - 1 - m; n++) {
            if (arr[n] > arr[n + 1]) {
                swapArr(arr, n, n + 1);
            }
        }
    }
}

​ 在查阅资料以及学习的过程中发现，其实冒泡排序还能进行更近一步的优化，当每次排序时，发现之后所有的元素都已经有序时，可以记录这个位置，下一次冒泡只考虑前面的元素即可。

function bubbleSortBest (arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError('传入参数必须为数组');
    }
    if (arr.length <= 1) {
        return;
    }
    let index = arr.length - 1;
    let temp = 0;
    for (let m = 0; m < arr.length - 1; m++) {
        for (let n = 0; n < index; n++) {
            if (arr[n] > arr[n + 1]) {
                swapArr(arr, n, n + 1);
                temp = n + 1;
            }
        }
        index = temp;
    }
}

​ 如果要求更高的话，我们可以发现外层for循环，其实还可以做一些小调整，循环次数可以减少。

插入排序

​ 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。 （很类似大多数人玩扑克牌时，抓牌时的策略）

/**
 * 直接插入排序
 */
function insertSort (arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError('传入参数必须为数组');
    }
    if (arr.length <= 1) {
        return;
    }
    for (let m = 1; m < arr.length; m++) {
        let temp = arr[m];
        let insertIndex = m;
        for (let n = m - 1; n >= 0; n--) {
            if (arr[n] > temp) {
                arr[n + 1] = arr[n];
                insertIndex--;
            }
        }
        arr[insertIndex] = temp;
    }
}

​ 根据插入排序的思想我们可以知道，插入排序前半部分的数组一定是有序的，所以想要快速找到待插入元素正确的插入位置，可以使用二分查找的思想。

/**
 * 二分插入排序
 */
function binarySearchInsertSort (arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError('传入参数必须为数组');
    }
    if (arr.length <= 1) {
        return;
    }
    for (let m = 1; m < arr.length; m++) {
        let temp = arr[m];
        let index = binarySearch(arr, m - 1, temp);
        for (let n = m - 1; n >= index; n--) {
            arr[n + 1] = arr[n];
        }
        arr[index] = temp;
    }
}
// 二分查找，(如果元素不存在，返回二分查找最后一步较大值的位置)
function binarySearch (arr, length, target) {
    let l = 0;
    let r = length;
    while (l <= r) {
        // 防止整形溢出的
        // let mid = Math.floor((l + r) / 2);
        let mid = l + ((r - l) >> 1);
        if (arr[mid] === target) {
            return mid;
        }
        if (arr[mid] > target) {
            r = mid - 1;
        }
        if (arr[mid] < target) {
            l = mid + 1;
        }
    }
    return r + 1;
}

O(nlogn)时间复杂度的排序算法

归并排序

​ 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

/**
 * 归并排序-递归法实现
 */
function mergeSort (arr, left, right) {
    if (left >= right) {
        return;
    }
    let mid = left + ((right - left) >> 1);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
function merge (arr, left, mid, right) {
    let temp = [];
    for (let i = left; i <= right; i++) {
        temp[i] = arr[i];
    }
    let m = left;
    let n = mid + 1;
    for (let k = left; k <= right; k++) {
        if (m > mid) {
            arr[k] = temp[n++];
        } else if (n > right) {
            arr[k] = temp[m++];
        } else if (temp[m] < temp[n]) {
            arr[k] = temp[m++];
        } else {
            arr[k] = temp[n++];
        }
    }
}

​ 对于以上递归实现的归并排序，有两个小点可以优化.

function mergeSort (arr, left, right) {
    // 优化1：当数组长度小于一定时，使用直接插入排序
    if( right - left <= 15 ){
        insertionSort(arr, l, r);
        return;
    }
    let mid = left + ((right - left) >> 1);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    // 优化2：前半部分最大值都比后半部分最小值都小的情况，不进行归并
    // 使算法对基本有序数组的排序效率大大增加
    if (arr[mid] > arr[mid+1]) {
         merge(arr, left, mid, right);
    }
}
function merge (arr, left, mid, right) {
    let temp = [];
    for (let i = left; i <= right; i++) {
        temp[i] = arr[i];
    }
    let m = left;
    let n = mid + 1;
    for (let k = left; k <= right; k++) {
        if (m > mid) {
            arr[k] = temp[n++];
        } else if (n > right) {
            arr[k] = temp[m++];
        } else if (temp[m] < temp[n]) {
            arr[k] = temp[m++];
        } else {
            arr[k] = temp[n++];
        }
    }
}

​ 使用递归法实现一个算法时，优点是思路清楚，缺点是递归函数会频繁的调用自身，递归次数过多时可能会发生栈溢出的情况，所以在实际应用中，我们应该考虑使用迭代法，来实现归并排序。

/**
 * 归并排序-迭代法（自低而上）
 */
function mergeSortBU (arr) {
    for (let size = 1; size < arr.length; size = 2 * size) {
        for (let i = 0; i < arr.length - size; i = i + 2 * size) {
            merge(arr, i, i + size - 1, Math.min(arr.length - 1, i + 2 * size - 1));
        }
    }
}

​ 对于迭代法而言，同样也可以使用插入排序来优化。对于有序的两个子项，不进行merge操作

function mergeSortBU (arr) {
    // 数据少时使用插入排序优化
    for (let i = 0; i < arr.length; i += 16) {
        insertSort(arr, i, Math.min(i + 15, arr.length - 1));
    }
    for (let size = 1; size < arr.length; size = 2 * size) {
        for (let i = 0; i < arr.length - size; i = i + 2 * size) {
            // 有序的情况下，不进行merge
            if (arr[i + size - 1] > arr[i + size) {
                merge(arr, i, i + size - 1, Math.min(arr.length - 1, i + 2 * size - 1));
            }

        }
    }
}

快速排序

​ 快速排序的思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

/**
 * 快速排序-递归-使用快慢指针
 */
function quickSort (arr, l, r) {
    if (l >= r) {
        return;
    }
    let p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
}
// 快慢指针法
function partition (arr, l, r) {
    let p = l;
    for (let i = l + 1; i <= r; i++) {
        if (arr[i] < arr[l]) {
            p++;
            swapArr(arr, p, i);
        }
    }
    swapArr(arr, l, p);
    return p;
}

​ 以上代码应该算是quickSort最简单的实现了，但是这个实现中有一个严重的缺陷，当我们的待排序数组已经是几乎有序的时候，我们直接选取第一个元素为标定点P的时候quickSort会退化为时间复杂度为O(n^2)级别的算法，所有我们可以随机选取标定点P可以解决这个问题。同时在小数组的时候使用插入排序，也是一种通用的优化策略。

function _quickSort (arr, l, r) {
    // 当数据量小时，使用插入排序优化
    if (r - l < 22) {
        insertSort(arr, l, r);
        return;
    }
    let p = _partition(arr, l, r);
    _quickSort(arr, l, p - 1);
    _quickSort(arr, p + 1, r);
}
// 快慢指针法
function _partition (arr, l, r) {
    // 随机选取标定点，解决快排在有序的情况下退化为O(n^2)级别的算法
    swapArr(arr, l, Math.floor(Math.random() * (r - l + 1)) + l);
    let p = l;
    for (let i = l + 1; i <= r; i++) {
        if (arr[i] < arr[l]) {
            p++;
            swapArr(arr, p, i);
        }
    }
    swapArr(arr, l, p);
    return p;
}

​ 除了排序数组近乎有序的情况下，当数组中存在大量重复值的时候，也可能出现算法时间复杂度退化为O(n^2)的情况。这时候我们可以使用二路快排的算法优化。二路快排的核心思想就是从数组两端开始扫描，即使遇到与标的点P相等的数据时，也进行交换位置。这样就使得quickSort在进行partition操作的时候将数组分为平衡的两个部分。

function _quickSortTwoWay (arr, l, r) {
    // 当数据量小时，使用插入排序优化
    if (r - l < 22) {
        insertSort(arr, l, r);
        return;
    }
    let p = _partition2(arr, l, r);
    _quickSort(arr, l, p - 1);
    _quickSort(arr, p + 1, r);
}
function _partition2 (arr, l, r) {
    // 随机选取标定点
    swapArr(arr, l, Math.floor(Math.random() * (r - l + 1)) + l);
    let i = l + 1;
    let j = r;
    while (true) {
        if (i <= r && arr[i] < arr[l]) {
            i++;
        }
        if (j >= l + 1 && arr[j] > arr[l]) {
            j--;
        }

        if (i > j) {
            break;
        }
        swapArr(arr, i, j);
        i++;
        j--;
    }

    swapArr(arr, l, j);
    return j;
}

​ 基于二路快排的思想，我们可以发现其实我们重复的移动了与标定点P数值相等的元素，那么我们可以找到一种方法减少这种重复且无用的操作吗？答案当然是，这也就是quickSort最经典的优化三路快排。

// 三路快排
function _quickSortThreeWay (arr, l, r) {
    // 当数据量小时，使用插入排序优化
    if (r - l < 22) {
        insertSort(arr, l, r);
        return;
    }
    let range = _partition3(arr, l, r);
    _quickSortThreeWay(arr, l, range.lt);
    _quickSortThreeWay(arr, range.gt, r);
}

function _partition3 (arr, l, r) {
    swapArr(arr, l, Math.floor(Math.random() * (r - l + 1)) + l);
    let lt = l + 1; // arr[l,lt) < v
    let gt = r; // arr(gt,r] > v
    let i = l + 1;
    while (i <= gt) {
        if (arr[i] > arr[l]) {
            swapArr(arr, i, gt);
            gt--;
        } else if (arr[i] < arr[l]) {
            swapArr(arr, lt, i);
            lt++;
            i++;
        } else {
            i++;
        }
    }
    return {
        lt: lt - 1,
        gt: gt + 1,
    };
}

未完待续

​ 对于排序算法而言，以上列出的种种只是冰山一角，之后有兴趣的时候在一一完善记录吧~

​ （堆排序、希尔排序、计数排序、桶排序……）

​