您好,登錄后才能下訂單哦!
這篇文章主要為大家展示了C++如何實(shí)現(xiàn)快速排序算法,內(nèi)容簡而易懂,希望大家可以學(xué)習(xí)一下,學(xué)習(xí)完之后肯定會有收獲的,下面讓小編帶大家一起來看看吧。
一、基本思想是:
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
二、方法1實(shí)現(xiàn)程序:左右兩個(gè)方向掃描
// 快速排序:選第一個(gè)對象作為基準(zhǔn),按照該對象的排序碼大小,將整個(gè)對象 // 序列劃分為左右兩個(gè)字序列: // 左側(cè)子序列中所有對象的排序碼都小于或等于基準(zhǔn)對象的排序碼; // 右側(cè)子序列中所有對象的排序碼都大于基準(zhǔn)對象的排序碼; // 基準(zhǔn)對象則排在這兩個(gè)子序列中間,這也是該對象最終應(yīng)放的位置 // 然后分別對這兩個(gè)子序列重復(fù)施行上述方法,直到所有的對象都排在相應(yīng)位置上為止 #include <iostream> // 一次快速排序算法 int quickPass(int arr[], int low, int high) { int down, up, temp; down = low; up = high; temp = arr[low]; while(down < up) { while((down < up) && arr[up] >= temp) // 從右向左掃描 up--; if(down < up) arr[down++] = arr[up]; // 在被騰空出來的單元(由down指向)中填入arr[up] while((down < up) && arr[down] < temp) // 從左向右掃描 down++; if(down < up) arr[up--] = arr[down]; // 在被騰空出來的單元(由up指向)中填入arr[down] } arr[down] = temp; // 最后把基準(zhǔn)插回到數(shù)組中間去 return down; } // 快速排序算法 void quickSort(int arr[], int low, int high) { // 對序列arr[low]到arr[high]作快速排序 int mid; if(low < high) { mid = quickPass(arr, low, high); // 對序列arr[low]到arr[high]作一趟快速排序 quickSort(arr, low, mid-1); // 對左半部分作遞歸處理 quickSort(arr, mid+1, high); // 對右半部分作遞歸處理 } } int main(int argc, const char * argv[]) { // insert code here... int len, i; int arr[] = {40, 30, 60, 90, 70, 10, 20, 40}; len = sizeof(arr) / sizeof(arr[0]); std::cout << "排序前:\n"; for(i = 0; i < len; i++) std::cout << arr[i] << " "; std::cout << std::endl; quickSort(arr, 0, len-1); // 調(diào)用快速排序法 std::cout << "排序后:\n"; for(i = 0; i < len; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; }
運(yùn)行結(jié)果:
三、方法2:只往一邊掃描
// 快速排序的另一種方法:只往一邊掃描 #include <iostream> // 交換兩個(gè)數(shù) void Exchange(int &a, int &b) { int temp; temp = a; a = b; b = temp; } // 將序列分為左右兩部分,左部分較小,右部分較大 int Partition(int arr[], int low, int high) { int x, i, j; x = arr[high]; // 以high位置的數(shù)作為基準(zhǔn) i = low - 1; // 進(jìn)行數(shù)據(jù)分類:左部分較小,右部分較大 for(j = low; j < high; j++) if(arr[j] <= x) { // 往右掃描找小于或者等于基準(zhǔn)的數(shù) i = i + 1; Exchange(arr[i], arr[j]); // 交換 } Exchange(arr[i+1], arr[high]); // 把基準(zhǔn)放到中間 return i+1; } // 快速排序算法 void quickSort(int arr[], int low, int high) { int q; if(low < high) { q = Partition(arr, low, high); quickSort(arr, low, q-1); quickSort(arr, q+1, high); } } int main(int argc, const char * argv[]) { int len, i; int arr[] = {40, 30, 60, 90, 70, 10, 20, 40}; len = sizeof(arr) / sizeof(arr[0]); std::cout << "排序前:\n"; for(i = 0; i < len; i++) std::cout << arr[i] << " "; std::cout << std::endl; quickSort(arr, 0, len-1); // 調(diào)用快速排序法 std::cout << "排序后:\n"; for(i = 0; i < len; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; }
運(yùn)行結(jié)果:
以上就是關(guān)于C++如何實(shí)現(xiàn)快速排序算法的內(nèi)容,如果你們有學(xué)習(xí)到知識或者技能,可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。