QuickSort - 快速排序
核心：快速排序是采用分治思想的典型应用。
- 基本思想：
- 从要排序数组中下标从 p 到 r 之间的一组数据，任意一个数据作为 pivot（分区点/基准值）。
- 将所有比基准值小的排在基准前面，所有比基准值大的排在基准的后面；在这个分区退出之后，该基准就处于数列的中间位置。
- 递归地把“基准值前面的子数列”和“基准值后面的子数列”进行排序。
分区点
- 先写出快速排序的递推公式：
递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)
终止条件：
p >= r
- 我们将递推公式转化为递归代码。写出伪代码，你可以翻译成你熟悉的任何语言。
// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
时间复杂度
- 最优时间复杂度：
- 最坏时间复杂度：
- 稳定性：不稳定
- Python代码实现
class Solution(object):
def quickSort(self, numbers, l, r):
if l >= r:
return
pivot = numbers[r]
left, right = l, r - 1
while left <= right:
while left <= right and numbers[left] < pivot:
left += 1
while left <= right and numbers[right] >= pivot:
right -= 1
if left > right:
break
# swap numbers[left] with numbers[right] while left <= right
numbers[left], numbers[right] = numbers[right], numbers[left]
# swap the smaller with pivot
numbers[left], numbers[r] = numbers[r], numbers[left]
self.quickSort(numbers, l, left - 1)
self.quickSort(numbers, left + 1, r)
if __name__ == "__main__":
numbers = [1, 2, 3, 2, 2, 2, 5, 4, 2]
solution = Solution()
solution.quickSort(numbers, 0, len(numbers) - 1)
print("快速排序：", numbers)
# 结果
快速排序： [1, 2, 2, 2, 2, 2, 3, 4, 5]
- Java代码实现
import java.util.Arrays;
public class QuickSort {
// 基于快排的思想
public static void quickSort(int[] numbers, int l, int r) {
// 递归终止条件
if(l >= r) {
return;
}
int pivot = numbers[r];
int left = l;
int right = r - 1;
while(left <= right) {
while(left <= right && numbers[left] < pivot) {
left++;
}
while(left <= right && numbers[right] >= pivot) {
right--;
}
if(left > right) {
break;
}
// swap numbers[left] with numbers[right] while left <= right
int temp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = temp;
}
// swap the smaller with pivot
numbers[r] = numbers[left];
numbers[left] = pivot;
quickSort(numbers, l, left - 1);
quickSort(numbers, left + 1, r);
}
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 2, 2, 2, 5, 4, 2};
quickSort(numbers, 0, numbers.length - 1);
System.out.println("快速排序：" + Arrays.toString(numbers));
}
}
// 结果
快速排序：[1, 2, 2, 2, 2, 2, 3, 4, 5]
- C++代码实现
#include <iostream>
class Solution
{
public:
// 基于快排的思想
void quickSort(int* numbers, int l, int r) {
// 递归终止条件
if(l >= r) {
return;
}
int pivot = numbers[r];
int left = l;
int right = r - 1;
while(left <= right) {
while(left <= right && numbers[left] < pivot) {
left++;
}
while(left <= right && numbers[right] >= pivot) {
right--;
}
if(left > right) {
break;
}
// swap numbers[left] with numbers[right] while left <= right
int temp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = temp;
}
// swap the smaller with pivot
numbers[r] = numbers[left];
numbers[left] = pivot;
quickSort(numbers, l, left - 1);
quickSort(numbers, left + 1, r);
}
};
// 数组打印模板
template<typename T>
void PrintArray(const T input_array[], const unsigned int array_size) {
for(int i = 0; i < array_size; i++) {
std::cout << input_array[i];
if(i < array_size - 1){
std::cout << ' ';
}
}
std::cout << std::endl;
}
int main() {
int numbers[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
Solution solution;
solution.quickSort(numbers, 0, 8);
std::cout << "快速排序：";
PrintArray(numbers, 9);
return 0;
}
// 结果
快速排序：1 2 2 2 2 2 3 4 5
- Go代码实现
package main
import "fmt"
func quickSort(numbers []int, l int, r int) {
// 递归终止条件
if l >= r {
return
}
// 分区值
pivot := numbers[r]
left := l
right := r - 1
for left <= right {
for left <= right && numbers[left] < pivot {
left++
}
for left <= right && numbers[right] >= pivot {
right--
}
if left > right {
break
}
numbers[left], numbers[right] = numbers[right], numbers[left]
}
numbers[left], numbers[r] = numbers[r], numbers[left]
quickSort(numbers, l, left - 1)
quickSort(numbers, left + 1, r)
}
func main() {
numbers := []int{1, 2, 3, 2, 2, 2, 5, 4, 2}
quickSort(numbers, 0, 8)
fmt.Println("快速排序：", numbers)
}
// 结果
快速排序： [1 2 2 2 2 2 3 4 5]
参考文献
- 《数据结构与算法之美》
网友评论