1. Toy模板网首页
  2. > Toy博客

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）

9月前 作者：花想云 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

目录

1. hoare法

方法与步骤

代码实现

2. 挖坑法

方法与步骤

代码实现

3. 前后指针法

方法与步骤

代码实现 

4. 快速排序的缺点与优化

1.快速排序的缺点

2.快速排序的优化

① 三数取中法选 key

代码实现

② 小区间优化

代码实现

5. 快速排序的非递归实现

附录﹡完整源码

快速排序递归实现

快速排序非递归实现

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

快速排序是霍尔大佬在1962年提出的排序方法，因其出色的排序效率使得它成为使用最广泛的排序算法。快速排序之所以敢叫做快速排序，自然是有一定的道理，今天我们就来看看快速排序是如何凌驾于其它算法之上的。

快速排序的基本思想是：任取待排序数列中的一个数作为 key 值，通过某种方法使得 key 的左边所有的数都比它小，右边的数都比它大；以 key 为中心，将 key 左边的数列与右边的数列取出，做同样的操作（取 key 值，分割左右区间），直至所有的数都到了正确的位置。

上述所提到的某种方法可以有很多种，例如：hoare法、挖坑法、前后指针法。它们虽然做法不相同，但做的都是同一件事——分割出 key 的左右区间（左边的数比 key 小，右边的数比 key 大）。

我们首先来看看霍尔大佬所用的方法——hoare法。

1. hoare法

方法与步骤

以数列 6，1，2，7，9，3，4，5，8，10 为例：

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言1.取最左边为 key ，分别有 left 和 right 指向数列的最左端与最右端；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

2. right 先走，找到比 key 小的数就停下来；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

3. left 开始走，找到比 key 大的数就停下来；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

4. 交换 left 与 right 所在位置的数；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

5.重复上述操作，right 找小，left 找大，进行交换；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

6. right 继续找小；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

7. left 继续找大，若与 right 就停下来；

8.交换二者相遇位置与 key 处的值；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

此时一趟排序就完成了，此时的数列有两个特点：

1. key 所指向的值（6）已经到了正确的位置；

2. key 左边的数字都比 key 要小，右边的都比 key 要大；

接下来就是递归的过程了，分别对左右区间进行同样的操作：

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

代码实现

知道了详解步骤，用代码来实现并不困难，但是有很多很多的细节需要注意。（这里的代码未经优化，当前的代码有几种极端的情况不能适应）

void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

void QuickSort(int* a, int begin, int end)
{
    //数列只有一个数，或无数列则返回
	if (begin >= end)
	{
		return;
	}

	int left = begin;
	int right = end;

	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]);

	QuickSort(a, begin, left - 1);
	QuickSort(a, left + 1, end);
}

2. 挖坑法

挖坑法相比于hoare法，思路上更为简单易懂。

方法与步骤

还是以同样的数列 6，1，2，7，9，3，4，5，8，10 为例：

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

1. 先将第一个数存放到 key 中，形成一个坑位：分别有 left 和 right 指向数列的最左端与最右端； 

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

2.  right 先走，找到比 key 小的数，将该数丢到坑里；同时又形成了一个新的坑；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

3. left 开始走，找到比 key 大的数，将该数丢到坑里；同时形成一个新的坑；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

 4. right继续找小，进行重复的操作； 

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

5. left 找大；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言6. right 找小；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言7. left 找大；

8.若二者相遇就停下来；将 key 值放入坑；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

至此，一趟排序已经完成，我们发现此时的数列与hoare具有相同的特点：

1. key 所指向的值（6）已经到了正确的位置；

2. key 左边的数字都比 key 要小，右边的都比 key 要大；

挖坑法、hoare、前后指针法完成一趟排序后都具有相同的特点，所以不同版本的快速排序不一样的只有单趟排序的实现，总体思路都是相同的。

代码实现

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int left = begin;
	int right = end;

	int key = a[left];
	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;

	QuickSort(a, begin, hole - 1);
	QuickSort(a, hole + 1, end);
}

3. 前后指针法

方法与步骤

以同样的数列为例：

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言1. 取第一个值为 key ；有 prev 和 cur 分别指向数列开头和 prev 的下一个数；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言2. cur 先走，找到比 key 小的数就停下来；

3. ++prev ，交换 prev 与 cur 位置的数；（前两次无需交换，因为自己与自己换没有意义）

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言4. 重复此步骤；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言5. 直到 cur 走完整个数列，交换 prev 与 key 处的值；

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

至此，第一趟排序就结束了，又是与前两种方法相同的结果；

代码实现 

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int prev = begin;
	int cur = prev + 1;

	int keyi = begin;

	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		
		cur++;
	}

	Swap(&a[keyi], &a[prev]);
	keyi = prev;

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

4. 快速排序的缺点与优化

1.快速排序的缺点

我们用三种方式实现了快速排序，其实这三种方式并无明显的优劣之分。但是我们前面设计的快速排序其实是有两个缺点的：

1.在最坏情况下它的的效率极慢；

