篇一

---

前言

快速排序和归并排序都是基于递归实现的经典排序算法，使用了递归调用来处理子问题。通过递归调用，算法能够自然地处理子问题，并将子问题的解组合成原问题的解。这种分而治之的策略使得代码更加直观和易于理解。总而言之递归实现快速，归并排序使得算法更加简洁，高效。
但递归调用涉及函数调用栈的使用，每次递归调用都会在栈上增加一个新的栈帧，用于保存函数参数、局部变量等信息。当递归深度较大时，会占用较多的内存空间。此外，频繁的函数调用会导致额外的时间开销，影响程序性能。
本篇先介绍快速排序的非递归

一、 回顾快排

快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比令一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。这个思想最先也是由 托尼·霍尔（Tony Hoare）最先提出的，下面依次会介绍挖坑法，前后指针法。

1.hoare法

1.选取一个基准值第一个元素或者最后一个元素（本文选取第一个）
2.定义两个指针left,right分别指针序列的开始和结尾
3.首先移动right指针，找到比基准值小的元素，接着移动left指针找到比基准值大的元素，然后在序列中交换left和right指针指向的元素（交替移动）直到left，right指针相遇
4.最后将相遇位置的值与基准值交换，从而分割成两个子序列，左序列中的元素都小于相遇位置元素，右序列中的元素都大于相遇位置元素。

（1）图示

1.选取第一个元素做key，初始化left,right.

2.移动right指针到比key小的元素，移动left指针到比key大的元素

3.交换left，right指针指向元素

4.left,right重复以上操作

5.交换left,right指向元素

6.left,right指针相遇停止操作

7.交换相遇位置与基准值key，这样左序列均小于相遇位置元素，右序列均大于相遇位置元素

（2）注意事项

以上演示了单趟排序的流程，但还有一些值得注意的地方

1.第一个元素做key，right指针先走（尾做key反之）

让right指针先走是确保在一次遍历中将数组分为小于基准和大于基准的两部分，且相遇位置小于基准值.

2.边界问题

在right指针在序列中找小于基准时，若右边的元素均大于基准值，会造成越界，死循环的情况，(left<right)确保了在相遇点停止移动

（3）代码

1.基准值优化（三数取中）

待排序数组已经部分有序或完全有序时，如果简单地选择第一个或最后一个元素作为基准，可能会导致划分过程不平衡，使得算法的性能退化到O(n^2)。
实现：选取序列中首元素，中间元素，尾元素获取它们之间次大的元素做为基准值

三数取中代码:

int GetMid(vector<int>& a, int begin, int mid, int end) {
	int a1 = a[begin];
	int a2 = a[mid];
	int a3 = a[end];
	if (a1 > a2) swap(a1, a2);
	if (a2 > a3) swap(a2, a3);
	if (a1 > a3) swap(a1, a3);
	return mid;
}

2.完整代码

int hoaresort(vector<int>& a, int begin, int end) {

	//三数取中
	int index = GetMid(a, begin, begin + (end - begin) / 2, end);
	swap(a[index], a[begin]);
	int key = begin;
	int left = begin, right = end;
	while (left < right) {
		//找小
		while (left < right && a[right] >= a[key])   right--;
		//找大
		while (left < right && a[left] <= a[key])    left++;
		if (left < right)
			swap(a[left], a[right]);
	}
	swap(a[left], a[key]);
	return left;
}

2.前后指针法

1.同样选取第一个元素作为基准值,定义前后指针cur,prev分时指向所需单趟排序的第二个元素和第一个元素
2.cur指针率先开始向后移动,若找到比基准值小的元素就将prev+1所指向的元素与cur指针所指向的元素交换,同时prev向后移动一个单位
3.最后当cur指针越界时,交换基准值与prev指针所指向的元素

（1)图示

1.初始化cur,prev指针

2.cur指针率先向后移动,找比基准值小的元素

3.将prev+1所指向的元素与cur所指向元素交换,prev指针同时向后移动一个单位

4.cur指针继续寻找比基准值小的元素

5.重复步骤3
6.cur指针继续寻找比基准值小的元素

