個(gè)人中心
退出
劍指offer之快速排序
1 快速排序
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
2 分析思路
很明顯，先是用到了 partition算法思想（前面的博客提到了），然后再把原始數(shù)據(jù)分成幾部分然后遞歸同樣用partition算法處理
3 代碼實(shí)現(xiàn)
1) 代碼實(shí)現(xiàn)方式1
#include <iostream>
#include <vector>
using namespace std;
/*
*交換函數(shù)
*/
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類型，我們記得要加引用，
*不然改變不了數(shù)據(jù)，這里和java傳遞ArrayList不一樣，ArrayList作為參數(shù)可以改變集合里面的值，
*所以C++如果函數(shù)傳遞非基本數(shù)據(jù)類型，一半都是帶引用的
*/
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;
}
//這里用的數(shù)組賦值，而不是直接用swap交換函數(shù)，那么下面的2步也是用數(shù)組賦值，而不是用swap交換函數(shù)
vector[start] = vector[end];
while (start < end && pivot >= vector[start])
{
++start;
}
vector[end] = vector[start];
}
vector[start] = pivot;
printVector(vector);
return start;
}
/*
*partition算法, 這里只不過增加了2個(gè)變量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;
}
//這里用的數(shù)組賦值，而不是直接用swap交換函數(shù)，那么下面的2步也是用數(shù)組賦值，而不是用swap交換函數(shù)
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);/*最后用同樣的方式對分出來的左邊的小組進(jìn)行同上的做法*/
// quickSort1(vector, i + 1, end);
return i;
}
/*
*partition算法, 這里只不過增加了2個(gè)變量i和j,然后使用了交換函數(shù)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交換函數(shù)，那么下面的是是也是swap交換函數(shù)
swap(vector[i], vector[j]);
}
swap(vector[i], vector[start]);
printVector(vector);
return i;
}
/**
*快速排序 調(diào)用第一個(gè)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);
}
/**
*快速排序 調(diào)用第二個(gè)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);
}
/**
*快速排序 調(diào)用第三個(gè)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;
}
運(yùn)行結(jié)果如下
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個(gè)parition函數(shù)，我們調(diào)用quickSortOne(v1, 0, v1.size() - 1)或者quickSortTwo(v1, 0, v1.size() - 1)或者quickSortThree(v1, 0, v1.size() - 1)其中的的一個(gè)，結(jié)果都是一樣。
作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)
分類導(dǎo)航