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

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.总结

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

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

原文地址：https://blog.csdn.net/wer24_25/article/details/140518371

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

上一篇：【面试题】数据结构：堆排序的排序思想？
下一篇：逆向案例二十四——webpack所需模块函数较少，某多多登录密码逆向

MYSQL常用基本操作总结
SQL查询中各个关键字的执行先后顺序： from > on> join > where > group by > with > having >select
阅读更多2024-09-19
JAVA并发编程系列之Semaphore信号量剖析
候选人，心中万马奔腾！！！吐了一口82年老血，当场砸电脑回家！原因是：腾讯T2面试，现场限时3分钟+限最多20行代码，模拟地铁口安检进站。其中安检入口10个，当前排队人数是100个，每个人安检进站耗时
阅读更多2024-09-19
24年蓝桥杯及攻防世界赛题-MISC-2
24年蓝桥杯及攻防世界赛题-MISC-2
阅读更多2024-09-19
干货-并发编程提高——重谈 RUNNABLE-上篇（十四）
直接看它的 Javadoc 中的说明：一个在 JVM 中执行的线程处于这一状态中。（A threadexecuting而传统的进（线）程状态一般划分如下：注：这里的进程指早期的单线程进程，这里所谓进程
阅读更多2024-09-19
phpstudy 建站使用 php8版本打开 phpMyAdmin后台出现网页提示致命错误：（phpMyAdmin这是版本问题导致的）
将网站根目录phpMyAdmin4.8.5里面的文件换成官网下载的5.2.1版本即可。重启网站，打开phpMyAdmin后台即可（若打不开更改 mysql密码即可）解决方法：官网下载phpmyadm
阅读更多2024-09-19
零工市场小程序：保障灵活就业
截止2024年高校毕业生达到1179万，在今年的经济情况下，就业市场就面临着比较大的压力，许多毕业生面临一时之间难以找到合适的工作的问题，那么求职者就会需要一份临时的工作来得到报酬，面对传统的找零工方
阅读更多2024-09-19
Linux中权限和指令
mv指令是move的缩写，用来，经常用来备份文件或目录。
阅读更多2024-09-19
Redis 底层揭秘：事务与 Lua 脚本的工作原理
定义Lua 是一种轻量级的脚本语言，它可以在 Redis 中被执行，用于实现复杂的逻辑操作。优势与事务相比，Lua 脚本具有更高的性能和更好的灵活性。Lua 脚本可以在 Redis 服务器端一次性执行
阅读更多2024-09-19
Vue3使用shapefile读取矢量数据，以数组形式返回坐标点
【代码】Vue3使用shapefile读取矢量数据，以数组形式返回坐标点。
阅读更多2024-09-19
WEB 编程：使用富文本编辑器 Quill 配合 WebBroker 后端
评估了好几个，最后选择这个开源的。把前端代码，存储为一个单独的文本文件，方便随便哪个页面需要的时候可以使用。相当于封装为一个独立的对象，方便代码重用。
阅读更多2024-09-19

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

前置说明

1.快速排序的优化

测试代码

1.hoare版本

2.挖坑法

3.前后指针法

1.1三数取中

1.2小区间优化

优化后的快速排序

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

完整代码:

3.总结

相关文章