自学内容网 自学内容网
自学内容网 > 正文

数据结构——快速排序

🕗 发布于 2024-11-15 21:38 数据结构  算法  排序算法  

目录

一、排序思想

二、代码实现

（一）hoare版

1、原版——固定选key

2、随机选key、三数取中选key

（二）挖坑法

（三）前后指针法

（四）小区间优化

（五）非递归写法

一、排序思想

任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右两子序列重复该过程，直到所有元素都排列在相应位置上为止。

二、代码实现

下列所有代码示例均是排成升序。

注：

快排在对存在大量相同的数据排序时，效率很低，这种情况三路划分可以解决，感兴趣的朋友可以自行了解，这里不作介绍。

（一）hoare版

1、原版——固定选key

缺点：

固定位置选key，在数据有序或几乎有序时容易栈溢出。

注：

选最左边元素为key，最右边先开始选数


选最右边元素为key，最左边先开始选数

#include<stdio.h>

void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//haore
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
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;
//begin keyi-1  keyi  key+1 end
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);

}

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

QuickSort1(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, 10);

return 0;
}

2、随机选key、三数取中选key

思想较之于原版并没有本质变化，只是优化了选key的方式。

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

//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//三数取中
int Midnum(int* a,int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}

}

//快排(升序)——hoare(优化选key)
void QuickSort(int* a,int left,int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
//随机选key
/*int ran = left + rand() % (right - left);
Swap(&a[left], &a[ran]);
int keyi = left;*/

//三数取中选key
int mid = Midnum(a,left, right);
Swap(&a[left], &a[mid]);
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]);
}
//将key移至中间
Swap(&a[left], &a[keyi]);
//更新keyi
keyi = left;
//递归 [begin,keyi-1] keyi [keyi+1,end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}

int main()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0])-1);
Print(arr, 10);

return 0;
}

（二）挖坑法

思想：

将选定的key存起来，原本key的位置就空出来成为一个坑位，然后将找到的符合要求的元素填入坑内，该元素原本所在的位置成为新的坑位，循环往复。

其实就是一个不断填坑造坑的过程。

#include<stdio.h>

//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}


//快排(升序)——挖坑法
void QuickSort3(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left, end = right;
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
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;
//[begin,hole-1] hole [hole+1,end]
QuickSort3(a, begin, hole - 1);
QuickSort3(a, hole+1, end);
}

int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
QuickSort3(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));

return 0;
}

（三）前后指针法

思想：

1、cur找到比key小的值，++prev，cur和prev位置的值交换，++cur
2、cur找到比key大的值，++cur

循环往复

其实就是将比key大的值向右扔，将比key小的值向左扔。

注：

1、prev要么紧跟着cur
2、prev要么跟cur中间间隔着比key大的一段值区间

#include<stdio.h>

//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}

//快排——前后指针法
void QuickSort4(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && cur != ++prev)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//a[prev]永远都比a[keyi]小
Swap(&a[prev], &a[keyi]);
//更新keyi
keyi = prev;
//[left,keyi-1] keyi [keyi+1,right]
QuickSort4(a, left, keyi - 1);
QuickSort4(a, keyi+1, right);
}

int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,13,14};
QuickSort4(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));

return 0;
}

（四）小区间优化

①主要针对递归层数太多的情况。

②小区间优化需要用到直接插入排序，不了解的朋友可以先移步直接插入排序

#include<stdio.h>
#include"InsertSort.h"

//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}

//快排——前后指针法
int _QuickSort5(int* a, int left, int right)
{
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && cur != ++prev)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//a[prev]永远都比a[keyi]小
Swap(&a[prev], &a[keyi]);
//更新keyi
keyi = prev;
return keyi;
}

void QuickSort5(int* a, int left, int right)
{
if (left >= right)
{
return;
}

if (right - left + 1 > 10)
{
int keyi = _QuickSort5(a, left, right);
//[left,keyi-1] keyi [keyi+1,right]
QuickSort5(a, left, keyi - 1);
QuickSort5(a, keyi + 1, right);
}
//小区间优化
else
{
IsertSort(a+left, right - left + 1);
}
}

