JS排序之快速排序详解

快速排序是一种高效的排序算法，它的核心思想是分治。快排的具体步骤如下：

1. 选择一个基准元素，将序列中所有元素和这个基准元素进行比较，将比基准元素小的元素放入左侧序列，将比基准元素大的元素放入右侧序列。

2. 递归地对左右两个子序列进行快速排序，直到每个子序列只有一个元素或者为空。

示例1：将序列[3,1,6,4,8,2,5,7]进行快速排序。

首先，我们选择3作为基准元素。将序列中的其他元素与3进行比较，得到左侧序列[1,2]和右侧序列[6,4,8,5,7]。

接下来，我们递归地对左侧序列和右侧序列进行快速排序。对于左侧序列[1,2]，选择1作为基准元素，得到左侧序列[]和右侧序列[2]。此时，左右两个子序列均已排序完成。对于右侧序列[6,4,8,5,7]，选择6作为基准元素，得到左侧序列[4,5]和右侧序列[8,7]。递归地对左右两个子序列进行快速排序，得到左侧序列[4]和右侧序列[5]，以及左侧序列[7]和右侧序列[8]。此时，右侧序列[4,5,6,7,8]已经排序完成。

最终的排序结果为[1,2,3,4,5,6,7,8]。完整的快速排序代码如下：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivot = arr[0];
    let left = [];
    let right = [];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

示例2：将序列['apple', 'banana', 'orange', 'pear', 'kiwi']按字母顺序进行快速排序。

首先，我们选择'apple'作为基准元素。将序列中的其他元素与'apple'进行比较，得到左侧序列['banana']和右侧序列['orange', 'pear', 'kiwi']。

接下来，我们递归地对左侧序列和右侧序列进行快速排序。对于左侧序列['banana']，选择'banana'作为基准元素，得到左侧序列[]和右侧序列[]。此时，左右两个子序列均已排序完成。对于右侧序列['orange', 'pear', 'kiwi']，选择'orange'作为基准元素，得到左侧序列['kiwi']和右侧序列['pear']。递归地对左右两个子序列进行快速排序，得到左侧序列[]和右侧序列['kiwi', 'pear']。最终，右侧序列['banana', 'kiwi', 'orange', 'pear']已经排序完成。

最终的排序结果为['apple', 'banana', 'kiwi', 'orange', 'pear']。对字符串进行快排需要使用字符串比较函数来进行排序，完整的代码如下：

function quickSortStrings(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivot = arr[0];
    let left = [];
    let right = [];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSortStrings(left).concat(pivot, quickSortStrings(right));
}

let fruits = ['apple', 'banana', 'orange', 'pear', 'kiwi'];
console.log(quickSortStrings(fruits));

以上是快速排序的详细讲解和示例说明。