快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中
的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右
子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止
// 假設(shè)按照升序?qū)rray數(shù)組中[left, right)區(qū)間中的元素進(jìn)行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基準(zhǔn)值對array數(shù)組的 [left, right)區(qū)間中的元素進(jìn)行劃分
int div = partion(array, left, right);
// 劃分成功后以div為邊界形成了左右兩部分 [left, div) 和 [div+1, right)
// 遞歸排[left, div)
QuickSort(array, left, div);
// 遞歸排[div+1, right)
QuickSort(array, div+1, right);
}
上述為快速排序遞歸實(shí)現(xiàn)的主框架，發(fā)現(xiàn)與二叉樹前序遍歷規(guī)則非常像，同學(xué)們在寫遞歸框架時(shí)可想想二叉
樹前序遍歷規(guī)則即可快速寫出來，后序只需分析如何按照基準(zhǔn)值來對區(qū)間中數(shù)據(jù)進(jìn)行劃分的方式即可。
將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式有：
1. hoare版本
看懂了動圖那么我們的代碼實(shí)現(xiàn)如下
// Hoare
int PartSort1(int* a, int left, int right)
{
//int midi = GetMidi(a, left, right);
//Swap(&a[left], &a[midi]);
int keyi = left;
while (left < right)
{
// 找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
// 找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
// 三數(shù)取中
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
2.挖坑法
代碼實(shí)現(xiàn)如下
// 挖坑法
int PartSort2(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int key = a[left];
// 保存key值以后，左邊形成第一個(gè)坑
int hole = left;
while (left < right)
{
// 右邊先走，找小，填到左邊的坑，右邊形成新的坑位
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
// 左邊再走，找大，填到右邊的坑，左邊形成新的坑位
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
// 三數(shù)取中
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
3.前后指針版本
代碼實(shí)現(xiàn)如下
// 前后指針
int PartSort3(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int prev = left;
int cur = prev + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
// 三數(shù)取中
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
2.3.2 快速排序優(yōu)化文章來源：http://www.zghlxwxcb.cn/news/detail-717705.html
- 三數(shù)取中法選key
- 遞歸到小的子區(qū)間時(shí)，可以考慮使用插入排序
快速排序的特性總結(jié)： - 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 時(shí)間復(fù)雜度：O(N*logN)
- 空間復(fù)雜度：O(logN)
- 穩(wěn)定性：不穩(wěn)定
三路劃分與三數(shù)隨機(jī)取中的思想實(shí)現(xiàn)快速排序的再優(yōu)化
這是題目 我們按照上面所講的（這里我們使用快速排序的方法來實(shí)現(xiàn) 所以代碼可以拷貝粘貼 所以我們就不再繼續(xù)贅述）
看一下這個(gè)圖片 我們定義一個(gè)變量將key保存起來以便后續(xù)比較不會丟失key的數(shù)據(jù)
定義一個(gè)cur表示當(dāng)前數(shù)據(jù) 然后根據(jù)我的藍(lán)色字體部分思考一下 ++L，–R的各自的含義
最后就會形成一個(gè)左邊為小于key的數(shù) 中間為等于key的數(shù) 右邊為大于key的數(shù) 這樣做的好處是如果避免大量的重復(fù)數(shù)據(jù)帶來的不利影響 希望大家能夠理解
這樣以來 我們中間的和key相等的數(shù)據(jù)就不用再次遞歸了 只用遞歸左和右的兩組數(shù)據(jù)了 是不是很方便
但是這里還有一個(gè)問題就是三數(shù)取中我們還要再次優(yōu)化一下避免Leetcode判題太嚴(yán)格導(dǎo)致我們所有測試用例通過了 但是超時(shí)了
下面給大家看一下詳細(xì)代碼和報(bào)錯(cuò)示例
希望我的講解能夠最大限度的幫助到你 希望你今天收獲滿滿 我們下一篇文章再見！文章來源地址http://www.zghlxwxcb.cn/news/detail-717705.html
到了這里，關(guān)于【Leetcode刷題（數(shù)據(jù)結(jié)構(gòu)）】：三路劃分與三數(shù)隨機(jī)取中的思想實(shí)現(xiàn)快速排序的再優(yōu)化的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
