排序算法—快速排序

文章目录

  • 快速排序
    • 一、递归实现
    • 二、非递归实现
    • 总结

快速排序

以下均以排升序为最终目的。

一、递归实现

有一个排序能解决所有问题吗？没有！不过，快速排序这种排序适用于大多数情况。

我们前面讨论排序算法一般都是先讨论一趟的情况，对于快速排序，也是可以这么讨论的，特别的是，快速排序的每一趟的代码实现有三种不同的思路：挖坑法、左右指针法、前后指针法。

不管采用哪种思路，其目的都是：将某个选定的key值排到正确位置，然后使得key位置左边的所有值都小于key值，这个位置右边的所有值都大于key值，不过，key位置的左右并不是有序的。key值元素已经排好序了，不需要再参与后续的排序，因而将原序列分割成两个子区间（以排升序为例）。通常key选择序列中的最左边或最右边的元素。

在这里插入图片描述

挖坑法

挖坑法选择一个值，放到变量key中，相当于备份了这个值，意味着这个值所在的位置可以被覆盖，称这样一个位置为 “坑”。假设key中存储的是序列最左边的元素，坑在左边，目的是实现升序排列。我们需要从最右边的元素开始遍历，寻找到比key值小的一个元素，用这个元素填坑，填坑后，填坑元素被备份，那么填坑元素的原位置成为新的坑。由于我们开始是从右开始遍历的，所以坑位更新后在右边，所以我们需要从左边开始遍历，寻找比key值大的元素，填坑，更新坑位，以此类推，当从左右遍历的指针相遇时，将它们指向的位置放上key值，此时一趟挖坑法结束。（推荐的思路）
在这里插入图片描述

左右指针法

左右指针法与挖坑法类似，选定一个key值，定义两个变量，起始指向序列最左边和最右边，两个指针开始向中间遍历，当左边的指针找到一个大于key的值，右边的指针找到一个小于key的值，则交换这两个位置的值，依次类推，最后将key值放到指定位置。（此方法不推荐，需要注意的细节太多了，很容易写错，掌握思路就好）

前后指针法

