引言

快速排序一直是排序算法中使用比較高頻的一種算法。下面簡述一下快排，予以記錄。

實現思想

在一組無序的數組中，定義一個標志flag，這里以數組中左起第一個元素作為標志，定義一個i值和j值，分別表示從左邊開始與flag比較的數組元素下標，從右邊開始與flag比較的數組元素下標，這里需要注意的是，若選擇數組中左起第一個元素為flag,則先從右開始與flag比較，反之亦然。當下標j 和下標i的元素相同的情況下，停止此次排序，用flag與當前下標i(下標i和下標j相等)的元素進行交換，就能滿足左邊小于flag的值，右邊大于flag的值。然后以左邊的元素構成一個數組，依舊選擇左起第一個元素為flag,同時下標i為左起第一個元素的下標，下標j為數組的右側最后一個元素的下標，開始比較排序，類似之前的操作。下面舉例說明。
23，54，6，34，55，12，4，67，8，29
上面的數組中，選擇左起第一個元素 23作為flag,定義i和j作為下標，分別指向最左邊和最右邊，即i指向23，j指向29，現在進行第一輪排序，要求左邊的元素小于等于23，右邊的元素大于等于23。29大于23，滿足要求，j–,此時j指向元素8，8<23不滿足右邊的元素大于flag,停止右邊的移動比較，開始比較左邊i下標的元素，23等于23，滿足條件，開始下一位54，54>23,不滿足條件，這時交換54與8的值，交換后數組元素的值為：
23，8，6，34，55，12，4，67，54，29
接下來進行第二次排序。此時經過上一次的排序后，下標i處的元素是8，下標j處的元素為54,接著j–,j處的元素為67，67>23滿足條件，j–,下標j處的元素為4，4<23不滿足條件，停止右側的比較，開始左側的比較，左側下標i處的元素為8，滿足條件，i++，下標i處的元素為6，6<23滿足條件，i++,下標i處的元素為34，34>23不滿足條件，交換下標i處是元素34與下標j處的元素4，交換后數組的元素為：
23，8，6，4，55，12，34，67，54，29
接著比較右邊j下標處的元素，34>23滿足條件，j–,下標j處的元素為12，12<23不滿足條件，左邊下標i處的元素為4，4<23滿足條件，i++,下標i處的元素為55，55>23不滿足條件，交換下標i處的元素55與下標j處的元素12，交換后數組的元素為：
23，8，6，4，12，55，34，67，54，29
接著比較右側下標j處的元素55，55>23滿足條件，j–,下標j處的元素為12，12<23不滿足條件，停止右側下標j的元素比較，此時左側的元素下標i 和右側的元素下標j都為同一個元素的下標，這時用flag與下標為i的元素進行交換，交換后元素的值為：
12，8，6，4，23，55，34，67，54，29
這樣完成了第一輪排序，實現了23左側比23小，右側比23大。下面以23左側的元素構成一個數組：
”12，8，6，4“
依舊選取12為flag,下標i處的元素為12，下標j處的元素為4，從右側開始比較，4<12,不滿足條件，停止下標j處的元素比較，開始下標i處的元素比較，12=12滿足條件，i++,下標i處的元素為8，8 <12滿足條件，i++,下標i處的元素為6，6<!2滿足條件，i++，下標i處的元素為4，此時下標i處的元素和下標j處的元素是同一個元素，停止下標i的比較，用flag與下標i處的元素4交換位置，交換后的數組：
”4，8，6，12“
此時12以左的元素小于12，這時以12以左的元素構成一個數組，
”4，8，6“
左起第一個元素4為flag,下標i處的元素為4，下標j處的元素為6，開始右側的元素比較，6 >4滿足條件，j–,下標j處的元素為8，8>4滿足條件，j–，下標j處的元素為4，此時下標i處的元素和下標j處的元素相等，交換flag與下標i處的元素，flag和下標i處的元素為同一個元素，此時，4右側的元素比4大，以右側的元素組成一個數組，
”8，6“
同理，flag為8，下標i處的元素為8，下標j處的元素為6，開始右側的比較，6<8不滿足條件，開始左側的比較，下標i處的元素為8，8==8滿足條件，i++，下標i處的元素為6，此時下標i和下標j為同一個元素的下標，交換flag和下標i的元素，交換后數組：
“6,8”
8左側比8小，此時在最開始以第一個元素23為標志得到的左側的數組為：
”4，6，8，12“
23右側的數組：
”55，34，67，54，29*
同理以第一個元素55為flag,下標i處的元素為55，下標j處的元素為29，開始右側的比較，29<55不滿足條件，開始左側的比較,下標i處的元素55，55等于55，i++，下標i處的元素為34，34<55滿足條件，i++,下標i處的元素為67，67>55不滿足條件，交換下標i和下標j處的元素，得到數組：
“55，34，29，54，67”
此時下標j處的元素為67，67 >55,滿足條件，j–，下標j處的元素為54，54<55不滿足條件，下標i處的元素為29，29<55滿足條件，i++，下標i處的坐標為54，下標i和下標j處的元素為同一個元素，交換flag與下標i處的元素得到數組：
“54，34，29，55，67”
這時55右側比55大，左側元素比55小，以左側元素構成數組：
“54，34，29”
第一個元素54為flag,下標i為54的下標，下標j為數組的右側最后一個元素的下標，開始右側的比較，下標j處的元素29<54不滿足條件，下標i處的元素54等于54，i++，下標i處的元素為34，34<54滿足條件，i++,下標i處的元素為29，下標i處的元素與下標j處的元素為同一個元素，交換小標i處的元素與flag得到：
“29，34，54”
54左側的元素比54小，以54左側的元素構成一個數組得到：
“29，34”
同樣flag為第一個元素，下標i為29的下標，下標j為右側最后一個元素34的下標，開始比較右側，34>29滿足條件，j–,下標j處的元素為29，此時下標i和下標j處的元素為同一個元素，交換flag與下標i處的元素，排序后
“29，34”
此時55左側的元素順序為：
“29，34，54”
55右側只有一個元素67，整個數組的排序已經排完，完整的順序為：
“4，6，8，12，23，29，34，54，55，67”
整個實現的比較就是上面所說。

