???內(nèi)容專欄： 《數(shù)據(jù)結(jié)構(gòu)與算法篇》
??本文概括： 利用數(shù)據(jù)結(jié)構(gòu)棧(Stack)來模擬遞歸，實現(xiàn)快排的非遞歸版本；遞歸版本測試OJ題時，有大量重復(fù)元素樣例不能通過，導(dǎo)致性能下降，優(yōu)化快速排序通過將數(shù)組劃分為三個區(qū)域，可以更有效地處理重復(fù)元素。
??本文作者： 阿四啊
??發(fā)布時間：2023.8.28
快速排序(非遞歸)
1.為什么要學(xué)習(xí)非遞歸版本?
前面我們使用了三個版本實現(xiàn)快速排序，但都是屬于遞歸類型算法，函數(shù)調(diào)用會建立函數(shù)棧幀，遞歸深度取決于函數(shù)調(diào)用的次數(shù)。棧空間內(nèi)存有限，在處理大規(guī)模數(shù)據(jù)集時，遞歸深度的增加可能導(dǎo)致棧溢出的情況，所以在我們學(xué)會了遞歸版本之后，需要繼續(xù)強(qiáng)化學(xué)習(xí)非遞歸版本，利用之前學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)棧(Stack)來模擬實現(xiàn)。
2.基本思想
我們知道，我們在寫遞歸版本的時候，快速排序主要處理的是數(shù)組的不同區(qū)間，將問題分解為較小的子問題并在每個子問題上遞歸地應(yīng)用相同的排序算法來完成排序。
那么我們?nèi)绾问褂脳?Stack)來模擬實現(xiàn)呢?
核心思想是使用一個棧來存儲待排序的子數(shù)組的起始和結(jié)束下標(biāo)。在每次循環(huán)中，從棧中彈出一個子數(shù)組并執(zhí)行分區(qū)操作（根據(jù)基準(zhǔn)值(
key)，劃分區(qū)間，這一步驟即遞歸版本寫的Partition函數(shù)），選然后根據(jù)分區(qū)結(jié)果將未處理的左右子數(shù)組的下標(biāo)壓入棧中，直到棧為空為止。
3.算法分析
??①：
??②：
??③：繼續(xù)重復(fù)以上步驟，直到棧中的數(shù)據(jù)為空。
4.代碼實現(xiàn)
因為涉及到使用棧，而本篇數(shù)據(jù)結(jié)構(gòu)基于C語言講解，所以講自己實現(xiàn)的棧的文件源代碼也順便放在這。
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//hoare版本
int Partition1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
//注意： 要加上left < right 否則會出現(xiàn)越界
//若不判斷等于基準(zhǔn)值，也會出現(xiàn)死循環(huán)的情況
//右邊找小
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;
}
void QuicksortNonR(int* a, int begin, int end)
{
Stack st;
StackInit(&st);
//注意棧的順序是后進(jìn)先出，需要倒著放進(jìn)去，正著拿出來
//將排序數(shù)組的起始和末端下標(biāo)入棧
StackPush(&st, end);
StackPush(&st, begin);
//棧不為空一直循環(huán)
while (!StackEmpty(&st))
{
//彈出子區(qū)間(左右兩個下標(biāo))
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
//執(zhí)行分區(qū)操作
int keyi = Partition1(a, left, right);
//[left,keyi - 1] keyi [keyi + 1, right]
//注意只剩一個數(shù)或區(qū)間不存在則停止入棧
if (keyi + 1 < right)
{
StackPush(&st,right);
StackPush(&st,keyi + 1);
}
if (left < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
}
int main()
{
int a[] = { 9,6,7,1,4,5,5,2,10,1,6,3,7 };
QuicksortNonR(a, 0, sizeof a / sizeof(int) - 1);
PrintArray(a, sizeof a / sizeof(int));
}
棧
相關(guān)函數(shù)聲明：
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int DataType;
typedef struct Stack
{
DataType* a;
int top;
int capacity;
}Stack;
//棧的初始化
void StackInit(Stack* pst);
//入棧
void StackPush(Stack* pst,DataType x);
//出棧
void StackPop(Stack* pst);
//棧的銷毀
bool StackEmpty(Stack* pst);
//獲取棧頂元素
DataType StackTop(Stack* pst);
//獲取棧元素個數(shù)
int StackSize(Stack* pst);
//棧的銷毀
void StackDestroy(Stack* pst);
相關(guān)函數(shù)實現(xiàn)：
#define _CRT_SECURE_NO_WARNINGS
#include "stack.h"
//棧的初始化
void StackInit(Stack* pst)
{
assert(pst);
pst->a = NULL;
//pst->top = -1;//棧頂元素的位置
pst->top = 0;//棧頂元素的下一個位置
pst->capacity = 0;
}
//入棧
void StackPush(Stack* pst,DataType x)
{
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : (pst->capacity) * 2;
DataType* tmp = (DataType*)realloc(pst->a, sizeof(DataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail\n");
return;
}
else
{
pst->a = tmp;
pst->capacity = newCapacity;
}
}
pst->a[pst->top++] = x;
}
//出棧
void StackPop(Stack* pst)
{
assert(pst);
pst->top--;
}
//判斷棧是否為空
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
//獲取棧頂元素
DataType StackTop(Stack* pst)
{
return pst->a[pst->top - 1];
}
//獲取棧元素個數(shù)
int StackSize(Stack* pst)
{
return pst->top;
}
//棧的銷毀
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
總結(jié)
時間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(logN)
??注意：盡管使用棧實現(xiàn)了遞歸過程，但棧的使用本質(zhì)上是在模擬遞歸調(diào)用棧。這種方法可以避免遞歸深度過大導(dǎo)致棧溢出的問題，并且在一些情況下比遞歸版本更有效。
遞歸版本優(yōu)化(三路劃分)
1.缺陷問題：
下面給出一道力扣OJ題：??傳送鏈接:912.排序數(shù)組
題目要求就是給定一些數(shù)據(jù)，將亂序的數(shù)組排列為升序。我們用希爾排序、歸并排序、堆排序……一般效率較高的都可以跑過，但是唯獨快排用遞歸、非遞歸都不能跑過！就很離譜，因為快排有名，也就是這題故意針對快排，下面利用寫出的遞歸版本的快排去跑這個OJ。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三數(shù)取中
int GetMidIndax(int* a,int left, int right)
{
int mid = left + (rand() % (right - left));
if (a[mid] > a[left])
{
if (a[right] > a[mid]) return mid;
else if (a[right] > a[left]) return right;
else return left;
}
else //a[mid] < a[left]
{
if (a[right] < a[mid]) return mid;
else if (a[right] < a[left]) return right;
else return left;
}
}
//hoare版本
int Partition1(int* a, int left, int right)
{
int midi = GetMidIndax(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[left], &a[keyi]);
return left;
}
//快排(遞歸版本)
void QuickSort(int* a, int begin, int end)
{
if (begin >= end) return;
int keyi = Partition1(a, begin, end);
//前序遍歷
//遞歸基準(zhǔn)值左邊的區(qū)間
QuickSort(a, begin, keyi - 1);
//遞歸基準(zhǔn)值右邊的區(qū)間
QuickSort(a, keyi + 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
QuickSort(nums, 0, numsSize - 1);
*returnSize = numsSize;
return nums;
}
我們發(fā)現(xiàn)這題一共21個測試用例，只通過了17個，顯示超出時間限制，并且nums里出現(xiàn)了很多2，因為有大量重復(fù)元素樣例不能通過，這樣的基準(zhǔn)值key一直是處于數(shù)組第一個位置，導(dǎo)致性能下降，出現(xiàn)了最壞的情況，時間復(fù)雜度為O(N2)
文章來源：http://www.zghlxwxcb.cn/news/detail-679060.html
2.解決方案：
- [----------------------------------------------------------------------------------------------------------------------------------------]
基本思想：三路劃分通過將數(shù)組劃分為三個部分來解決這個問題：小于、等于和大于基準(zhǔn)值的元素。文章來源地址http://www.zghlxwxcb.cn/news/detail-679060.html
- 用隨機(jī)值三數(shù)取中法選擇一個基準(zhǔn)值
key。- 定義三個指針變量：
left、cur、right，left的初始值為區(qū)間的起始位置，cur指針的初始值為left + 1，right指針的初始值為區(qū)間的末尾位置。- 遍歷數(shù)組，通過與基準(zhǔn)值的比較將元素分成三部分：
- 如果當(dāng)前元素小于
key，將它與left指針?biāo)傅奈恢媒粨Q，然后將left指針和cur指針都向右移動。- 如果當(dāng)前元素等于
key，將cur指針向右移動。- 如果當(dāng)前元素大于
key，將它與right指針?biāo)傅奈恢媒粨Q，然后將right指針向左移動。left指針和right指針之間的區(qū)域(包含left和right)即為與key相等的所有元素，然后前序遍歷，對left指針左邊區(qū)域進(jìn)行遞歸，right指針右邊區(qū)域進(jìn)行遞歸。- 最終，數(shù)組會被劃分為三個區(qū)域：小于
key區(qū)域 、等于key區(qū)域 和大于key區(qū)域。
3.代碼參考
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int GetMidIndax(int* a,int left, int right)
{
int mid = left + (rand() % (right - left));
if (a[mid] > a[left])
{
if (a[right] > a[mid]) return mid;
else if (a[right] > a[left]) return right;
else return left;
}
else //a[mid] < a[left]
{
if (a[right] < a[mid]) return mid;
else if (a[right] < a[left]) return right;
else return left;
}
}
//三路分割 左 l r 右
void QuickSort(int* a, int begin, int end)
{
if (begin >= end) return;
int left = begin;
int right = end;
int cur = left + 1;
int mid = GetMidIndax(a, begin, end);
Swap(&a[mid],&a[left]);
int key = a[left];
while (cur <= right)
{
if (a[cur] < key)
{
Swap(&a[cur], &a[left]);
left++;
cur++;
}
else if (a[cur] > key)
{
Swap(&a[cur], &a[right]);
right--;
}
else //a[cur] == key
{
cur++;
}
}
// [begin left- 1],[left,right],[right + 1,end]
QuickSort(a, begin, left - 1);
QuickSort(a, right + 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
srand(time(NULL));
QuickSort(nums, 0, numsSize - 1);
*returnSize = numsSize;
return nums;
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法篇】手撕八大排序算法之快排的非遞歸實現(xiàn)及遞歸版本優(yōu)化(三路劃分)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[ 數(shù)據(jù)結(jié)構(gòu) -- 手撕排序算法第二篇 ] 冒泡排序](https://imgs.yssmx.com/Uploads/2024/02/501879-1.png)
