vlambda博客
学习文章列表

本节分两个部分，第一部分为利用栈实现非递归快速排序，第二部分利用队列实现非递归快速排序。

非递归写法

介绍：

辅助实现：栈 。

        入栈出栈的过程跟递归的调用的逻辑是一样的，所以一般用栈实现非递归写法，因为他俩有血缘关系。

利用栈辅助理解递归的执行过程。可以完整展示逻辑。

图解过程如下：该图视频中有讲解。

代码如下：

#include <iostream>

#include <stack>

using namespace std;

stack<int> st;  //栈

void Sort(int* arr, int left, int right)

{

st.push(left);   //入栈

st.push(right);

while(!st.empty())  //栈不为NULL

{

right = st.top();

st.pop();

left = st.top();

st.pop();

int q = left, h = right;

while (q < h)  //两头找 交换

{

//h先--

while (q < h && arr[h] >= arr[left])

                        {

h--;

}

//q后++

while (q < h && arr[q] <= arr[left])

{

q++;

}

//相遇

if (q == h)

break;

//没相遇，就交换

int temp = arr[q];

arr[q] = arr[h];

arr[h] = temp;

}

// == 基数归位 

if (q != left)

{

int temp = arr[q];

arr[q] = arr[left];

arr[left] = temp;

}

//递归

//Sort(arr, left, q - 1);

if (left < q - 1)

{

st.push(left);   //入栈

st.push(q - 1);

}

//Sort(arr, h + 1, right);

if (h + 1 < right)

{

st.push(h+1);   //入栈

st.push(right);

}

}

}

int main(void)

{

int arr[10] = { 4,3,5,1,6,3,0,2,8,7 };

Sort(arr, 0, 9);

return 0;

}

队列：也是可以辅助实现递归的过程，但是其算法执行逻辑跟递归是不同的，所以一般被人忽略。

代码如下：

#include <iostream>

#include <queue>

using namespace std;

queue<int> qu;

void Sort(int* arr, int left, int right)

{

qu.push(left);   //入队

qu.push(right);

while (!qu.empty())  //队列不为NULL

{

left = qu.front();

qu.pop();

right = qu.front();

qu.pop();

int q = left, h = right;

while (q < h)  //两头找 交换

{

//h先--

while (q < h && arr[h] >= arr[left])

{

h--;

}

//q后++

while (q < h && arr[q] <= arr[left])

{

q++;

}

//相遇

if (q == h)

break;

//没相遇，就交换

int temp = arr[q];

arr[q] = arr[h];

arr[h] = temp;

}

// == 基数归位 

if (q != left)

{

int temp = arr[q];

arr[q] = arr[left];

arr[left] = temp;

}

//递归

//Sort(arr, left, q - 1);

if (left < q - 1)

{

qu.push(left);   //入栈

qu.push(q - 1);

}

//Sort(arr, h + 1, right);

if (h + 1 < right)

{

qu.push(h + 1);   //入栈

qu.push(right);

}

}

}

int main(void)

{

int arr[10] = { 4,3,5,1,6,3,0,2,8,7 };

Sort(arr, 0, 9);

return 0;

}