int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,2,4,45,33 };
QuickSort5(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));

return 0;
}

（五）非递归写法

此处是用栈来辅助改成循环，需要用到栈。

思想：

①将初始区间入栈

②从栈中取一段区间进行单趟快排并分割

③将分割出的子区间入栈（区间内元素数量>=2）

#include<stdio.h>
#include"Stack.h"

//打印
void Print(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
int mid = (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]<a[mid]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
}

//快排——前后指针法
int _QuickSort6(int* a, int left, int right)
{
int mid = GetMidnum(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && cur != ++prev)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//a[prev]永远都比a[keyi]小
Swap(&a[prev], &a[keyi]);
//更新keyi
keyi = prev;
return keyi;
}

//快排——非递归形式
void QuickSort6(int* a, int left, int right)
{
ST st;
StackInit(&st);
//将初始区间入栈
StackPush(&st, right);
StackPush(&st, left);
while (!Empty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//分割母区间
int keyi = _QuickSort6(a, begin, end);

//[begin,keyi-1]  keyi  [keyi+1,end]
//将子区间入栈(元素>=2)
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi+1);
}
if (begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}

StackDestroy(&st);
}

int main()
{
int arr[] = { 9,7,8,5,4,6,3,1,2,0 };
QuickSort6(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
Print(arr, sizeof(arr) / sizeof(arr[0]));

return 0;
}

感谢阅读，本文如有疏漏不当之处，烦请各位指正。


原文地址：https://blog.csdn.net/2301_81298637/article/details/143652805

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

  • VBA学习笔记：基础知识

    若提示宏被禁止，解决办法之一：工具-宏-安全性-安全级-中，关闭excel重新打开，启用宏。Dim arr(1 to 10) As Integer 数组。Dim x As Integer 整数。Dim

    阅读更多2024-11-16
  • swoole mysql连接池使用

    并不支持连结池的功能。连结池通常是数据库连接池的一种，它能够管理多个数据库连接，避免了频繁创建和关闭连接的开销，提高了系统的性能。释放连接，以便其他协程可以使用。这样就实现了连接的复用，提高了系统的性

    阅读更多2024-11-16
  • Jmeter中的监听器（三）

    假设我们需要测试一个Web应用，并使用比较断言来验证两个请求的响应数据是否一致，然后使用“比较断言可视化器”来查看比较结果。假设我们需要测试一个Web应用，并使用断言来验证响应数据的正确性，然后使用“

    阅读更多2024-11-16
  • Area-Composition模型部署指南

    Area-Composition模型可以通过输入不同的提示词，然后根据各部分提示词进行融合生成图片。本文详细介绍了如何实现该模型的本地部署。

    阅读更多2024-11-16
  • 3.task1 suimove helloword 上链

    水龙头”通常指的是一种分发加密货币或代币的机制，尤其是通过小额赠送或奖励的方式来吸引用户参与。网络问题 ，切换为国内源。move.toml中修改。

    阅读更多2024-11-16
  • Unity类银河战士恶魔城学习总结（P126 Item ToolTip物品提示）

    本章节实现了把鼠标放到物品上面就会显示物品属性

    阅读更多2024-11-16
  • 游戏如何应对内存修改

    由于进行内存修改需要提供root权限，GG修改器常运行虚拟机、虚拟框架等环境，在获取root权限后，可以使用magisk实现对游戏隐藏进程，来躲避游戏检测，让传统的检测手段失效，对抗难度大幅度提升。内

    阅读更多2024-11-16
  • C#从入门到放弃

    C#是一个编程语言。

    阅读更多2024-11-16
  • NCC前端调用查询弹框

    选择左侧 查询区 拖拽指右侧，并添加对应的查询模板字段，注意右上角 区域编码要维护card_query。2. 动态建模平台- 开发配置- 应用管理 - 应用注册 下找到对应的单据模板。6. 卡片下调用

    阅读更多2024-11-16
  • UI库架构设计

    工程架构：monorepo，core + components + hooks +utils …测试，单元测试，vitest，jest+react-testing-library。构建打包：rollu

    阅读更多2024-11-16
自学内容网
Copyright © 2015-2024