7.重复步骤3

8.cur指针继续寻找比基准值小的元素

9.重复步骤3

10.最后cur指针在向后寻找小于key的元素时越界，即循环结束

11.交换prev所指向元素与基准值元素

前后指针法同样将序列分为两个子序列,左序列均小于prev所指向元素，右序列均大于prev所指向元素,直接上code

（2)代码

int pointsort(vector<int>& a, int begin, int end) {
	int prev = begin, cur = prev + 1;
	int key = begin;
	while (cur <= end) {
		if (a[cur] < a[key] && ++prev != cur) { // ++prev!=cur 避免交换同一元素
			swap(a[prev], a[cur]);
		}
		++cur;
	}
	swap(a[prev], a[key]);
	return prev;
}

3.挖坑法

1.初始化left,right指针分别指向序列的开头和结尾元素，并将一个元素存入key中，使第一个位置元素成为第一个坑位
2.right指针率先向左移动寻找比key小的元素，并将小于key的元素放入坑位中，自身产生新的坑位
3.接着left指针向右移动寻找比key大的元素，将大于key的元素放入新产生的坑位中，自身产生新坑位
4.最后将key放入left,right指针相遇的地方，从而实现单趟排序

（1)图示

1.第一个元素做为key，并成为坑位， 初始化left,right指针

2.right指针出发找小

3.将right指针指向的值放入坑位中，并产生新的坑位

4.left指针找大

5.将left指针指向的值放入坑位中，并产生新的坑位
6.right指针继续找key小的元素

7.将right指针指向的值放入坑位中，并产生新的坑位

8.left指针继续找大

9.将left指针指向的值放入坑位中，并产生新的坑位

10.right移动找小

11.将right指针指向的值放入坑位中，并产生新的坑位

12.最后将key值放入left,right指针相遇点

（2)动图演示

同样挖坑法也实现了单趟排序左序列均小于相遇点所指向元素，右序列均大于相遇点。下面是动图演示。

（3)代码

int holesort(vector<int>& a, int begin, int end) {
	int key = a[begin];
	int left = begin, right = end;
	int hole = begin;
	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;
}

二、 快排非递归

1.如何实现？

前面讲述了3种实现单趟排序的算法，接下来介绍如何实现快速排序的非递归实现。
在快速排序的递归实现中，每次函数调用都会保存子序列的状态（数组的起始和结束下标进行单趟排序），因此我们可以用栈模拟递归调用的过程。
下面这张图简单演示了栈实现快速排序的流程。（根据栈先进后出这一特性，所以先推入右区间，在推入左区间）

总之，栈在先进后出的原则下，通过存储和管理子数组的索引，使得非递归快速排序能够实现与递归版本相同的排序逻辑。在结合代码仔细理解

2.完整代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void print(vector<int>& a) {
	for (int x : a)
		cout << x << ' ';
	cout << endl;
}
//单趟排序
int partition(vector<int>& a, int begin, int end) {
	int prev = begin, cur = prev + 1;
	int key = begin;
	while (cur <= end) {
		if (a[cur] < a[key] && ++prev != cur) { // ++prev!=cur 避免交换同一元素
			swap(a[prev], a[cur]);
		}
		++cur;
	}
	swap(a[prev], a[key]);
	return prev;
}

void quicksort(vector<int>& a,int begin,int end ) {
	stack<int> st;
	st.push(end);
	st.push(begin);
    //当栈为空时整个序列已经有序
	while (!st.empty()) {
		int left = st.top(); st.pop();
		int right = st.top(); st.pop();
		int key = partition(a, left, right);
		//[left,key-1] [key+1,right] 单趟排序元素>=3
		if (key + 1 < right) {
			st.push(right);
			st.push(key+1);
		}
		if (left < key - 1) {
			st.push(key - 1);
			st.push(left);
		}
	}

}

int main() {
	vector<int> vec = { 5,7,2,9,3,1,8,4,6,10};
	print(vec);
	int n = vec.size()-1;
	quicksort(vec,0,n);

	print(vec);
	return 0;
}