首页 > 编程语言 >C#快速排序算法

C#快速排序算法

时间:2023-08-13 12:22:05浏览次数:32  
标签:C# 基准 元素 int 算法 array 排序 指针

快速排序实现原理

快速排序(Quick Sort)是一种常用的排序算法,它基于分治的思想,通过将一个无序的序列分割成两个子序列,并递归地对子序列进行排序,最终完成整个序列的排序。

其基本思路如下:

  1. 选择数组中的一个元素作为基准(pivot)。
  2. 将数组中小于等于基准的元素放在基准的左边,将大于基准的元素放在基准的右边。
  3. 对基准左右两边的子数组分别重复步骤1和步骤2,直到子数组的大小为1或0(递归结束)。

具体实现步骤如下:

  1. 首先选择一个基准元素,通常为数组的第一个或最后一个元素。
  2. 设置两个指针,一个指向数组的起始位置(低位),一个指向数组的结束位置(高位)。
  3. 使用两个指针从两个方向同时遍历数组,直到两个指针相遇。
  4. 从低位开始,比较当前元素与基准元素的大小关系:
    • 如果当前元素小于等于基准元素,则向右移动低位指针。
    • 如果当前元素大于基准元素,则向左移动高位指针。
    • 如果低位指针仍然在高位指针的左侧,则交换低位指针和高位指针所指向的元素。
  5. 重复步骤4,直到低位指针与高位指针相遇。
  6. 将基准元素与相遇位置的元素进行交换,确保基准元素位于其最终的排序位置。
  7. 根据基准元素的位置,将数组分为两个子数组,并递归地对这两个子数组进行快速排序。

快速排序图解

递归的快速排序的代码示例

    public class 快速排序算法
    {
        public static void Sort(int[] array, int low, int high)
        {
            if (low < high)
            {
                //将数组分割为两部分,并返回分割点的索引
                int pivotIndex = Partition(array, low, high);

                //递归对分割后的两部分进行排序
                Sort(array, low, pivotIndex - 1);
                Sort(array, pivotIndex + 1, high);
            }
        }

        private static int Partition(int[] array, int low, int high)
        {
            //选择最后一个元素作为基准元素
            int pivot = array[high];
            int i = low - 1;

            for (int j = low; j <= high - 1; j++)
            {
                //如果当前元素小于等于基准元素,则将它与i+1位置的元素交换
                if (array[j] <= pivot)
                {
                    i++;
                    Swap(array, i, j);
                }
            }

            //将基准元素放置到正确的位置上
            Swap(array, i + 1, high);

            return i + 1; //返回基准元素的索引
        }

        private static void Swap(int[] array, int i, int j)
        {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        public static void QuickSortRun()
        {
            int[] array = { 2, 3, 5, 38, 19, 15, 26, 27, 36, 44, 47, 46, 50, 48, 4 };
            Sort(array, 0, array.Length - 1);
            Console.WriteLine("排序后结果:" + string.Join(", ", array));
        }
    }

总结

快速排序是一种高效的排序算法,它的优势在于平均时间复杂度为O(nlogn),在实际应用中通常表现出色。然而,最坏情况下的时间复杂度可能达到O(n^2),但通过合适的优化方法如随机选择基准元素、三数取中法等,可以避免最坏情况的发生,提高性能。递归方式简洁易懂但对于大数据量的排序可能会出现栈溢出的问题,而使用栈模拟递归则可以解决这个问题。

标签:C#,基准,元素,int,算法,array,排序,指针
From: https://www.cnblogs.com/Can-daydayup/p/17626390.html

相关文章

  • Codeforces Round 892 (Div.2)
    A.UnitedWeStand题解赛时想复杂了题目要求我们保证数组\(c\)中的数不是数组\(b\)中任意一个数的因子我们考虑将最小值置于数组\(b\)即可constintN=2e5+10,M=4e5+10;intn;inta[N];voidsolve(){cin>>n;intmi=INF;for(inti......
  • CSP模拟-19
    D.西安行原AGC013E思路DP.最朴素的DP是\(\Theta(n^2)\)的,考虑i是当前DP到的点,j是当前线段的起点.考虑分类讨论数据范围很抽象,所以考虑用矩阵加速。首先试着把它转换成线性的赋予它一个新的组合意义:把每条线段看作一个整体\(a_i\)因为题最后求的是\(\prod_{i=1}^{num}a_i^......
  • dectron2框架export导出并使用 onnx 记录
    pythontools/deploy/export_model.py\--sample-image/Users/gatilin/PycharmProjects/model-graphviz-plot/model_graph/detectron/000000439715.jpg\--config-fileconfigs/COCO-InstanceSegmentation/mask_rcnn_R_50_FPN_3x.yaml\--export-methodt......
  • java.lang.NoSuchMethodError: com.baomidou.mybatisplus.core.toolkit.StringUtils.i
    1、原因这是由于两个版本不一致导致的;<!--mybatis-plus--><dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.1</version&......
  • RCC & GPIO库函数&传感器输入
    RCC: ResetandClockControl,即复位和时钟控制。  一般在.h文件的末尾都是一些函数声明,RCC常用的三个函数(外设时钟控制,没有时钟外设不工作):voidRCC_AHBPeriphClockCmd(uint32_tRCC_AHBPeriph,FunctionalStateNewState);voidRCC_APB2PeriphClockCmd(uint32_tRCC_AP......
  • c语言笔记2
    c语言笔记2(关键字,数据类型,运算符,流程控制语句)1.c语言中的关键字学习关键字的目的是了解存在哪些关键字,另外,在定义变量名、函数名(标识符命名)避免使用关键字1.1数据类型相关的关键字char字符类型,占1个字节,ASCII表有128字符,每个字符占1个字节。short短整型,占2个字节i......
  • centos7忘记密码处理办法
    此界面按e进入grub编辑界面进入grub编辑界面。把linux16这行的ro修改为rwinit=/sysroot/bin/sh。按ctrl+x进入单用户模式登陆进去后,输入如下命令:chroot/sysroot/#切换到原系统LANG=en#设置显示语言passwdroot#修改root密码touch/.autorelabel#如果之前系......
  • Java| jdk的src源码目录讲解
    JavaJDK的源代码目录(src)包含了Java核心类库的源代码,它提供了Java编程语言的基本功能和类。src目录结构通常按照包的层次结构组织,每个包对应一个文件夹,而每个类则在相应的包文件夹中以.java文件的形式存在。目录结构-com--sun-java--applet--awt--beans--io--lang--mat......
  • 8-13|Cannot run program "C:\Users\Administrator\AppData\Local\Temp\GoLand
    您的错误消息指的是尝试运行的程序与您当前的Windows版本不兼容。这可能是因为您正在使用一个旧版本的Windows(例如32位的版本)并试图运行一个为新版本(例如64位)编译的程序。以下是解决这个问题的建议步骤:1.**确认您的操作系统版本**: -打开“运行”(按`Win+R`),输入`msinfo32......
  • abc270d Stones
    abc270d直接贪心每次取最大的会有问题,比如说下面的例子11245我们考虑dp\(f[i]\)表示在先手的情况下,有i个石头的局面,最多能拿多少个石头,同时记录\(g[i]\)表示选的哪一个\(a[i]\)那么转移就是\(f[i]=max(f[i-a[j]-a[g[i-a[j]]]]+a[j])\)#include<algorithm>#include<cst......