? ? 快速排序是最流行的,也是速度最快的排序算法(C++?STL?的sort函數(shù)就是實(shí)現(xiàn)的快速排序);?快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由C.?A.?R.?Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)序列變成有序序列。其算法的特點(diǎn)就是有一個(gè)樞軸(pivot),?樞軸左邊的元素都小于/等于樞軸所指向的元素,?樞軸右邊的元素都大于樞軸指向的元素;

?

快速排序算法思想:

? ? 設(shè)要排序的數(shù)組是A[0],?...,?A[N-1]，首先任意選取一個(gè)數(shù)據(jù)作為standard（通常選用數(shù)組的最后一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面,所有比它大的數(shù)都放到它后面(其實(shí)只要保證所有比他小的元素都在其前面,則后一條件則自動(dòng)滿足了),這個(gè)過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個(gè)相同的值的相對位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。(信息來源:百度百科)

一次劃分

目標(biāo):

? ? 找一個(gè)記錄，以它的關(guān)鍵字/下標(biāo)作為”樞軸/pivot”，凡是值小于樞軸的元素均移動(dòng)至該樞軸所指向的記錄之前,凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。

? ? 致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t]，且??

???????R[j].value ≤?R[i].value?≤?R[j].value

//實(shí)現(xiàn) template <typename Type> int partitionBy3Loop(Type *array, int p, int r) {int i = p;int j = r+1; //j:超出末尾元素額下一位置Type x = array[p]; //將最左邊的元素作為樞軸元素//將<x的元素交換到左邊區(qū)域//將>x的元素交換到右邊區(qū)域while (true){//找到一個(gè)比x大(>=x)的元素while (i < r && array[++i] < x);//找到一個(gè)比x小(<=x)的元素while (array[--j] > x);if (i >= j)break;//交換std::swap(array[i], array[j]);}//將樞軸元素與array[p]進(jìn)行交換std::swap(array[p], array[j]);//返回樞軸return j; } /**說明:幾乎國內(nèi)所有的數(shù)據(jù)結(jié)構(gòu)與算法的教材中的Partition實(shí)現(xiàn)都類似于上面的那一種, 雖然易于理解,但實(shí)現(xiàn)過于復(fù)雜;<算法導(dǎo)論>中給出了另一種實(shí)現(xiàn)方式,該方式雖然不易于理解(其實(shí)明白其原理之后你就會(huì)愛上她),但是比較容易實(shí)現(xiàn)! */ template <typename Type> int partitionBy1Loop(Type *array, int p, int r) {Type x = array[r]; //x作為最終樞軸所指向的元素//i指向的是樞軸左邊的最后一個(gè)元素//也就是與x左鄰元素的下標(biāo)int i = p - 1;//j則不斷的尋找下一個(gè)<=x的元素for (int j = p; j < r; ++j){if (array[j] <= x){++ i;std::swap(array[i], array[j]);}}std::swap(array[i+1], array[r]);//最終使得所有(i+1)左邊的元素都<=array[i+1],//因此, 所有array[i+2:r]的元素都是大于array[i+1]的return i+1; }

快速排序

首先對無序的記錄序列進(jìn)行“一次劃分”，之后分別對分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。

//實(shí)現(xiàn) template <typename Type> void quickSort(Type *array, int p, int r) {if (p < r){int pivot = partitionBy1Loop(array, p, r);quickSort(array, p, pivot-1);quickSort(array, pivot+1, r);} }

快速排序的時(shí)間復(fù)雜性

假設(shè)一次劃分所得樞軸位置?i = k，則對?n?個(gè)記錄進(jìn)行快排所需時(shí)間：

T(n)?=?{Tpass(n)?+?T(k-1)?+?T(n-k)?|Tpass(n)為對?n?個(gè)記錄進(jìn)行一次劃分所需時(shí)間}

若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則?k?取?1?至?n?中任意一值的可能性相同。

由此可得快速排序所需時(shí)間的平均值為：

??

設(shè)?Tavg(1)≤b,則可得結(jié)果：

?

因此:快速排序的時(shí)間復(fù)雜度為O(nlogn)

??

? ?若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判?#xff0c;其時(shí)間復(fù)雜度為O(n^2)。

? ?為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前，進(jìn)行“預(yù)處理”，即:先對?R(s).key,??R(t).key?和?R[?(s+t)/2?].key，進(jìn)行相互比較，然后取關(guān)鍵字為三個(gè)元素中居中間的那個(gè)元素作為樞軸記錄。

總結(jié)

以上是生活随笔為你收集整理的数据结构基础(4) --快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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