当前位置: 首页 > article >正文

[数据结构]排序之 快速排序详解(递归版非递归版)

目录

一、递归版本

1. hoare版本

(一)低配版

(二)高配版

①随机选key

②三数取中法选key(在begin,end,mid三个数中选)

2. 挖坑法

3. 前后指针版本(推荐,细节容易把控)

二、非递归版本


快速排序是Hoare 1962 年提出的一种二叉树结构的交换排序方法,其基本思想为: 任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右 子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止
区间按照基准值划分为左右两半部分的常见方式有:

一、递归版本

1. hoare版本

(一)低配版

什么是key?
key就是选出汗一个关键值key,把它放到正确的位置(最终排好序要去的位置)
第一轮排完之后,比6小的放左边,比6大的放右边    
第一轮排序过程:
右边的R在找比key小的数 左边的L在找比key大的数 ,找到了以后,交换这两个数(把小的往左边换,大的往右边换)
交换完之后R继续往左边走找比key小的数,L继续往右边走找比key大的数,找到之后交换这两个数,R再继续……直到L==R,相遇之后把key对应的数与L或R对应的数交换
注意一点:左边做key要让右边先走,反之亦然。
第一轮结束以后整个区间被分为三段,key的左边、key、key的右边

结束后key左边的值都比key小,右边的都比key大

代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
       int temp = *a;
       *a = *b;
       *b = temp;
}
void QuickSort(int* a, int left,int right)
{
       //递归结束条件
       //当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
       //分为[0,0] keyi [2,1],此时会出现left>right的情况
       if (left >= right)
              return;
       int begin = left;
       int end = right;
       int keyi = left;
       while (left < right)
       {
              //右边先走 找小
              while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
              {
                      --right;
              }
              //左边找大
              while (left < right&&a[left] <= a[keyi])
              {
                      ++left;
              }
              Swap(&a[left], &a[right]);
       }
       Swap(&a[keyi], &a[left]);
       keyi = left;
       //[begin,kei-1] key [key+1,end]
       //递归
       QuickSort(a, begin, keyi - 1);
       QuickSort(a, keyi+1, end);
}
int main()
{
       int a[] = { 6,1,2,7,9,3,4,5,10,8 };
       QuickSort(a, 0, 9);
       for (int i = 0; i < 10; i++)
       {
              printf("%d ", a[i]);
       }
}
快速排序的特性总结:
1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫 快速 排序
2. 时间复杂度: O(N*logN)
3. 空间复杂度: O(logN)
4. 稳定性:不稳定
影响快排性能的是key的位置,key的位置越接近中间就越能进行二分就越接近满二叉树
所以越有序反而快排效率越低
如何改进?

(二)高配版

①随机选key
int randi = left + (rand() % ( right - left));
Swap(& a[ left], & a[randi]);
int keyi = left;
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
void Swap(int* a, int* b)
{
       int temp = *a;
       *a = *b;
       *b = temp;
}
void QuickSort(int* a, int left,int right)
{
       //递归结束条件
       //当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
       //分为[0,0] keyi [2,1],此时会出现left>right的情况
       if (left >= right)
              return;
       int begin = left;
       int end = right;
       int randi = left + (rand() % (right - left));
       Swap(&a[left], &a[randi]);
       int keyi = left;
       while (left < right)
       {
              //右边先走 找小
              while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
              {
                      --right;
              }
              //左边找大
              while (left < right&&a[left] <= a[keyi])
              {
                      ++left;
              }
              Swap(&a[left], &a[right]);
       }
       Swap(&a[keyi], &a[left]);
       keyi = left;
       //[begin,kei-1] key [key+1,end]
       //递归
       QuickSort(a, begin, keyi - 1);
       QuickSort(a, keyi+1, end);
}
int main()
{
       int a[] = { 6,1,2,7,9,3,4,5,10,8 };
       QuickSort(a, 0, 9);
       for (int i = 0; i < 10; i++)
       {
              printf("%d ", a[i]);
       }
}
三数取中法选key(在begin,end,mid三个数中选)
在有序或者接近有序的情况下选中间值效果最好
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
       int temp = *a;
       *a = *b;
       *b = temp;
}
int GetMidNumi(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])//此时mid最大
              {
                      return left;
              }
              else
              {
                      return right;
              }
       }
       else//a[left] > a[mid]
       {
              if (a[mid] > a[right])
              {
                      return mid;
              }
              else if (a[left] > a[right])//此时mid最小,此时另外两个小的那个就是中间值
              {
                      return a[right];
              }
              else
              {
                      return a[left];
              }
       }
}
void QuickSort(int* a, int left,int right)
{
       //递归结束条件
       //当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
       //分为[0,0] keyi [2,1],此时会出现left>right的情况
       if (left >= right)
              return;
       int begin = left;
       int end = right;
       //三数选中
       int mini = GetMidNumi(a, left, right);
       Swap(&a[left], &a[mini]);
       int keyi = left;
       while (left < right)
       {
              //右边先走 找小
              while (left<right&&a[right] >= a[keyi])//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
              {
                      --right;
              }
              //左边找大
              while (left < right&&a[left] <= a[keyi])
              {
                      ++left;
              }
              Swap(&a[left], &a[right]);
       }
       Swap(&a[keyi], &a[left]);
       keyi = left;
       //[begin,kei-1] key [key+1,end]
       //递归
       QuickSort(a, begin, keyi - 1);
       QuickSort(a, keyi+1, end);
}
int main()
{
       int a[] = { 6,1,2,7,9,3,4,5,10,8 };
       QuickSort(a, 0, 9);
       for (int i = 0; i < 10; i++)
       {
              printf("%d ", a[i]);
       }
}
为什么相遇的位置一定key小?
左边做key右边先走就能保证相遇位置一定比key小
相遇:
1、R找小,L找大没有找到,L遇到R,此时相遇位置比key小
2、R找小没有找到,直接跟L相遇,此时相遇位置比key小
类似道理,右边做key左边先走,相遇位置比key要大