2.在数据量太大时会造成栈溢出。

那么什么情况是最坏情况呢？答案是，当数据本身就是有序的时候（无论是逆序还是顺序）。在最坏情况下，每次我们的 key 值都是最大或者最小，这样就会使 key 与数列的每个数都比较一次，它的时间复杂度为 O(n^2);

为什么会发生栈溢出呢？因为我们的快速排序是利用递归实现的，有递归调用，就要建立函数栈帧，并且随着递归的深度越深所要建立的函数栈帧的消耗就越大 。如这幅图所示：

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言

2.快速排序的优化

① 三数取中法选 key

为了应对最坏情况会出现时间复杂度为 O(N^2) 的情况，有人提出了三数取中的方法。

旧方法中，我们每次选 key 都是数列的第一个元素。三数取中的做法是，分别取数列的第一个元素、最后一个元素和最中间的元素，选出三个数中不是最大也不是最小的那个数当作 key 值。

有了三数取中，之前的最坏情况立马变成了最好情况。

代码实现

由于hoare法、挖坑法、前后指针法最终的效果都相同且效率差异很小，所以就任意选取一个为例，其余两者都类似。

//三数取中的函数
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // a[begin] > a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}
//hoare法
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int mid = GetMidIndex(a, begin, end);
	Swap(&a[mid], &a[begin]);

	int left = begin;
	int right = end;
	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]);

	QuickSort(a, begin, left - 1);
	QuickSort(a, left + 1, end);
}

② 小区间优化

随着递归的调用越深入，此时有个很大的缺点就是函数栈帧的消耗很大。但是同时又有一个好处，就是越往下，数列就越接近有序，且此时每个小区间的数据个数特别少。

那么有什么办法可以取其长处避其短处呢？不知道你是否还记得插入排序的特点——数据越接近有序，效率就越高。并且，在数据量极少的情况下，时间复杂度为 O(N^2) 的插入排序与时间复杂度为 O(N*log N) 的快速排序基本没有什么区别。所以，我们干脆就在排序数据量少的数列时，采用插入排序代替。

代码实现

//三数取中的函数
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // a[begin] > a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

//插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)         //大于tmp，往后挪一个
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;          //把tmp插入空隙
	}
}

//hoare法
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	if ((end - begin + 1) < 15)
			{
				// 小区间用直接插入替代，减少递归调用次数
				InsertSort(a+begin, end - begin + 1);
			}
	else
	{
		int mid = GetMidIndex(a, begin, end);
		Swap(&a[mid], &a[begin]);

		int left = begin;
		int right = end;
		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]);

		QuickSort(a, begin, left - 1);
		QuickSort(a, left + 1, end);
	}
}

两外两种方法的代码实现已打包完成，可在文末直接取用。

5. 快速排序的非递归实现

快速排序的非递归思路与递归相差无几，唯一不同的是，非递归用栈或队列模拟函数递归建立栈帧的过程。

void QuickSortNonR(int* a, int begin, int end)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort1(a, left, right);//三种方法任选其一
		//int keyi = PartSort2(a, left, right);
		//int keyi = PartSort3(a, left, right);

		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}

		if (left < keyi - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
	}

	StackDestroy(&st);
}

附录﹡完整源码

快速排序递归实现

//交换函数
void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

//三数取中
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // a[begin] > a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

//插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)         //大于tmp，往后挪一个
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;          //把tmp插入空隙
	}
}

// Hoare法
int PartSort1(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int left = begin, right = end;
	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]);
	keyi = left;

	return keyi;
}

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int left = begin, right = end;
	int key = a[left];
	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;
}

//前后指针法
int PartSort3(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int keyi = begin;
	int prev = begin, cur = begin + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

//快速排序（递归）
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	if ((end - begin + 1) < 15)
	{
		// 小区间用直接插入替代，减少递归调用次数
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort1(a, begin, end);
		//int keyi = PartSort2(a, begin, end);
		//int keyi = PartSort3(a, begin, end);

		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

快速排序非递归实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;  //动态开辟数组
	int capacity; //记录栈的容量大小
	int top; //记录栈顶的位置
}Stack;

//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);


// Hoare法
int PartSort1(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int left = begin, right = end;
	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]);
	keyi = left;

	return keyi;
}

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int left = begin, right = end;
	int key = a[left];
	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;
}

int PartSort3(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int keyi = begin;
	int prev = begin, cur = begin + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSortNonR(int* a, int begin, int end)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort1(a, left, right);//三种方法任选其一
		//int keyi = PartSort2(a, left, right);
		//int keyi = PartSort3(a, left, right);

		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}

		if (left < keyi - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
	}

	StackDestroy(&st);
}

//栈的实现_函数定义

