快速排序（QuickSort）算法详解

创作时间:

作者:

@小白创作中心

快速排序（QuickSort）算法详解

引用

CSDN

https://blog.csdn.net/hefeng_aspnet/article/details/138489858

快速排序（QuickSort）是一种基于分而治之算法的排序算法，它选择一个元素作为主元，并通过将主元放置在已排序数组中的正确位置，围绕所选主元对给定数组进行分区。

快速排序的工作原理

枢轴的选择

选择枢轴有许多不同的选择：

始终选择第一个元素作为枢轴。
始终选择最后一个元素作为基准（在下面实现）
选择一个随机元素作为基准。
选择中间作为枢轴。

分区算法

逻辑很简单，我们从最左边的元素开始，并跟踪较小（或等于）元素的索引i。遍历时，如果找到较小的元素，则将当前元素与 arr[i] 交换。否则，我们忽略当前元素。

让我们借助以下示例来了解分区和快速排序算法的工作原理：
考虑：arr[] = {10, 80, 30, 90, 40}。

将10与枢轴比较，小于枢轴则依次排列。

QuickSort 中的分区：将主元与 10 进行比较
将 80 与枢轴进行比较。它大于枢轴。

QuickSort 中的分区：将枢轴与 80 进行比较
将 30 与枢轴进行比较。它小于枢轴，因此请相应地安排它。

QuickSort 中的分区：将数据透视表与 30 进行比较
将 90 与枢轴进行比较。它大于枢轴。

QuickSort 中的分区：将枢轴与 90 进行比较
将枢轴布置在正确的位置。

QuickSort 中的分区：将枢轴放置在正确的位置

快速排序的说明：
由于分区过程是递归完成的，因此它不断地将主元放在排序数组中的实际位置。反复将枢轴放入其实际位置可以使数组排序。按照下图了解分区算法的递归实现如何帮助对数组进行排序。

主阵列上的初始分区：

快速排序：执行分区

子数组的划分：
快速排序：执行分区

快速排序的代码实现

// C program for QuickSort  
#include <stdio.h>  

// Utility function to swap tp integers  
void swap(int* p1, int* p2)  
{  
    int temp;  
    temp = *p1;  
    *p1 = *p2;  
    *p2 = temp;  
}  

int partition(int arr[], int low, int high)  
{  
    // choose the pivot  
    int pivot = arr[high];  
    // Index of smaller element and Indicate  
    // the right position of pivot found so far  
    int i = (low - 1);  
    for (int j = low; j <= high; j++) {  
        // If current element is smaller than the pivot  
        if (arr[j] < pivot) {  
            // Increment index of smaller element  
            i++;  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i + 1], &arr[high]);  
    return (i + 1);  
}  

// The Quicksort function Implement  
void quickSort(int arr[], int low, int high)  
{  
    // when low is less than high  
    if (low < high) {  
        // pi is the partition return index of pivot  
        int pi = partition(arr, low, high);  
        // Recursion Call  
        // smaller element than pivot goes left and  
        // higher element goes right  
        quickSort(arr, low, pi - 1);  
        quickSort(arr, pi + 1, high);  
    }  
}  

int main()  
{  
    int arr[] = { 10, 7, 8, 9, 1, 5 };  
    int n = sizeof(arr) / sizeof(arr[0]);  
    // Function call  
    quickSort(arr, 0, n - 1);  
    // Print the sorted array  
    printf("Sorted Array\n");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

输出
排序数组
1 5 7 8 9 10

快速排序的复杂度分析

时间复杂度：

最佳情况：Ω (N log (N))
快速排序的最佳情况发生在每一步选择的主元将数组分成大致相等的两半时。在这种情况下，算法将进行平衡分区，从而实现高效排序。
平均情况：θ ( N log (N))
快速排序的平均情况性能在实践中通常非常好，使其成为最快的排序算法之一。
最坏情况：O(N2)
快速排序的最坏情况发生在每一步的枢轴始终导致高度不平衡的分区时。当数组已经排序并且枢轴始终被选为最小或最大元素时。为了缓解最坏的情况，使用了各种技术，例如选择一个好的主元（例如，三的中位数）并使用随机算法（随机快速排序）在排序之前对元素进行混洗。