實現

#include <QCoreApplication> #include <stdio.h>#if 0 void my_print(char text[]) {printf(">>>my_print()=%d\n",sizeof(text)); } int main(int argc, char *argv[]) {QCoreApplication a(argc, argv);char test[]="Welcome to China";my_print(test);printf(">>>main()=%d",sizeof(test));return 0; } #endif#if 0 #include <QVector> #include <QString> #include <QDebug> using namespace std;struct Grade {string name;int grade; };int main() {Grade subject[3] = {{ "English", 80 },{ "Biology", 70 },{ "History", 90 }};int sum = accumulate(subject, subject + 3, 0, [](int a, Grade b){return a + b.grade; });string strObject = accumulate(subject,subject+3,string(" "),[](string str1,Grade str2){return str1+str2.name;});//accumulate如果是字符串求和，第三個參數必須是string(" ")qDebug() << sum<<"strObject="<<strObject.data()/*.c_str()*/;//240system("pause");return 0; } #endif#include <iostream> using namespace std;void outputArr(int *arr,int count){for (int i = 0; i < count; ++i) {cout<<arr[i]<<" ";} }//快速排序 void quickSort(int *arr,int left,int right){//left-下標起始值，小標結束值if (left >= right) {return ;}int flag = arr[left];int i = left;int j = right;int temp;while (i < j) {while (i < j && arr[j] >= flag) {//不能排除相等的情況，否則不適用于含有重復元素--j;}while (i < j && arr[i] <= flag) {++i;}if (i < j) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}if (arr[i] == arr[j]) {//一輪比較結束后，i和j相等temp = arr[i];arr[i] = arr[left];arr[left] = temp;}quickSort(arr,left,i-1);quickSort(arr,i+1,right); }int main() {int nums[] = {23,1,34,4,6,78,33,9,5};quickSort(nums,0,6);//傳入下標的范圍outputArr(nums,9);cout<<endl;cout<<"==========================="<<endl;int nums1[] = {7,1,34,4,6,8,33,9,43,6};quickSort(nums1,0,9);outputArr(nums1,10);cout<<endl;return 0; }

以上便是實現。

總結

以上是生活随笔為你收集整理的c++中快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。