个人中心
退出
剑指offer之快速排序
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)其中的的一个，结果都是一样。
作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)
分类导航