• 今天講解一下快速排序算法的原理以及實(shí)現(xiàn)、復(fù)雜度和穩(wěn)定性分析與優(yōu)化

---

目錄

• • 1 快速排序的原理
  • 2 快速排序代碼實(shí)現(xiàn)
  • 3 復(fù)雜度和穩(wěn)定性分析、優(yōu)化
  • 4 習(xí)題練習(xí)

---

1 快速排序的原理

快速排序是所有內(nèi)部排序算法中平均性能最優(yōu)的排序算法

快速排序是對冒泡排序算法的一種改進(jìn)

快速排序由C. A. R. Hoare在1960年提出。
它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列

快速排序的基本思想是基于分治法的

在待排序表L[1…n]中任取一個(gè)元素pivot作為樞軸(或基準(zhǔn)，通常取首元素)

也就是常見的 固定位置選取基準(zhǔn)

通過一趟排序?qū)⒋判虮韯澐譃楠?dú)立的兩部分L[1…k-1]和L[k+1…n]

使得L[1…k-1]中的所有元素小于pivot

L[k+1.n]中的所有元素大于等于pivot

則pivot放在了其最終位置L(k)上

這個(gè)過程稱為一趟快速排序(或一次劃分)

然后分別遞歸地對兩個(gè)子表重復(fù)上述過程，直至每部分內(nèi)只有一個(gè)元素或空為止，即所有元素放在了其最終位置上。

一趟快速排序的過程是一個(gè)交替搜索和交換的過程

常見方法就是 挖坑法

不過需要注意：

如果選擇 第一個(gè)數(shù)組元素為基準(zhǔn)時(shí)，必須先 從后向前進(jìn)行

如果選擇 最后一個(gè)數(shù)組元素為基準(zhǔn)時(shí)，必須先 從前向后進(jìn)行

挖坑法的流程：

---

2 快速排序代碼實(shí)現(xiàn)

首先寫好劃分操作算法，然后遞歸調(diào)用~

// 每一次的 劃分操作 int Partition(int *arr, int left, int right) {int i = left;int j = right;// 固定位置選取基準(zhǔn) 選第一個(gè) int k = arr[left]; while (i < j){while(i < j && arr[j] >= k) {j--;}arr[i] = arr[j];while(i < j && arr[i] <= k) {i++;}arr[j] = arr[i];}arr[i] = k;return i; }// 遞歸調(diào)用 實(shí)現(xiàn)快速排序 void QuickSort(int *arr,int low,int high) {int k = Partition(arr,low,high);if(low < k-1){QuickSort(arr,low,k-1);}if(high > k+1){QuickSort(arr,k+1,high);} }

示例：

int arr[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

---

3 復(fù)雜度和穩(wěn)定性分析、優(yōu)化

① 空間復(fù)雜度

由于快速排序是遞歸的，需要借助一個(gè)遞歸工作棧來保存每層遞歸調(diào)用的必要信息，其容量應(yīng)與遞歸調(diào)用的最大深度一致。

最好情況下為 O(log2n)

最壞情況下 O(n) ;因?yàn)橐M(jìn)行n-1 次遞歸調(diào)用

平均情況下，棧的深度為 O(log2n)

---

② 時(shí)間復(fù)雜度

快速排序的運(yùn)行時(shí)間與劃分是否對稱有關(guān)

最壞情況發(fā)生在初始排序表基本有序或基本逆序時(shí)，時(shí)間復(fù)雜度為 O(n)

最好的情況，每一次劃分都很均衡，時(shí)間復(fù)雜度為 O(nlog2n)

---

③ 優(yōu)化：提高算法效率

一種方法是盡量選取一個(gè)可以將數(shù)據(jù)中分的樞軸元素

三分取中法選取基準(zhǔn)：從序列的頭尾及中間選取三個(gè)元素，再取這三個(gè)元素的中間值作為最終的樞軸元素;

隨機(jī)選擇基準(zhǔn)：隨機(jī)地從當(dāng)前表中選取樞軸元素

這樣做可使得最壞情況在實(shí)際排序中幾乎不會發(fā)生。

④ 穩(wěn)定性

一種情況是，右端區(qū)間有兩個(gè)關(guān)鍵字相同，且均小于基準(zhǔn)值，則交換到左端區(qū)間后，它們的相對位置(不是絕對位置)會發(fā)生變化

所以快速排序是一種不穩(wěn)定的排序方法

---

4 習(xí)題練習(xí)

總結(jié)

以上是生活随笔為你收集整理的排序算法 | 快速排序，算法的图解、实现、复杂度和稳定性分析与优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。