排序算法(4)之快速排序(2)

  • 开发
  • 18

 个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

排序算法(4)之快速排序(2)

收录于专栏【数据结构初阶】
本专栏旨在分享学习数据结构学习的一点学习笔记，欢迎大家在评论区交流讨论💌

目录

前置说明

1.快速排序的优化

测试代码

1.hoare版本

2.挖坑法

3.前后指针法

1.1三数取中

1.2小区间优化

优化后的快速排序

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

完整代码:

3.总结

前置说明

大家对快排还不是很了解的可以先去看--排序算法(4)之快速排序(1)-CSDN博客

1.快速排序的优化

上章节我们说到了快排有三个版本,分别是hoare版本,挖坑法和前后指针法,现在我就分别测试一下它们的性能.

测试代码

测试链接--912. 排序数组 - 力扣（LeetCode）

1.hoare版本

代码展示:

void Swap(int* n, int* m)
{
    int p = *n;
    *n = *m;
    *m = p;
}
//hoare版本
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		//右边找小
		while (begin < end && a[end] >= a[keyi])
		{
			end--;
		}
		//左边找大
		while (begin < end && a[begin] <= a[keyi])
		{
			++begin;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[keyi], &a[begin]);
	keyi = begin;
	//[left,keyi-1] keyi [keyi+1, right]
	QuickSort1(a, left, keyi - 1);
	QuickSort1(a, keyi + 1, right);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
    (*returnSize) = numsSize;
    int* array = (int*)malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i < numsSize; i++)
    {
        array[i] = nums[i];
    }
    QuickSort1(array, 0, numsSize-1);
    return array;
}

结果展示: 

 发现当数据有序时,会超出时间限制....

2.挖坑法

代码展示:

//挖坑法
void QuickSort2(int* a, int left, int right) {
	if (left >= right)
		return;
	int key = a[left]; // 选择第一个元素作为基准值
	int low = left, high = right;
	while (low < high) {
		// 从右向左找到第一个小于基准值key的元素
		while (low < high && a[high] >= key)
			high--;
		if (low < high) {
			a[low] = a[high]; // 使用 a[high] 的值填充 a[low] 的坑
			low++;
		}

		// 从左向右找到第一个大于基准值key的元素
		while (low < high && a[low] <= key)
			low++;
		if (low < high) {
			a[high] = a[low]; // 使用 a[low] 的值填充 a[high] 的坑
			high--;
		}
	}
	a[low] = key; // 将基准值放入最终的坑中
	int pivot = low; // 基准值的最终位置
	QuickSort2(a, left, pivot - 1); // 对左子数组递归排序
	QuickSort2(a, pivot + 1, right); // 对右子数组递归排序
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
    (*returnSize) = numsSize;
    int* array = (int*)malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i < numsSize; i++)
    {
        array[i] = nums[i];
    }
    QuickSort2(array, 0, numsSize-1);
    return array;
}

结果展示:

 

3.前后指针法

代码展示:

// 前后指针_快速排序
void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = left;

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

		cur++;
	}

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

	QuickSort3(a, left, keyi - 1);
	QuickSort3(a, keyi + 1, right);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
    (*returnSize) = numsSize;
    int* array = (int*)malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i < numsSize; i++)
    {
        array[i] = nums[i];
    }
    QuickSort3(array, 0, numsSize-1);
    return array;
}

 

结果显然,三个方法都没有通过,快排作为排序界的杠把子,难道就这么拉吗?都跟冒泡和选择排序一个挡位了,所以这里我们需要进一步优化快速排序.

1.1三数取中

以hoare版本为例,key都是取左端点.在有序序列中,原本分区的时间复杂度为O(logN)就会转换成O(N),这就会导致快速排序遇到有序或逆序时,时间复杂度就会变成O(N^2)

示例:

当key为中间值时,满足O(logN)的时间复杂度

