剑指offer之快速排序
【摘要】 1 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2 分析思路
很明显，先是用到了 partition算法思想（前面的博客提到了），然后再把原始数据分...
1 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2 分析思路
很明显，先是用到了 partition算法思想（前面的博客提到了），然后再把原始数据分成几部分然后递归同样用partition算法处理
3 代码实现
1) 代码实现方式1
-
#include <iostream>
-
#include <vector>
-
-
using namespace std;
-
-
/*
-
*交换函数
-
*/
-
void swap(int* a, int* b)
-
{
-
int temp = *a;
-
*a = *b;
-
*b = temp;
-
}
-
-
/*
-
* 打印vector
-
*/
-
void printVector(vector<int> 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(vector<int>& 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(vector<int>& 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(vector<int>& 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(vector<int>& 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(vector<int>& 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(vector<int>& 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()
-
{
-
vector<int> 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)其中的的一个，结果都是一样。
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/102634525
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）