根據算法導論上的流程，將數組最后一個數作為主元，i和j都是從start往end移動。

void QuickSort(T*source,size_t length){if(!source){return;}QSort(source,0,length-1); } template<typename T> void Qsort(T*source,size_t start,size_t end){if(start<end){int pivot = Partition(source,start,end);Qsort(source,start,pivot-1);Qsort(source,pivot+1,end);} } template<typename T> size_t Partition( T*source, int start, int end ){if(start>end || !source){throw std::runtime_error("Invalid Input");}//T temp = source[start];size_t i = start-1;for(size_t j = start;j<end;j++){if(source[j]<=source[end]){i++;swap(source[j],source[i]);}}swap(source[i+1],source[end]);return i+1; }

如果，需要記錄原數組的位置標記。下面的程序已數組的第一個為主元，i從start往后指示第一個大于主元的位置，j從end往前指示第一個小于主元的位置，每次交換數組的兩個位置的數據，id記錄數組當前的數據是未排序前數組的哪一項。

template <typename T> void QuickSort( T*source, size_t* id, size_t length ) {if(!source || length < 2)return;QSort( source, id, 0, length -1); }template <typename T> void QSort( T*source, size_t* id, int start, int end ) {if(start < end){int pivot = Partition(source, id, start, end);QSort(source, id, start, pivot-1);QSort(source, id, pivot+1, end);} } template <typename T> size_t Partition( T*source, size_t* id, int start, int end ) {if(start > end || !source)throw std::runtime_error("Invalid Input");T temp = source[start];size_t tmpID = id[start];while(start < end){while(start < end && source[end] >= temp)end--;source[start] = source[end];id[start] = id[end];while(start < end && source[start] <= temp)start++;source[end] = source[start];id[end] = id[start];}source[start] = temp;id[start] = tmpID;return start; }

?

總結

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

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