#include #include #include "./lib/DoubleVector.h" using namespace std; /** * 快速排序 * * 整个排序过程只需要三步： *　　（1）在数据集之中，选择一个元素作为"基准"（pivot）。 *　 （2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。 *　　（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止 * 参考链接: https://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html */ int main() { vector vList = cinDoubleVector(); vector quickSort(vector); vector sortV = quickSort(vList); coutDoubleVector(sortV); return 0; } vector quickSort(vector vList) { if (vList.size() <= 1) return vList; double pivot = vList[0]; // 取第一个元素作为参考 vector leftV; vector rightV; for (int i = 1; i < vList.size(); i++) { cout << "for " << i << endl; if (vList[i] < pivot) // cout << "qs: " << leftV[leftV.size()] << endl; // leftV[leftV.size()] = vList[i]; leftV.insert(leftV.end(), vList[i]); else rightV.insert(rightV.end(), vList[i]); } vector newV; leftV = quickSort(leftV); rightV = quickSort(rightV); newV.insert(newV.begin(), leftV.begin(), leftV.end()); newV.insert(newV.end(), pivot); newV.insert(newV.end(), rightV.begin(), rightV.end()); return newV; }