当key为最小或最大值时 ,时间复杂度为O(N):

这里还有可能存在栈溢出的风险

 所以快排里面有一个取中的方式,让key不会成为最大数或者时最小数,这里就介绍一下三数取中的方式:

这里的三数是指:left,right,midi((left+right)/2) ,我们需要在这三个数中找出中间值并赋值给key

代码展示:

int GetMidi(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	// left midi right
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else // a[left] > a[midi]
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

1.2小区间优化

快速排序类似于二叉树递归的过程,越处于底层的数据会被重复调用多次,所以可以当划分的数列小于10时,可.直接调用其他排序,比如插入排序,直接排好,能减少很大一部分数据的递归调用,

 

代码展示:

	// 小区间优化，不再递归分割排序，减少递归的次数
	if ((right - left + 1) < 10)
	{
		InsertSort(a + left, right - left + 1);
	}
    void InsertSort(int* a, int n)
{
	//  [0, n-1]
	for (int i = 0; i < n - 1; i++)
	{
		// [0, n-2]是最后一组
		// [0,end]有序 end+1位置的值插入[0,end]，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

优化后的快速排序

void InsertSort(int* a, int n)
{
	//  [0, n-1]
	for (int i = 0; i < n - 1; i++)
	{
		// [0, n-2]是最后一组
		// [0,end]有序 end+1位置的值插入[0,end]，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void Swap(int* n, int* m)
{
    int p = *n;
    *n = *m;
    *m = p;
}
//hoare版本
int GetMidi(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	// left midi right
	if (a[left] == a[midi] && a[left] == a[midi] && a[midi] == a[right])
		return midi;
	else if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else // a[left] > a[midi]
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

// 避免有序情况下，效率退化
//三数取中
//小区间优化
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 midi = GetMidi(a, left, right);
		Swap(&a[left], &a[midi]);

		int keyi = left;
		int begin = left, end = right;
		while (begin < end)
		{
			// 右边找小
			while (begin < end && a[end] >= a[keyi])
			{
				--end;
			}

			// 左边找大
			while (begin < end && a[begin] <= a[keyi])
			{
				++begin;
			}

			Swap(&a[begin], &a[end]);
		}

		Swap(&a[keyi], &a[begin]);
		keyi = begin;
		// [left, keyi-1] keyi [keyi+1, right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

InsertSort 函数

  • 实现了插入排序算法，将传入的数组 a 按升序排序。
  • 在外部循环中，逐步将数组分为已排序部分和未排序部分。
  • 内部循环通过比较当前元素和已排序部分的元素，找到合适位置插入当前元素，保证数组的有序性。

Swap 函数：

        辅助函数，用于交换两个整数指针所指向的值。

GetMidi 函数：

  • 用于选择三个元素中间值作为快速排序的枢轴（pivot）。
  • 考虑了数组左端、中间和右端三个位置的元素，确保选择合适的枢轴来避免最坏情况下的效率问题。

QuickSort 函数：

  • 实现了快速排序算法。
  • 在大于等于10个元素时，采用快速排序策略，选择枢轴、分割数组、递归排序子数组。
  • 小于10个元素时，采用插入排序优化，减少递归深度，提高效率。

 

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

上面说到过,由于快速排序是递归实现的,在遇到有序或者无序的序列会有栈溢出的风险,所以快速排序的非递归实现是有必要的.

思路: 

利用栈后进先出的特点,模拟快速排序的过程

代码展示:

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort2(a, begin, end);
		// [begin, keyi-1] keyi [keyi+1, end]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

分析:

数据结构和函数调用：

ST 是一个栈结构，具备以下操作：

  • STInit(&st)：初始化栈 st。
  • STPush(&st, val)：将 val 压入栈 st。
  • STTop(&st)：获取栈顶元素但不弹出。
  • STPop(&st)：弹出栈顶元素。

非递归快速排序实现：

  • 主要逻辑通过栈来维护排序区间的边界。
  • 初始时，将整个数组的左右边界分别压入栈中，表示整个数组需要排序。
  • 进入循环，不断从栈中取出左右边界，执行分区操作（PartSort2 函数），得到分区点 keyi。
  • 根据分区点 keyi，将数组分为 [begin, keyi-1]、keyi、[keyi+1, end] 三部分。
  • 如果左边界小于 keyi - 1，说明左侧还有未排序部分，将其左右边界压入栈中。
  • 如果右边界大于 keyi + 1，同理将其左右边界压入栈中。

循环结束条件：

当栈为空时，说明所有区间已经排序完成，循环结束。

PartSort2 函数：

它的作用是进行数组的分区操作，将数组按照某个基准值分成左右两部分，并返回基准值最终的位置。(可以是hoare,挖坑法,前后指针法)

完整代码:

栈

Stack.h

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);

Stack.c 

#include"Stack.h"

// 初始化和销毁
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	// top指向栈顶数据的下一个位置
	pst->top = 0;

	// top指向栈顶数据
	//pst->top = -1;

	pst->capacity = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

// 入栈  出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	// 扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

// 20:08继续
// 取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

// 获取数据个数
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}

Sort.c

int GetMidi(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	// left midi right
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else // a[left] > a[midi]
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

// hoare
int PartSort1(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		// 右边找小
		while (begin < end && a[end] >= a[keyi])
		{
			--end;
		}

		// 左边找大
		while (begin < end && a[begin] <= a[keyi])
		{
			++begin;
		}

		Swap(&a[begin], &a[end]);
	}

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

// 前后指针
int PartSort2(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;

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

		cur++;
	}

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

// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
//
//void QuickSort(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort1(a, left, right);
//
//	 [left, keyi-1] keyi [keyi+1, right]
//	QuickSort(a, left, keyi - 1);
//	QuickSort(a, keyi + 1, right);
//}

#include"Stack.h"

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort2(a, begin, end);
		// [begin, keyi-1] keyi [keyi+1, end]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

3.总结

非递归与递归快速排序的对比

  • 非递归版本避免了递归调用的额外开销，使用栈来存储分割点，节省了空间。
  • 在处理大规模数据时，递归深度可能导致栈溢出，而非递归版本则能够更好地应对这种情况。

 

 

阅读全部

相关推荐

  3. 排序算法之快速排序

    2024-07-22 16:00:07       59 阅读

  9. 八大排序算法之快速排序

    2024-07-22 16:00:07       38 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 16:00:07       52 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 16:00:07       54 阅读

  9. 在Django里面运行非项目文件

    2024-07-22 16:00:07       45 阅读

  19. Python语言-面向对象

    2024-07-22 16:00:07       55 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-22 16:00:07       50 阅读

热门阅读

  1. 【c++刷题笔记-动态规划】day47： 647. 回文子串、 516.最长回文子序列

    2024-07-22 16:00:07       16 阅读

  6. 微软Edge浏览器全解析

    2024-07-22 16:00:07       16 阅读

  10. 【黄啊码】上百个AI提示词模板，不用多想，直接收藏【一】

    2024-07-22 16:00:07       13 阅读

  12. 零样本学习：目标检测的未来

    2024-07-22 16:00:07       17 阅读

  15. 大流量DDoS攻击：未来的网络攻击趋势与防御策略

    2024-07-22 16:00:07       16 阅读

  19. DASCTF2024暑期挑战赛

    2024-07-22 16:00:07       18 阅读

  26. mysql日志

    2024-07-22 16:00:07       19 阅读

  28. 锁相环 vivado FPGA

    2024-07-22 16:00:07       14 阅读

  29. Mybatis——缓存简介

    2024-07-22 16:00:07       15 阅读

  30. html 特效 学习 日志 2024/7/21 23:58

    2024-07-22 16:00:07       14 阅读