前后指针法较为抽象，选定最左边的元素为key，定义两个变量，假设cur、prev，prev初始指向key的的位置，cur初始指向key值后面一个元素，cur负责向右找比key小的值，如果找到了，prev++，然后交换prev和cur指向的两个位置的值，一直重复此过程，当cur要越界的时候停止，将prev指向的位置的值与key位置的值交换。(首推挖坑法，其次就是前后指针法）

以下是三种思路（每趟）的代码实现：

//挖坑法
int PartSort1(int* a, int left, int right)
{
    int begin = left;//从左遍历的下标
    int end = right;//从右遍历的下标
    int pivot = begin;//坑位下标
    int key = a[begin];//备份key值，初始坑位（这里选的是序列最左边元素）
    while (begin < end)
    {
        while (begin < end && a[end] >= key)
        {
            --end;
        }
        a[pivot] = a[end];
        pivot = end;
        while (begin < end && a[begin] <= key)//注意&&左边的语句，如果没有的话，可能会出现将一趟排序结果打乱的情况
        {
            ++begin;
        }
        a[pivot] = a[begin];
        pivot = begin;
    }
    a[pivot] = key;
    return pivot;
}



//左右指针法
int PartSort2(int* a, int left, int right)
{
    int begin = left;//左指针
    int end = right;//右指针
    int key = begin;
    while (begin < end)
    {
        while (begin < end && a[end] >= a[key])
        {
            --end;
        }
        while (begin < end && a[begin] <= a[key])
        {
            ++begin;
        }
        Swap(&a[begin], &a[end]);//交换函数
    }
    Swap(&a[begin], &a[key]);
    return begin;
}



//前后指针法
int PartSort3(int* a, int left, int right)
{
    int cur = left + 1;
    int prev = left;
    int key = left;
    while (cur <= right)
    {
        if (a[cur] < a[key] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
    }
    Swap(&a[prev], &a[key]);
    return prev;
}

当结束一趟排好一个元素后，这个位置将序列分为了两个子区间，我们只要将这两个子区间排好序，那么就排序完毕。

对于每个子区间，采用相同的方式（挖坑法、前后指针法、左右指针法）排序，再将此子区间分割成两个新的子区间，基于这一特点，我们可以采用分治递归的方式解决。

以下每趟排序采用的是挖坑法。

void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
    int begin = left;
    int end = right;
    int key = a[begin];
    int pivot = begin;
    while (begin < end)
    {
        while (begin < end && a[end] >= key)
        {
            --end;
        }
        a[pivot] = a[end];
        pivot = end;
        while (begin < end && a[begin] <= key)
        {
            ++begin;
        }
        a[pivot] = a[begin];
        pivot = begin;
    }
    a[pivot] = key;
    QuickSort(a, left, pivot - 1);
    QuickSort(a, pivot + 1, right);
}

快速排序什么情况下最坏？时间复杂度是多少？

有序的情况下最差，这种情况下，每趟挖坑认为只能排好一个元素。

最坏的时间复杂度为O(N^2)

假如我们每次挖坑选择第一个元素为key，那么有序情况下，一趟挖坑分割的左子区间为空，所以只对右子区间执行挖坑法，每趟挖坑分割后的左子区间都是空，如果是排升序，那么从右找比key小的数要一直从右遍历到左边（因为原序列已经有序）。

针对这样的情况，采用三数取中
三数取中就是拿出序列中位置最左、最右和中间的三个元素，比较它们的大小，选出大小排序后为中间的元素。

这个元素将在后面被选定为key。

三数取中优化后的快速排序：

//三树取中
int GetmidIndex(int* a, int left, int right)
{
    int mid = (left + right) >> 1;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return right;
        }
        else
            return left;
    }
    else//a[mid] > a[left]
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
            return right;
    }
}
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int index = GetmidIndex(a, left, right);/拿到中间大的元素的下标
    Swap(&a[left], &a[index]);//为了不影响后续最左边元素为key的逻辑，我们将三数取中得到的下标位置的值和序列最左边的值交换
    int begin = left;
    int end = right;
    int pivot = begin;
    int key = a[begin];
    while (begin < end)
    {
        while (begin < end && a[end] >= key)
        {
            --end;
        }
        a[pivot] = a[end];
        pivot = end;
        while (begin < end && a[begin] <= key)
        {
            ++begin;
        }
        a[pivot] = a[begin];
        pivot = begin;
    }
    a[pivot] = key;
    QuickSort(a, left, pivot - 1);
    QuickSort(a, pivot + 1, right);
}

我们还能继续优化吗？

对于数据总量庞大的情况，从头到尾递归快速排序，需要大量的递归调用，栈区空间占用较多。

不考虑其他情况，第一次挖坑为第一层；之后会出现两个子区间，这是第二层；接着4个子区间，第三层……我们发现越到后面，子区间越多，递归调用越多。

假如现在有100w（约等于2 ^ 20个数据，说明有20层，从后往前数2 ^ 19（50w）、2 ^ 18（25w）……我们发现大多数的函数调用都发生在后面的几层，而后面的几层处理的每个子区间的元素个数相对数据总量很少。

基于此，我们采用小区间优化消除后面几层的递归调用。

对小区间采用其他的排序方式，而不是继续递归调用，一般采用直接插入排序。

不过，小区间优化的效果并不明显，且要注意的是，到什么程度不递归，需要结合数据总量考虑，下面代码给的10。

三数取中、小区间优化后的快速排序：

int GetmidIndex(int* a, int left, int right)
{
    int mid = (left + right) >> 1;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return right;
        }
        else
            return left;
    }
    else//a[mid] > a[left]
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
            return right;
    }
}
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int index = GetmidIndex(a, left, right);
    Swap(&a[left], &a[index]);
    int begin = left;
    int end = right;
    int pivot = begin;
    int key = a[begin];
    while (begin < end)
    {
        while (begin < end && a[end] >= key)
        {
            --end;
        }
        a[pivot] = a[end];
        pivot = end;
        while (begin < end && a[begin] <= key)
        {
            ++begin;
        }
        a[pivot] = a[begin];
        pivot = begin;
    }
    a[pivot] = key;
    
    if (pivot - 1 - left < 10)//判断区间是否为小区间
    {
        InsertSort(a + left, pivot - 1 - left + 1);//插入排序
    }
    else
        QuickSort(a, left, pivot - 1);//递归
    if (right - pivot - 1 < 10)
    {
        InsertSort(a + pivot + 1, right - pivot - 1 + 1);
    }
    else
        QuickSort(a, pivot + 1, right);
}

