算法基本思想：

第一步：
教官面對一列無序的隊伍，他指著最右邊的一個人A說：“比他高的站他右邊，比他矮的站他左邊。”
完成之后，隊伍被他分割成了兩列，第一列：比A矮的在A的左邊；第二列：比A 高的在A 的右邊。
第二步：
他首先處理第一列，指著在A的左邊的一個人B（也就是第一列中的最右邊的一個人）
說到：“比B高的站他右邊，比B矮的站他左邊”。這樣完成之后，第一列又他成了兩列。
同樣的方法處理第二列，第二列也被分成兩列。
第二步完成之后，序列變成了四列。教官又以上面的方法處理這四列，如此循環下去。。。
那什么時候遞歸停止呢？那就是當最后被分割成的小列中只有一個人的時候遞歸停止，不用再分了。
當然，上例中考官是以最右邊的人為基準，進行分割的。你也可以隨便指一個人作為基準進行分割。

---

---

?

?

算法的實現：

?

//---------QuickSort.h-----------// class QuickSort { const int arraySize; float * array; public: QuickSort(int arraySize); ~ QuickSort(); void Initital(); int Partition(int first, int last); void Quicksort(int first, int last); void Sort(); void PrintIt(); };??

//-------------QuickSort.cpp------------// #include "iostream" #include "QuickSort.h" using namespace std; QuickSort::QuickSort(int Size):arraySize(Size) { } void QuickSort::Initital() { array = new float[arraySize]; for(int i = 0; i < arraySize; i++) { cout << "Input the number " << i+1 << " : "; cin >> array[i]; } cout << "Entered !" << endl; } int QuickSort::Partition(int first, int last) { int i, j; j = first - 1; for(i = first; i < last; i++) //Partition的精華思想，把last當做是標準 { if(array[i] < array[last]) { j ++; float temp = array[i]; array[i] = array[j]; array[j] = temp; } } float temp = array[last]; array[last] = array[++j]; array[j] = temp; return j; } void QuickSort::Quicksort(int first, int last) { int pivot; if(first < last) //算法的基本實現 { pivot = Partition(first, last); Quicksort(first, pivot - 1); Quicksort(pivot + 1, last); } } void QuickSort::Sort() { Quicksort(0, arraySize - 1); } void QuickSort::PrintIt() { cout << "After QuickSort :" << endl; for(int i = 0; i < arraySize; i ++) { cout << array[i] << " "; } cout << endl; } QuickSort::~QuickSort() { delete []array; }//------------main.cpp------------// #include "iostream" #include "QuickSort.h" using namespace std; int main() { int size; cout << "Enter the size of the array : "; cin >> size; if(size > 0) { QuickSort sort(size); sort.Initital(); sort.Sort(); sort.PrintIt(); system("pause"); } return 0; }

?

感想：

本文算法只是一個QuickSort的模板，可以根據情況來靈活應變，當然也有許多地方可以優化，在這就不再多述了

轉載于:https://www.cnblogs.com/kedebug/archive/2009/12/09/2791763.html

總結

以上是生活随笔為你收集整理的C++实现快速排序算法QuickSort()的全部內容，希望文章能夠幫你解決所遇到的問題。

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