/********************************************************************** *版權所有 (C)2014, cheng yang。 * *文件名稱:快速排序.cpp 數組實現 *內容摘要:無 *其它說明:無 *當前版本: V1.0 *作 者:cheng yang *完成日期: 20140625 * * 版本 修改時間 修改人 修改內容 ******************************************************************** * V1.0 20140625 cy 創建 **********************************************************************/ #include#include using namespace std; inline void swap(int &a, int &b)//是取地址,是要修改數組的!!!!! { int iTemp = a; a = b; b = iTemp; } /********************************************************************** *功能描述:數組的劃分 *輸入參數:數組,數組首下標,數組尾下標 *輸出參數:無 *返回值:主元下標 *其它說明:無 *修改日期 版本號 修改人 修改內容 * -------------------------------------------------------------- * ***********************************************************************/ int Partition(int ArrayInput[],int iFirst, int iLast) { int iKey = ArrayInput[iLast]; int j = iFirst-1 ; for (int i = iFirst; i != iLast; i++) { if (ArrayInput[i] <= iKey) { j++; if (j != i) { swap(ArrayInput[j], ArrayInput[i]); } } } swap(ArrayInput[iLast], ArrayInput[j + 1]); return j + 1; } /********************************************************************** *功能描述:quick sort *輸入參數:數組,數組首下標,數組尾下標 *輸出參數:無 *返回值:無 *其它說明:無 *修改日期 版本號 修改人 修改內容 * -------------------------------------------------------------- * ***********************************************************************/ void QuickSort(int ArrayInput[],int iFirst, int iLast) { if (iFirst < iLast) { int iIndex = Partition(ArrayInput,iFirst, iLast); QuickSort(ArrayInput, iFirst, iIndex - 1); QuickSort(ArrayInput,iIndex + 1, iLast); } } /**************************************************************** *功能描述: 主函數 * *輸入參數: 無 * *輸出參數: 無 * *返回值 :無 * *其他說明: 無 * *修改日期 版本號 修改人 修改內容 * ------------------------------------------------------------------ * ****************************************************************/ int main() { int ArrayInput[10] = { 2, 4, 1, 5, 11, 6, 9, 16, 23, 10 }; int iFirst = 0; int iLast = 9; QuickSort(ArrayInput,iFirst, iLast); int i = 0; while (i < 10) { cout << ArrayInput[i++] << endl; } system("pause"); }
容器實現
#include#include using namespace std; inline void swap(int &a, int &b) { int temp = a; a = b; b = temp; } template int Partition(vector & a, int istart, int iend) { int ipivot = a[iend]; int i = istart - 1; for (int j = istart; j != iend; j++) { if (a[j] <= ipivot) { i++; if (i != j) { swap(a[i], a[j]); } } } swap(a[iend], a[i + 1]); return i + 1; } template void QuickSort(vector & a, int istart, int iend) { if (istart< iend) { int ipivot_pos = Partition(a, istart, iend); QuickSort(a, istart, ipivot_pos - 1); QuickSort(a, ipivot_pos + 1, iend); } } int main() { vector a; int input{ 0 }; while (cin >> input) a.push_back(input); int istart = 0; int iend = a.size()-1;//輸入6個數,大小是6,數組下標別忘了減1啊 QuickSort(a, istart, iend); for (auto i = a.begin(); i != a.end(); i++) { cout << *i << endl; } system("pause"); return 0; }