void StackInit(Stack* ps)
{
	assert(ps);
	//初始化时，可附初值，也可置空
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	//若并未对ps->a申请内存，则无需释放
	if (ps->capacity == 0)
		return;
	//释放
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
	assert(ps);
	//若容量大小等于数据个数，则说明栈已满，需扩容
	if (ps->capacity == ps->top)
	{
		//若为第一次扩容，则大小为4，否则每次扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//压栈
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//出栈
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//返回栈顶的数据
	return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	//返回top
	return ps->top == 0;
}

『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）,新星计划免费学习专栏·数据结构与算法,排序算法（C语言版）,排序算法,算法,c语言文章来源地址https://www.toymoban.com/news/detail-637674.html

到了这里，关于『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 『初阶数据结构 • C语言』④ - 冒泡排序

    『初阶数据结构 • C语言』④ - 冒泡排序

      本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余，我决定把这本书精彩的部分摘录出来与大家分享。      本章内容 写在前面 1.冒泡排序 2.冒泡排序实战 3.冒泡排序的实现 4.冒泡排序的效率 5.二次问题 6.线性解决 7.总结     大 O记法能客观地衡量

    2024年02月16日
    浏览(45)
  • 『初阶数据结构 • C语言』⑤ - 选择排序

    『初阶数据结构 • C语言』⑤ - 选择排序

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余，我决定把这本书精彩的部分摘录出来与大家分享。     目录 写在前面 1.选择排序 2.选择排序实战 3.选择排序的实现 4.选择排序的效率 5.忽略常数 6.大O的作用 7.总结     大 O 是一种能够比较算法效

    2024年02月14日
    浏览(45)
  • 『初阶数据结构 • C语言』⑬ - 堆排序详解【附完整源码】

    『初阶数据结构 • C语言』⑬ - 堆排序详解【附完整源码】

     = 目录 0.写在前面 1.什么是堆？ 2. 堆排序 2.1 建堆 2.1.1 AdjustUp（向上调整算法） 2.1.2 AdjustDown（向下调整算法） 2.2 两种建堆算法的时间复杂度 2.2.1 AdjustUp建堆的时间复杂度 2.2.2 AdjustDown建堆的时间复杂度 2.3 排序 3.堆排序的时间复杂度 完整源码 你是否对堆排序早有耳闻？身

    2024年02月16日
    浏览(37)
  • 第11章：C语言数据结构与算法初阶之排序

    第11章：C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 ：所谓排序，就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的操作。 稳定性 ：假定在待排序的记录序列中，存在多个具有相同的的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，

    2024年02月12日
    浏览(47)
  • 【数据结构】—从冒泡排序丝滑过度快速排序（含C语言实现）

    【数据结构】—从冒泡排序丝滑过度快速排序（含C语言实现）

                                            食用指南：本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了： C语言                                        ♈️ 今日夜电波：靴の花火—ヨルシカ            

    2024年02月08日
    浏览(39)
  • 数据结构__＜八大排序＞ __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序（C语言实现）

    数据结构__＜八大排序＞ __插入排序 |希尔排序 |选择排序 |堆排序 |快速排序 |归并排序（C语言实现）

    目录 插入排序  希尔排序 选择排序 堆排序 冒泡排序 快速排序 hoare法 挖坑法 前后指针法 快排特性总结 三数取中优化 小区间优化 快排非递归 归并排序 归并排序非递归 计数排序 总结 OJ测试 1、元素集合越接近有序，直接插入排序算法的时间效率越高 2、时间复杂度：O(N^2

    2023年04月09日
    浏览(87)
  • 【数据结构初阶】九、五种比较排序的讲解和实现（直接插入 \ 希尔 \ 直接选择 \ 堆 \ 冒泡 -- C语言）

    【数据结构初阶】九、五种比较排序的讲解和实现（直接插入 \ 希尔 \ 直接选择 \ 堆 \ 冒泡 -- C语言）

    ========================================================================= 相关代码gitee自取 ： C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 ： 【数据结构初阶】八、非线性表里的二叉树（二叉树的实现 -- C语言链式结构）-CSDN博客  ====

    2024年02月08日
    浏览(51)

  • 数据结构（C语言实现）——常见排序算法的基本思想及实现（快速排序的三种方法和优化及非递归实现快速排序）

    生活中几乎处处都会用到排序，比如：网购时的店铺顺序，学生成绩的排名等，今天我们就来学习数据结构中常见的几种排序算法。 排序 ：所谓排序，就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的操作。 稳定性 ：假定在待排序的记录序列

    2023年04月24日
    浏览(66)
  • 数据结构初阶--排序2

    数据结构初阶--排序2

    本篇文章将继续介绍快排，归并等排序算法以及其变式。 快速排序是Hoare于1962年提出的一种 二叉树结构 的交换排序方法。 其基本思想为：任取待排序元素序列中的某元素作为 基准值 ，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序

    2024年02月16日
    浏览(36)
  • 【数据结构初阶】八大排序(三)——归并排序&&计数排序

    【数据结构初阶】八大排序(三)——归并排序&&计数排序

    大家好我是沐曦希💕 往期博客：【数据结构初阶】八大排序(一)——希尔排序堆排序直接插入排序直接选择排序 【数据结构初阶】八大排序(二)——快速排序冒泡排序 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一

    2024年02月03日
    浏览(133)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包