目錄

一 簡(jiǎn)介

二 代碼實(shí)現(xiàn)

快速排序基本原理：

C語(yǔ)言實(shí)現(xiàn)快速排序的核心函數(shù)：

三 時(shí)空復(fù)雜度

A.時(shí)間復(fù)雜度

B.空間復(fù)雜度

C.總結(jié)：

---

一 簡(jiǎn)介

快速排序是一種高效的、基于分治策略的比較排序算法，由英國(guó)計(jì)算機(jī)科學(xué)家C.A.R. Hoare在1960年提出。

二 代碼實(shí)現(xiàn)

以下是使用C語(yǔ)言實(shí)現(xiàn)快速排序的基本步驟和代碼示例：

快速排序基本原理：

• 選擇一個(gè)基準(zhǔn)元素（pivot），通常選擇數(shù)組的第一個(gè)元素或者最后一個(gè)元素。
• 將所有比基準(zhǔn)小的元素移動(dòng)到基準(zhǔn)元素之前，所有比基準(zhǔn)大的元素移動(dòng)到基準(zhǔn)之后。這個(gè)操作被稱為分區(qū)操作（partition）。
• 對(duì)基準(zhǔn)左右兩邊的子數(shù)組分別遞歸地進(jìn)行上述操作。

C語(yǔ)言實(shí)現(xiàn)快速排序的核心函數(shù)：

#include <stdio.h>// 分區(qū)操作，返回基準(zhǔn)元素最后的位置
int partition(int arr[], int low, int high) {int pivot = arr[high]; // 基準(zhǔn)元素（這里選取了數(shù)組的最后一個(gè)元素）int i = (low - 1);  // 指針i初始化為low - 1for (int j = low; j <= high - 1; j++) {// 如果當(dāng)前元素小于或等于基準(zhǔn)元素，則與指針i所指向位置的元素交換，并將i后移一位if (arr[j] <= pivot) {i++;// 交換arr[i]和arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 把基準(zhǔn)元素放到正確的位置（即所有小于它的元素都在它前面）int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return (i + 1);
}// 快速排序主函數(shù)
void quickSort(int arr[], int low, int high) {if (low < high) {// pi是基準(zhǔn)元素最后所在的位置int pi = partition(arr, low, high);// 對(duì)基準(zhǔn)元素左側(cè)子數(shù)組進(jìn)行遞歸排序quickSort(arr, low, pi - 1);// 對(duì)基準(zhǔn)元素右側(cè)子數(shù)組進(jìn)行遞歸排序quickSort(arr, pi + 1, high);}
}// 測(cè)試快速排序
int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr)/sizeof(arr[0]);quickSort(arr, 0, n-1);printf("Sorted array: \n");for (int i=0; i<n; i++)printf("%d ", arr[i]);return 0;
}

這段代碼首先定義了一個(gè)partition函數(shù)，該函數(shù)負(fù)責(zé)對(duì)輸入數(shù)組進(jìn)行一次劃分操作，然后通過(guò)quickSort函數(shù)遞歸地對(duì)左右兩個(gè)子數(shù)組執(zhí)行同樣的操作，直到子數(shù)組只剩下一個(gè)元素為止（因?yàn)橹挥幸粋€(gè)元素的數(shù)組被認(rèn)為是有序的）。最終，整個(gè)數(shù)組會(huì)被排序完成。

三 時(shí)空復(fù)雜度

A.時(shí)間復(fù)雜度

• 平均情況：當(dāng)每次劃分都能將數(shù)組大致均分為兩個(gè)子數(shù)組時(shí)，快速排序的平均時(shí)間復(fù)雜度為 。這是由于每次遞歸調(diào)用都會(huì)將問(wèn)題規(guī)模減半，并且需要對(duì) n 個(gè)元素進(jìn)行 層遞歸。

• 最好情況：最好的情況即每次選取的基準(zhǔn)都能將數(shù)組完美地劃分為大小相等的兩部分，此時(shí)時(shí)間復(fù)雜度也是 。

• 最壞情況：最壞的情況是每次劃分后，一個(gè)子數(shù)組為空或只有一個(gè)元素，而另一個(gè)子數(shù)組包含所有剩余元素。例如，對(duì)于已經(jīng)完全有序的數(shù)組，這種情況會(huì)導(dǎo)致退化為的時(shí)間復(fù)雜度。然而，在實(shí)際應(yīng)用中，可以通過(guò)隨機(jī)化選擇基準(zhǔn)元素（如三數(shù)取中法）來(lái)避免這種極端情況的發(fā)生，從而保證快速排序在期望下的時(shí)間復(fù)雜度仍為。

B.空間復(fù)雜度

• 遞歸棧空間：快速排序是一種遞歸算法，其遞歸深度取決于輸入數(shù)據(jù)的結(jié)構(gòu)。在最壞情況下，遞歸深度可以達(dá)到 n，所以空間復(fù)雜度為 O(n)。但大多數(shù)情況下，遞歸深度為，此時(shí)的空間復(fù)雜度主要來(lái)自于遞歸調(diào)用棧，約為 。

• 輔助空間：快速排序在原地排序的情況下不需要額外的數(shù)據(jù)存儲(chǔ)空間，除了遞歸調(diào)用棧所占用的空間外，算法本身不使用其他額外空間，因此輔助空間復(fù)雜度可認(rèn)為是 O(1)。

C.總結(jié)：

綜上所述，快速排序在理想情況下是一個(gè)非常高效的排序算法，具有較好的平均性能。不過(guò)需要注意的是，為了避免最壞情況下的性能下降，通常會(huì)采取一些策略優(yōu)化基準(zhǔn)元素的選擇方法。