您當(dāng)前位置：首頁 > php開源 > php教程 > 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(4) --快速排序

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(4) --快速排序

來源：程序員人生發(fā)布時間：2015-01-07 08:58:38 閱讀次數(shù)：2591次

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

快速排序算法思想:

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

1次劃分

目標(biāo):

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

導(dǎo)致1趟排序以后，記錄的無序序列R[s..t]將分割成兩部份：R[s..i⑴]和R[i+1..t]，且

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

//實現(xiàn) template <typename Type> int partitionBy3Loop(Type *array, int p, int r) { int i = p; int j = r+1; //j:超越末尾元素額下1位置 Type x = array[p]; //將最左側(cè)的元素作為樞軸元素 //將<x的元素交換到左側(cè)區(qū)域 //將>x的元素交換到右側(cè)區(qū)域 while (true) { //找到1個比x大(>=x)的元素 while (i < r && array[++i] < x); //找到1個比x小(<=x)的元素 while (array[--j] > x); if (i >= j) break; //交換 std::swap(array[i], array[j]); } //將樞軸元素與array[p]進行交換 std::swap(array[p], array[j]); //返回樞軸 return j; }

/**說明: 幾近國內(nèi)所有的數(shù)據(jù)結(jié)構(gòu)與算法的教材中的Partition實現(xiàn)都類似于上面的那1種, 雖然易于理解,但實現(xiàn)過于復(fù)雜; <算法導(dǎo)論>中給出了另外一種實現(xiàn)方式, 該方式雖然不容易于理解(其實明白其原理以后你就會愛上她),但是比較容易實現(xiàn)! */ template <typename Type> int partitionBy1Loop(Type *array, int p, int r) { Type x = array[r]; //x作為終究樞軸所指向的元素 //i指向的是樞軸左側(cè)的最后1個元素 //也就是與x左鄰元素的下標(biāo) int i = p - 1; //j則不斷的尋覓下1個<=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)左側(cè)的元素都<=array[i+1], //因此, 所有array[i+2:r]的元素都是大于array[i+1]的 return i+1; }

快速排序

首先對無序的記錄序列進行“1次劃分”，以后分別對分割所得兩個子序列“遞歸”進行快速排序。

//實現(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⑴); quickSort(array, pivot+1, r); } }