作风建设年网站,品牌建设的目的,房地产网站建设联系方式,有九类商标可以做网站名吗1 快速排序
通过一趟排序将要排序的数据分割成独立的两部分#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小#xff0c;然后再按此方法对这两部分数据分别进行快速排序#xff0c;整个排序过程可以递归进行#xff0c;以此达到整个数据变成有序序列 2 分析…1 快速排序
通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列 2 分析思路
很明显先是用到了 partition算法思想前面的博客提到了然后再把原始数据分成几部分然后递归同样用partition算法处理 3 代码实现
1) 代码实现方式1
#include iostream
#include vectorusing namespace std;/**交换函数*/
void swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}/** 打印vector*/
void printVector(vectorint v)
{for (int i 0; i v.size(); i){std::cout v[i] \t;}std::cout std::endl;
}/**partition算法 记得如果这里是C我们传递的是vector类型我们记得要加引用*不然改变不了数据这里和java传递ArrayList不一样ArrayList作为参数可以改变集合里面的值*所以C如果函数传递非基本数据类型一半都是带引用的*/
int partitionOne(vectorint vector, int start, int end)
{if (start end){std::cout vector is empty or start end std::endl;return -1;}int pivot vector[start];while (start end){//我们先从尾巴开始while (start end pivot vector[end]){--end;}//这里用的数组赋值而不是直接用swap交换函数那么下面的2步也是用数组赋值而不是用swap交换函数vector[start] vector[end];while (start end pivot vector[start]){start;}vector[end] vector[start];}vector[start] pivot;printVector(vector);return start;
}/**partition算法, 这里只不过增加了2个变量i和j**/
int partitionTwo(vectorint vector, int start, int end)
{if (start end){return -1;}int i start;int j end;int pivot vector[start];while (i j){//我们先从尾巴开始while (i j pivot vector[j]){--j;}//这里用的数组赋值而不是直接用swap交换函数那么下面的2步也是用数组赋值而不是用swap交换函数vector[i] vector[j];while (i j pivot vector[i]){i;}vector[j] vector[i];}vector[i] pivot;printVector(vector);// quickSort1(vector, start, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/// quickSort1(vector, i 1, end);return i;
}/**partition算法, 这里只不过增加了2个变量i和j,然后使用了交换函数swap**/
int partitionThree(vectorint vector, int start, int end)
{if (start end){return -1;}int i start;int j end;int pivot vector[start];while (i j){//我们先从尾巴开始while (i j pivot vector[j]){--j;}while (i j pivot vector[i]){i;}//这里用的shiswap交换函数那么下面的是是也是swap交换函数swap(vector[i], vector[j]);}swap(vector[i], vector[start]);printVector(vector);return i;
}/***快速排序 调用第一个partitionOne*/
void quickSortOne(vectorint vector, int start, int end)
{if (vector.size() 0 || start end)return;int index partitionOne(vector, start, end);quickSortOne(vector, start, index - 1);quickSortOne(vector, index 1, end);
}/***快速排序 调用第二个partitionTwo */
void quickSortTwo(vectorint vector, int start, int end)
{if (vector.size() 0 || start end)return;int index partitionTwo(vector, start, end);quickSortTwo(vector, start, index - 1);quickSortTwo(vector, index 1, end);
}/***快速排序 调用第三个partitionThree*/
void quickSortThree(vectorint vector, int start, int end)
{if (vector.size() 0 || start end)return;int index partitionThree(vector, start, end);quickSortThree(vector, start, index - 1);quickSortThree(vector, index 1, end);
}int main()
{vectorint v1;//[5,9,2,1,4,7,5,8,3,6]v1.push_back(5);v1.push_back(9);v1.push_back(2);v1.push_back(1);v1.push_back(4);v1.push_back(7);v1.push_back(5);v1.push_back(8);v1.push_back(3);v1.push_back(6);std::cout old data print std::endl;printVector(v1);quickSortOne(v1, 0, v1.size() - 1);// quickSortTwo(v1, 0, v1.size() - 1);// quickSortThree(v1, 0, v1.size() - 1);std::cout after partitionOne std::endl;printVector(v1);return 0;
}
运行结果如下
old data print
5 9 2 1 4 7 5 8 3 6
3 4 2 1 5 7 5 8 9 6
1 2 3 4 5 7 5 8 9 6
1 2 3 4 5 7 5 8 9 6
1 2 3 4 5 7 5 8 9 6
1 2 3 4 5 7 5 8 9 6
1 2 3 4 5 6 5 7 9 8
1 2 3 4 5 5 6 7 9 8
1 2 3 4 5 5 6 7 9 8
1 2 3 4 5 5 6 7 8 9
1 2 3 4 5 5 6 7 8 9
after partitionOne
1 2 3 4 5 5 6 7 8 9
上面我们写了3个parition函数我们调用quickSortOne(v1, 0, v1.size() - 1)或者quickSortTwo(v1, 0, v1.size() - 1)或者quickSortThree(v1, 0, v1.size() - 1)其中的的一个结果都是一样。
