快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，
基本思想：
任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該程序，直到所有元素都排列在相應位置上為止，
將區間按斬訓準值劃分為左右兩半部分的常見方式: Hoare法、挖坑法、前后指標法，
1. hoare版本
動圖理解：
選擇方式：
1.當選擇最左做key時，右邊先走，-->左右相遇時比key小，
2.當選擇最右做key時，左邊先走，-->左右相遇時比key大，
核心思路：
選擇左邊值為key，right先走，找比key小的值停下（跳過大的），left再走，找到比key大的值停下（跳過小的），交換 left 與 right 的值，直到left，right相遇，相遇點的值和key值交換，
int Partion1(int* a, int left, int right)
{
// 三數取中 -- 面對有序最壞情況，變成選中位數做key，變成最好情況
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
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[left], &a[keyi]);
return left;
}注意：
快速排序優化：三數取中法選key：三數取中位數不會使最大或最小做key
2.挖坑法
動圖理解：
選擇方式：
1.當選擇最左做key時，右邊先走，
2.當選擇最右做key時，左邊先走，
核心思路：
右邊找小，把比key小的值放進坑里，右邊形成新的坑；左邊找大扔到坑里，左邊形成新的坑，
// 挖坑法
int Partion2(int* a, int left, int right)
{
// 三數取中 -- 面對有序最壞情況，變成選中位數做key，變成最好情況
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int key = a[left];
//坑
int pivot = left;
while (left < right)
{
// 右邊找小, 放到左邊的坑里面
while (left < right && a[right] >= key)
{
--right;
}
a[pivot] = a[right];
pivot = right;
// 左邊找大，放到右邊的坑里面
while (left < right && a[left] <= key)
{
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}注意：
先往坑里填值，再改變坑的位置，
3. 前后指標法:
動圖理解：
選擇方式：
核心思路：
cur找到比key小的就停下來，++prev，再交換prev和cur位置的值，
prev要么緊跟著cur，要么緊跟著比key大的序列，
// 推薦掌握這個 -- 思想三種大家都要掌握
int Partion3(int* a, int left, int right)
{
// 三數取中 -- 面對有序最壞情況，變成選中位數做key，變成最好情況
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
return prev;
}快速排序優化
1. 三數取中法選key
2. 遞回到小的子區間時，可以考慮使用插入排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小區間優化，當分割到小區間時，不再用遞回分割思路讓這段子區間有序
// 對于遞回快排，減少遞回次數
if (right - left + 1 < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
//類似二叉樹遍歷，根左右
int keyi = Partion(a, left, right);
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}非遞回方法：
利用堆疊的結構處理區間，
// 遞回深度太深的程式，只能考慮改非遞回
void QuickSortNonR(int* a, int left, int right)
{
ST st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
int keyi = Partion3(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
if (begin < keyi - 1)
{
StackPush(&st, begin);
StackPush(&st, keyi - 1);
}
}
StackDestroy(&st);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/384268.html
標籤：其他