2. 挖坑法

思路:
1、先将第一个数据存储在key中让第一个数据对应位置为空形成一个坑位
2、右边先走找比key小的位置后把那个比key小的数放到坑位里面去,此时右边形成了新的坑位
3、左边再走找比key大的数,找到后把这个数放到新的坑位里面去,此时又形成了新的坑位
4、以此类推,直到L和R相遇,一定相遇在坑里面,因为他们两一定有一个是坑,此时将key填到坑里面去排完后跟 hoare排完第一轮一般是不一样的
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void QuickSort(int* a, int left, int right)
{
    //递归结束条件
    //当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
    //分为[0,0] keyi [2,1],此时会出现left>right的情况
    if (left >= right)
        return;
    int begin = left;
    int end = right;
    //首先保存好值
    int key = a[left];
    //定义一个坑的位置
    int hole = left;
    while (left < right)
    {
        //右边先走 找小
        while (left < right && a[right] >= key)//left<right,防止right在左边没有找到一个比key小的,这样的话right会飘出数组导致越界
        {
            --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]
    //递归
    QuickSort(a, begin, hole - 1);
    QuickSort(a, hole + 1, end);
}
int main()
{
    int a[] = { 6,1,2,7,9,3,4,5,10,8 };
    QuickSort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
}

3. 前后指针版本(推荐,细节容易把控)

1、cur找到比key小的值,++prev,cur和prev位置交换,++cur
2、cur找到比key大的值,++cur ( cur一直在找小 )
说明:
1、prev要么紧跟着cur(prev下一个就是cur)
2、prev跟cur中间间隔着比key大的一段区间
把比key大的值往右翻,比key小的值往左翻
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int GetMidNumi(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])//此时mid最大
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else//a[left] > a[mid]
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])//此时mid最小,此时另外两个小的那个就是中间值
        {
            return a[right];
        }
        else
        {
            return a[left];
        }
    }
}
void QuickSort(int* a, int left, int right)
{
    //递归结束条件
    //当递归到begin==0,end==1,keyi==1时,区间通过[begin,kei-1] key [key+1,end]划分后
    //分为[0,0] keyi [2,1],此时会出现left>right的情况
    if (left >= right)
        return;
    int begin = left;
    int end = right;
    //三数选中
    int mini = GetMidNumi(a, left, right);
    Swap(&a[left], &a[mini]);
    
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur<=right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    keyi = prev;
    //[begin,kei-1] key [key+1,end]
    //递归
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}
int main()
{
    int a[] = { 6,1,2,7,9,3,4,5,10,8 };
    QuickSort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
}

二、非递归版本

 递归改非递归:

1.直接改循环:斐波拉契
2.利用栈辅助改循环
之前递归的本质是区间的变化,那么栈也要存区间
#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"
void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int GetMidNumi(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 right;
        }
        else
        {
            return left;
        }
    }
}
void QuickSort(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 mini = GetMidNumi(a, begin, end);
        // 修正:将 left 改为 begin
        Swap(&a[begin], &a[mini]);
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        // 修正:将 right 改为 end
        while (cur <= end)
        {
            if (a[cur] < a[keyi] && ++prev != cur)
            {
                Swap(&a[cur], &a[prev]);
            }
            ++cur;
        }
        Swap(&a[keyi], &a[prev]);
        keyi = prev;
        if (keyi + 1 < end)
        {
            // 先入后出,先入右区间
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1)
        {
            // 先入后出,先入右区间
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}
int main()
{
    int a[] = { 6,1,2,7,9,3,4,5,10,8 };
    QuickSort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}


http://www.kler.cn/a/590403.html

相关文章:

  • 游戏引擎学习第162天
  • 2025年高职大数据可视化实训室建设及实训平台整体解决方案
  • Vue秘籍:如何动态修改页面 Title(浏览器页签名称)?
  • idea cpu干到100%的解决方法?
  • HarmonyOS NEXT开发实战——HUAWEI DevEco Studio 开发指南
  • 车载以太网测试-13【网络层-IGMP协议】
  • 【Godot】Viewpoint
  • mapbox基础,使用线类型geojson加载symbol符号图层,用于标注文字
  • 解锁智慧养老新可能,全面提升养老生活质量
  • Go语言中的错误处理与异常恢复:性能对比与实践思考
  • 【leetcode】51.N皇后
  • 如何检查CMS建站系统的插件是否安全?
  • 《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(60)五火七禽扇灭火 - 接雨水(双指针与动态规划)
  • Kubernetes Network Policy使用场景
  • 微软远程桌面即将下架?Splashtop:更稳、更快、更安全的 RDP 替代方案
  • Django 5实用指南(十四)项目部署与性能优化【完】
  • 调用华为云API实现口罩识别
  • 从以太网 II 到 VLAN 和 Jumbo Frame:数据帧格式解读
  • 前端面试:如何减少项目里面 if-else?
  • 基于Python实现的结合U - Net与Transformer的神经网络用于视网膜血管分割的示例代码