算法系列九：十大经典排序算法之——快速排序

​

1. 快速排序

• 什么是快速排序？

快速排序是一种较为高效的排序算法，是针对冒泡排序算法的一种改进。
基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1.1 排序流程

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

1.2 算法思想

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

具体来说，快速排序的过程如下：
首先选取待排序数组中一个元素作为基准元素，通常选择第一个元素或最后一个元素作为基准元素。
遍历数组，将小于基准元素的元素放到左边，大于等于基准元素的元素放到右边，此时数组被划分成了两个部分。
对左半部分和右半部分分别递归执行上述操作，直到排序完成。

需要注意的是，在遍历数组时，一般采用双指针法来实现。具体来说，我们使用一个左指针指向数组的第一个元素，用一个右指针指向数组的最后一个元素，然后从左到右依次遍历数组中的元素，如果当前元素小于基准元素，就将它和左指针所指的元素交换，然后将左指针向右移动一位；如果当前元素大于等于基准元素，就将它和右指针所指的元素交换，然后将右指针向左移动一位。重复上述操作直到左指针和右指针相遇为止。

1.3 时空复杂度

• 时间复杂度：O(n㏒₂n)，最好O(n㏒₂n)，最坏O(n²)
• 空间复杂度：O(n㏒₂n)
• 稳定性：不稳定（相同元素相对位置可能发生交换）

1.4 动图演示

1.5 算法实现

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;
 
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}
 
function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }       
    }
    swap(arr, pivot, index - 1);
    return index-1;
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Java代码：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) { // 当数组只有一个元素时结束递归
        int partitionIndex = partition(arr, left, right); // 对数组进行划分，获取基准元素位置
        quickSort(arr, left, partitionIndex - 1); // 对左子数组递归执行快速排序
        quickSort(arr, partitionIndex + 1, right); // 对右子数组递归执行快速排序
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left]; // 将数组的第一个元素设置为基准元素
    int i = left; // 初始化左指针
    int j = right; // 初始化右指针
    while (i < j) { // 当左指针和右指针没有相遇时循环
        while (i < j && arr[j] >= pivot) { // 右指针从右向左遍历，找到第一个小于基准元素的元素
            j--;
        }
        if (i < j) { // 如果左指针和右指针没有相遇，将右指针所指的元素赋值给左指针所指的位置
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < pivot) { // 左指针从左向右遍历，找到第一个大于等于基准元素的元素
            i++;
        }
        if (i < j) { // 如果左指针和右指针没有相遇，将左指针所指的元素赋值给右指针所指的位置
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = pivot; // 将基准元素放到最终位置
    return i; // 返回基准元素的位置
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

在上述代码中，quickSort() 方法是快速排序算法的入口，它采用递归的方式对左右两个子数组进行排序。partition() 方法则是用来对数组进行划分的，它使用双指针法来实现。

具体来说，我们首先将数组的第一个元素作为基准元素 pivot，然后初始化左指针 i 和右指针 j。接着，我们先让右指针 j 从右向左遍历数组，找到第一个小于基准元素的元素，并将其赋值给左指针所指的位置；然后让左指针 i 从左向右遍历数组，找到第一个大于等于基准元素的元素，并将其赋值给右指针所指的位置。重复上述操作直到左指针和右指针相遇。

最后，将基准元素 pivot 放到最终位置，即左指针所指的位置，这样就完成了对数组的一次划分。在 partition() 方法中，返回的是基准元素的位置，这个位置将用于快速排序算法的递归操作。

2. 总结

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢?

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
​

---

嘿，你的头发还好吗？

活动地址：CSDN21天学习挑战赛