快排

2019-11-06 09:07:02

字体：大中小

来源：转载

供稿：网友

快排是所有内部排序算法中平均性能最优的排序算法，其基本思想是基于分治法。本文首先实现了一个快排的基本程序，然后列举了一个关于快排的应用：最小的k个数。

1.快排算法实现

理论部分就不说了，直接上代码。程序中从无重复数字数组、带有重复数字的数组、单个数字的数组和空数组几方面测试了代码的完整性。代码：

#include<iostream>#include<vector>using namespace std;void QuickSort(vector<int> &array, int low, int high); //将数组[low high]区间排序int partition(vector<int> &array, int low, int high); //将数组[low high]区间以返回值位置划分为两部分，且通过调整数组中元素的位置使前一部分的元素值均比返回值位置的元素小，后一部分则相反。void test(vector<int> &array);int main(){ vector<int> v1 = { 3, 8, 7, 1, 2, 5, 6, 4 }; vector<int> v2 = { 3, 8, 6, 1, 2, 5, 6, 4 }; vector<int> v3 = { 3 }; vector<int> v4 = {}; test(v1); //功能测试 test(v2); test(v3); //边界测试 test(v4); //负面测试 return 0;}void test(vector<int> &array) { unsigned int lengthOfArray = array.size(); cout << "The original order of the array is:" << endl; for (int i = 0; i<lengthOfArray; i++) { cout << array.at(i) << ' '; } cout << endl; if (0 == lengthOfArray) cout << "The array is empty." << endl; else { QuickSort(array, 0, lengthOfArray - 1); cout << "The sorted order of the array is:" << endl; for (int i = 0; i < lengthOfArray; i++) cout << array.at(i) << ' '; cout << endl; } cout << endl;}void QuickSort(vector<int> &array, int low, int high) { if (low<high) { int pivotpos = partition(array, low, high); QuickSort(array, low, pivotpos - 1); QuickSort(array, pivotpos + 1, high); }}int partition(vector<int> &array, int low, int high) { int pivot = array.at(low); //选取数组low位置的元素作为枢轴值，进行划分 while (low < high) { while (low < high && array.at(high) >= pivot) --high; array.at(low) = array.at(high); while (low < high && array.at(low) <= pivot) ++low; array.at(high) = array.at(low); } array.at(low) = pivot; return low;}

2.快排应用：最小的k个数：

题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8 这8个数字，则最小的4个数字是1、2、3、4。此问题有多种解法，这里使用了基于快排一次排序分治的思想来解决此问题。

#include<iostream>#include<vector>using namespace std;void GetLeastNumber_1(vector<int> &inputArray, vector<int> &outputArray,const int k); int partition(vector<int> &array, int low, int high); //将数组[low high]区间以返回值位置划分为两部分，且通过调整数组中元素的位置使前一部分的元素值均比返回值位置的元素小，后一部分则相反。void test(vector<int> &inputArray,const int k);int main(){ vector<int> v1 = { 3, 8, 7, 1, 2, 5, 6, 4 }; vector<int> v2 = { 2, 8, 6, 1, 2, 5, 6, 4 }; vector<int> v4 = {}; test(v1, 3); //功能测试 test(v2, 3); test(v1, 1); //边界测试 test(v1, v1.size()); test(v4, 3); //负面测试 test(v1, 0); test(v1, v1.size()+1); return 0;}void test(vector<int> &inputArray,const int k) { unsigned int lengthOfinputArray = inputArray.size(); if(lengthOfinputArray<=0 || k<=0 || k>lengthOfinputArray) { cout << "Input Error!!!" << endl; return ; } cout << "The original array is:" << endl; for (int i = 0; i<lengthOfinputArray; i++) { cout << inputArray.at(i) << ' '; } cout << endl; vector<int> output; GetLeastNumber_1(inputArray, output, k); cout << "The least k numbers are:" << endl; for (int i = 0; i < k; i++) cout << output.at(i) << ' '; cout << endl; cout << endl;}void GetLeastNumber_1(vector<int> &inputArray, vector<int> &outputArray,const int k) { int lengthOfinputArray = inputArray.size(); int index = partition(inputArray, 0, lengthOfinputArray-1); while(index != k-1) { if(index > k-1) { index = partition(inputArray, 0, index-1); } else { index = partition(inputArray, index+1, lengthOfinputArray-1); } } for(int i=0; i<k; i++) { outputArray.push_back(inputArray.at(i)); } return ;}int partition(vector<int> &array, int low, int high) { int pivot = array.at(low); //选取数组low位置的元素作为枢轴值，进行划分 while (low < high) { while (low < high && array.at(high) >= pivot) --high; array.at(low) = array.at(high); while (low < high && array.at(low) <= pivot) ++low; array.at(high) = array.at(low); } array.at(low) = pivot; return low;}

上一篇：吐槽 - 20170228 - 年少无知的 bookmark

下一篇：将本地nodejs服务器的代码提交到github