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

六、C#快速排序算法

简介

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

其基本思路如下:

  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#十大排序总结-CSDN博客


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

相关文章:

  • 靜態IP與DHCP的區別和用法
  • MySQL数据库下载及安装教程
  • OB删除1.5亿数据耗费2小时
  • 智能工厂的设计软件 认知系统和内涵智能机 之1
  • python脚本中使用git命令
  • Mybatis加密解密查询操作(sql前),where要传入加密后的字段时遇到的问题
  • SQL server服务连接失败,通过端口1433连接到主机 localhost的 TCP/IP 连接失败
  • GitHub Copilot+ESP开发实战-串口
  • 【STM32嵌入式系统设计与开发】——6矩阵按键应用(4x4)
  • QT配置libtorch(一步到位!!!防止踩坑)
  • Flutter-实现扫描线移动效果
  • HarmonyOS NEXT应用开发之Navigation实现多设备适配案例
  • 学习总结1
  • React状态管理库快速上手-Redux(一)
  • 2024.3.19
  • WebSocket 和SSE的区别以及优缺点
  • publicPath 和 __webpack_public_path__ 和 process.env.BASE_URL的区别和使用方法
  • 使用Vscode连接云进行前端开发
  • Java使用itextpdf往pdf中插入图片
  • nodejs 使用express插件multer文件上传,接收不到文件的bug
  • 未来汽车EE架构趋势
  • 数库据设计最佳实践
  • React——关于表单元素
  • C#,图论与图算法,计算无向连通图中长度为n环的算法与源代码
  • 湖北省地质灾害分布数据 崩塌滑坡泥石流空间分布地质灾害详查等数据集
  • Spark-Scala语言实战(3)