GeezerVison is showing github.com — cpp-algorithms/sorting/QuickSort.cpp at master · atwill007/cpp-algorithms

Expand file tree

QuickSort.cpp

Copy path

More file actions

Latest commit

History

53 lines (46 loc) · 1.51 KB

QuickSort.cpp

Copy path

File metadata and controls

53 lines (46 loc) · 1.51 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

#include <iostream>

#include <vector>

#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<double> vList = cinDoubleVector();

vector<double> quickSort(vector<double>);

vector<double> sortV = quickSort(vList);

coutDoubleVector(sortV);

return 0;

}

vector<double> quickSort(vector<double> vList)

{

if (vList.size() <= 1)

return vList;

double pivot = vList[0]; // 取第一个元素作为参考

vector<double> leftV;

vector<double> 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<double> 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;

}