二、非递归实现

递归的缺陷： 栈帧深度太深，栈空间不够用，可能会溢出

递归改非递归：

  • 直接改循环
  • 借助数据结构栈模拟递归过程

非递归实现快速排序需要用到栈。

想清楚，递归建立栈帧，栈帧存储局部变量，我们函数调用时存储的是区间，也就是 left 和 right，我们考虑用栈来模拟递归，存储left和right的值。

思路

每次将区间的左右下标入栈，每趟排序从栈顶拿取，这一过程要考虑栈的先入后出属性。

由于C语言限制，其库函数没有现成的栈，我们需要独立去实现一个栈。

独立实现的栈：

//Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

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

void StackInit(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
void StackDestory(ST* ps);
STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

//Stack.c
#include "Stack.h"

void StackInit(ST* ps)
{
    assert(ps);
    STDataType* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
    if(NULL == tmp)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    else
    {
        ps->a tmp;
        ps->capacity = 4;
        ps->top = 0;
    }
}


void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if(ps->capacity == ps->top)
    {
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
        if(NULL == tmp)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        else
        {
            ps->a = tmp;
            ps->capacity *= 2;
            ps->a[ps->top] = x;
            ps->top++;
        }
    }
}


void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}


void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}


STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top-1];
}


bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}


int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

基于上面栈的实现，我们实现一下非递归快速排序。

void QuickSortNonr(int* a, int len)
{
    ST st;
    StackInit(&st);
    StackPush(&st, len - 1);//第一趟排序区间入栈
    StackPush(&st, 0);
    while (!StackEmpty(&st))//栈为空则排序证明所有子区间排序完毕
    {
        int left = StackTop(&st);
        StackPop(&st);
        int right = StackTop(&st);
        StackPop(&st);
        
        int index = GetmidIndex(a, left, right);
        Swap(&a[left], &a[index]);
        
        int end = right;
        int begin = left;
        int pivot = begin;
        int key = a[begin];
        
        while (begin < end)
        {
            while (begin < end && a[end] >= key)
            {
                --end;
            }
            a[pivot] = a[end];
            pivot = end;
            while (begin < end && a[begin] <= key)
            {
                ++begin;
            }
            a[pivot] = a[begin];
            pivot = begin;
        }
        a[pivot] = key;
        
        if (right > pivot + 1)//子区间不存在或只有一个元素不入栈
        {
            StackPush(&st, right);
            StackPush(&st, pivot + 1);
        }
        
        if (left < pivot - 1)
        {
            StackPush(&st, pivot - 1);
            StackPush(&st, left);
        }
    }
    StackDestory(&st);
}

总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。

2. 时间复杂度：O(N*logN)
最坏情况下：O(N^2)
在这里插入图片描述

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/529196.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

服务器开发 Socket 相关函数

服务器开发 Socket 相关函数

Socket 函数 #include <sys/types.h> #include <sys/socket.h> int socket(int domain, int type, int protocol)domain: AF_INET 这是大多数用来产生 socket 的协议&#xff0c;使用TCP或UDP来传输&#xff0c;用IPv4的地址 AF_INET6 与上面类似&#xff0c;不过…
阅读更多...
Lua热更新（AssetBundle)

Lua热更新（AssetBundle)

AssetBundle 新版本导入ab包报错，则删除其中的Tests文件夹。 给资源分组 打包设置：平台、路径、重复打包清空文件夹、复制到streaming文件夹 建议勾选 建议使用LZ4压缩方式 用来观察文件中的包大小，不常用 参数总结： 这六个只做了解，重要的是上面的
阅读更多...
Cali Linux上的PoshC2安装和使用

Cali Linux上的PoshC2安装和使用

一、安装PoshC2 curl -sSL https://raw.githubusercontent.com/nettitude/PoshC2/master/Install-for-Docker.sh | sudo bash二、创建工程 posh-project -n test三、修改配置文件 posh-config将图中的baidu.com改为自己要攻击的域名或者IP地址 四、执行 posh-server 显示没…
阅读更多...
不牺牲算法，不挑剔芯片，这个来自中科院的团队正在加速国产AI芯片破局

不牺牲算法，不挑剔芯片，这个来自中科院的团队正在加速国产AI芯片破局

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 新建了免费的人工智能中文站https://ai.weoknow.com 新建了收费的人工智能中文站https://ai.hzytsoft.cn/ 更多资源欢迎关注 不降低大模型算法精度&#xff0c;还能把芯片的算力利用效率提升 2~10 倍&#xff0c;这就是…
阅读更多...
基于ssm餐厅点菜管理系统论文

基于ssm餐厅点菜管理系统论文

摘 要 网络技术和计算机技术发展至今&#xff0c;已经拥有了深厚的理论基础&#xff0c;并在现实中进行了充分运用&#xff0c;尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代&#xff0c;所以对于信息的宣传和管理就很关键。因此餐厅点菜信息的…
阅读更多...
KNN分类算法的MATLAB实现以及可视化

KNN分类算法的MATLAB实现以及可视化

一、KNN简介 KNN算法&#xff0c;即K-Nearest Neighbors&#xff0c;是一种常用的监督学习算法&#xff0c;可以用于分类问题&#xff0c;并且在实际应用中取得了广泛的成功。 二、KNN算法的基本原理 对于给定的测试样本&#xff0c;KNN算法首先计算它与训练集中所有样本的距…
阅读更多...
MySQL-用户与权限管理：用户管理、权限管理、角色管理

MySQL-用户与权限管理：用户管理、权限管理、角色管理

用户与权限管理 用户与权限管理1.用户管理1.1 登录MySQL服务器1.2 创建用户1.3 修改用户1.4 删除用户1.5 设置当前用户密码1.6 修改其它用户密码 2. 权限管理2.1 权限列表2.2 授予权限的原则2.3 授予权限2.4 查看权限2.5 收回权限 访问控制连接核实阶段请求核实阶段 3. 角色管理…
阅读更多...
拯救鲨鱼！Helping wireshark！wireshark未响应解决方法

拯救鲨鱼！Helping wireshark！wireshark未响应解决方法

前言 做题的的时候 在用wireshark解密tls秘钥的时候 我的小鲨鱼突然未响应了 然后我多次尝试无果 并且殃及池鱼 我电脑上所有的流量包都打不开了&#xff1f;&#xff01;&#xff01;&#xff01; 于是乎 尝试删了重下 还是未响应 开始怀疑电脑 重启电脑两次 还是打…
阅读更多...
Ngnix常用配置及和基本功能讲解

Ngnix常用配置及和基本功能讲解

Nginx已经广泛应用于J-one和Jdos的环境部署上&#xff0c;本文对Nginx的常用的配置和基本功能进行讲解&#xff0c;适合Nginx入门学习。 1 核心配置 找到Nginx安装目录下的conf目录下nginx.conf文件&#xff0c;Nginx的基本功能配置是由它提供的。 1.1 配置文件结构 Nginx的…
阅读更多...
Xinstall：专业的App下载量统计工具，让推广效果可衡量

Xinstall：专业的App下载量统计工具，让推广效果可衡量

在移动互联网时代&#xff0c;App的下载量是衡量一个应用受欢迎程度的重要指标。然而&#xff0c;很多开发者和广告主在推广App时&#xff0c;都面临着一个共同的问题&#xff1a;如何准确统计App的下载量&#xff1f;这不仅关系到推广效果的评估&#xff0c;还直接影响到广告R…
阅读更多...
lombok详解

lombok详解

一&#xff1a;概述 lombok是一种java使用的开发工具&#xff0c;可以帮助我们快速开发java中pojo实体类&#xff0c;通过注解消除java的冗余的java代码。 官网&#xff1a;projectlombok.org 原理&#xff1a;通过JDK6提供的新特性&#xff0c;在javac编译期间处理注解&…
阅读更多...
Django admin日志记录模块的使用，拓展LogEntry日志记录跳转改动详情页，日志搜索等功能

Django admin日志记录模块的使用，拓展LogEntry日志记录跳转改动详情页，日志搜索等功能

1、django admin日志记录引入 在使用django admin开发后台管理系统时&#xff0c;可以在admin模块中将django admin自带的操作日志记录模块注册到管理面板 from django.contrib.admin.models import LogEntry 可以看到引入后django admin的菜单栏新增出了一条日志记录的按钮 …
阅读更多...
QT windeployqt打包出现无法正常启动问题

QT windeployqt打包出现无法正常启动问题

QT 通过windeployqt 打包后出现的问题 原因QT构建选择的是64位的 但是windows下运行的却是32位的 步骤打开32的所在路径 一般在上一级目录会有安装好的64位的MSVC工具 运行打包即可
阅读更多...
秋招复习笔记——八股文部分：操作系统

秋招复习笔记——八股文部分：操作系统

笔试得刷算法题&#xff0c;那面试就离不开八股文&#xff0c;所以特地对着小林coding的图解八股文系列记一下笔记。 这一篇笔记是图解系统的内容。 硬件结构 CPU执行程序 计算机基本结构为 5 个部分&#xff0c;分别是运算器、控制器、存储器、输入设备、输出设备&#xf…
阅读更多...
梵宁教育课程深度解析：设计技能提升，从这里开始

梵宁教育课程深度解析：设计技能提升，从这里开始

在当今数字化快速发展的时代&#xff0c;设计技能已成为个人职业发展的重要一环。无论是从事广告、媒体、UI设计还是其他相关领域&#xff0c;拥有扎实的设计技能都意味着拥有了更多的职业机会和发展空间。梵宁教育&#xff0c;作为业界知名的教育机构&#xff0c;以其专业的课…
阅读更多...
4.9作业

4.9作业

1、完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和密码不匹配&…
阅读更多...
推进数智化财务管理体系，助力企业降本提效

推进数智化财务管理体系，助力企业降本提效

在数字经济快速发展的今天&#xff0c;数字化能力早已成为企业发展的核心竞争力。在开放、融合的数字经济大背景下&#xff0c;企业该如何将科技深度赋能业务&#xff0c;打造出高质量发展的新引擎&#xff1f;当财务管理缺乏精准化、精确化、及时性的问题逐渐显露&#xff0c;…
阅读更多...
关于51单片机TMOD定时器的安全配置

关于51单片机TMOD定时器的安全配置

定时器介绍&#xff1a; -------------------------------------------------------------------------------------------------------------------------- 首先配置的是控制寄存器 TCON 说直白点&#xff0c;这个寄存器就是用来计数的&#xff0c;打开计时器&#xff0c;关…
阅读更多...
基于51单片机轮胎胎压监测系统—数码管显示

基于51单片机轮胎胎压监测系统—数码管显示

基于51单片机轮胎胎压监测系统 &#xff08;仿真&#xff0b;程序&#xff0b;设计报告&#xff09; 功能介绍 具体功能&#xff1a; 1.MPX4115压力传感器胎压检测&#xff1b; 2.ADC0832进行模数转换后&#xff0c;51单片机处理控制&#xff1b; 3.数码管显示胎压&#xff…
阅读更多...
ST Motor Control Workbench生成工程报错PDSC version is not supported解决办法

ST Motor Control Workbench生成工程报错PDSC version is not supported解决办法

文章目录 前言一、报错相关信息二、解决办法 前言 使用 ST Motor Control Workbench 5.4.4 FOC 电机开发工具和 stm32cubemx 6.1.1 生成的工程报错&#xff0c;记录一下解决的办法。 一、报错相关信息 报错信息如下&#xff1a; 2024-04-09 18:35:28,527 ERROR [LineInfo_to…
阅读更多...
最新文章

Copyright @ 2022~2023