当前位置:

首页 > 编程开发 > C#使用随机枢轴实现快速排序的方法

C#使用随机枢轴实现快速排序的方法

说到排序算法,快速排序可以说是经典中的经典了。它的核心思想其实很直接:先选一个“枢轴”元素,然后通过一次遍历把数组分成两部分——左边全小于枢轴,右边全大于枢轴,接着递归地对左右两个子数组重复这个过程就行。和归并排序不同,快排不需要最后再合并两个有序数组,这个特性让它对辅助空间的需求更少,也是它常常比

本文目录

    说到排序算法,快速排序可以说是经典中的经典了。它的核心思想其实很直接:先选一个“枢轴”元素,然后通过一次遍历把数组分成两部分——左边全小于枢轴,右边全大于枢轴,接着递归地对左右两个子数组重复这个过程就行。和归并排序不同,快排不需要最后再合并两个有序数组,这个特性让它对辅助空间的需求更少,也是它常常比归并排序更受欢迎的原因。

    不过,细心的读者可能已经发现了关键问题:枢轴选得好不好,直接决定了快排的性能。如果每次都能选到中位数,那效率自然没话说;但要是运气不好,每次都选到最大值或最小值,那可就退化到O(N²)了。所以,一个很自然的改进思路就来了——用随机数来决定枢轴的位置。随机枢轴虽然在理论上仍然存在最坏情况,但实际运行中,它的期望时间复杂度可以稳定在O(N log N),这也是它被广泛采用的原因。

    关于数组划分方法,我们之前已经详细聊过两种主流方案:霍尔划分(Hoare)和洛穆托划分(Lomuto)。如果读者对这两种方案还不熟悉,可以先去翻阅一下相关文章,了解一下它们各自的工作原理和适用场景。下面,我们就直接进入正题,看看如何用随机枢轴搭配这两种分区方案来实现快速排序。

    C#使用随机枢轴实现快速排序的方法

    基于 Lomuto 分区的随机枢轴算法

    先来看洛穆托方案。在这种方法中,我们通常选择最后一个元素作为枢轴,然后通过一个指针遍历数组,把小于等于枢轴的元素放到左边。随机化的加入也很简单——在调用分区函数之前,先随机选一个位置,把它和最后一个元素交换,然后继续执行标准的洛穆托分区。

    partition(arr[], lo, hi) 
        pivot = arr[hi] 
        i = lo // 用于交换的位置
        for j := lo to hi – 1 do 
            if arr[j] <= pivot then 
                swap arr[i] with arr[j] 
                i = i + 1 
        swap arr[i] with arr[hi] 
        return i 
    partition_r(arr[], lo, hi) 
        r = Random Number from lo to hi 
        Swap arr[r] and arr[hi] 
        return partition(arr, lo, hi) 
    quicksort(arr[], lo, hi) 
        if lo < hi 
            p = partition_r(arr, lo, hi) 
            quicksort(arr, lo , p-1) 
            quicksort(arr, p+1, hi)

    使用 Lomuto 分区法实现:

    // C# program to illustrate
    // Randomised Quick sort 
    using System;
    class RandomizedQsort 
    {     
      /* This function takes last element as pivot, 
        places the pivot element at its correct 
        position in sorted array, and places all 
        smaller (smaller than pivot) to left of 
        pivot and all greater elements to right 
        of pivot */
      static int partition(int[] arr, int low, int high) 
      { 
        // pivot is chosen randomly 
        random(arr, low, high);
        int pivot = arr[high];
        int i = (low-1); // index of smaller element 
        for (int j = low; j < high; j++) 
        { 
          // If current element is smaller than or 
          // equal to pivot 
          if (arr[j] < pivot) 
          { 
            i++; 
            // swap arr[i] and arr[j] 
            int tempp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = tempp; 
          } 
        } 
        // swap arr[i+1] and arr[high] (or pivot) 
        int tempp2 = arr[i + 1]; 
        arr[i + 1] = arr[high]; 
        arr[high] = tempp2; 
        return i + 1; 
      } 
      // This Function helps in calculating
      // random numbers between low(inclusive)
      // and high(inclusive) 
      static int random(int[] arr, int low, int high) 
      { 
        Random rand = new Random(); 
        int pivot = rand.Next() % (high - low) + low; 
        int tempp1 = arr[pivot];  
        arr[pivot] = arr[high]; 
        arr[high] = tempp1; 
        return partition(arr, low, high);
      } 
      /* The main function that implements Quicksort() 
        arr[] --> Array to be sorted, 
        low --> Starting index, 
        high --> Ending index */
      static void sort(int[] arr, int low, int high) 
      { 
        if (low < high) 
        { 
          /* pi is partitioning index, arr[pi] is 
                now at right place */
          int pi = partition(arr, low, high); 
          // Recursively sort elements before 
          // partition and after partition 
          sort(arr, low, pi - 1); 
          sort(arr, pi + 1, high); 
        } 
      } 
      /* A utility function to print array of size n */
      static void printArray(int[] arr) 
      { 
        int n = arr.Length; 
        for (int i = 0; i < n; ++i) 
          Console.Write(arr[i] + " "); 
        Console.WriteLine(); 
      } 
      // Driver Code 
      static public void Main ()
      {
        int[] arr = {10, 7, 8, 9, 1, 5}; 
        int n = arr.Length; 
        sort(arr, 0, n-1); 
        Console.WriteLine("sorted array"); 
        printArray(arr); 
      } 
    }
    //  This code is contributed by shubhamsingh10

    输出

    已排序数组:
    1 5 7 8 9 10

    时间复杂度: O(N*N)

    辅助空间: O(N) // 由于递归调用栈

    使用霍尔分区法的随机枢轴算法

    接下来看霍尔方案。和洛穆托不同,霍尔的思路是设置两个指针,一个从左向右,一个从右向左,寻找需要交换的元素对。这种方式通常比洛穆托更高效,尤其是对于有大量重复元素的数组。随机化在这里同样适用——在分区前随机选一个元素,然后把它和第一个元素交换,再执行标准霍尔分区。

    partition(arr[], lo, hi)
       pivot = arr[lo]
       i = lo - 1  // Initialize left index
       j = hi + 1  // Initialize right index
        while(True)
               // Find a value in left side greater than pivot
               do
                  i = i + 1
               while arr[i] < pivot
            // Find a value in right side smaller than pivot
               do
                  j = j - 1
               while arr[j] > pivot
               if i >= j then  
                  return j
            else
                   swap arr[i] with arr[j]
           end    while
    partition_r(arr[], lo, hi)
        r = Random number from lo to hi
        Swap arr[r] and arr[lo]
        return partition(arr, lo, hi)
    quicksort(arr[], lo, hi)
        if lo < hi
            p = partition_r(arr, lo, hi)
            quicksort(arr, lo, p)
            quicksort(arr, p+1, hi)

    使用霍尔分区法的实现:

    // C# implementation of QuickSort
    // using Hoare's partition scheme
    using System;
    public class GFG {
        // Driver Code
        public static void Main()
        {
            int[] arr = { 10, 7, 8, 9, 1, 5 };
            int n = arr.Length;
            quickSort(arr, 0, n - 1);
            Console.WriteLine("Sorted array: ");
            printArray(arr, n);
        }
        // This function takes last element as
        // pivot, places the pivot element at
        // its correct position in sorted
        // array, and places all smaller
        // (smaller than pivot) to left of pivot
        // and all greater elements to right
        public static int partition(int[] arr, int low,
                                    int high)
        {
            int pivot = arr[low];
            int i = low - 1, j = high + 1;
            // Find leftmost element greater than
            // or equal to pivot
            while (true) {
                do {
                    i++;
                } while (arr[i] < pivot);
                // Find rightmost element smaller than
                // or equal to pivot
                do {
                    j--;
                } while (arr[j] > pivot);
                // If two pointers met
                if (i >= j)
                    return j;
                swap(arr, i, j);
            }
        }
        // Generates Random Pivot, swaps pivot with
        // end element and calls the partition function
        // In Hoare partition the low element is selected
        // as first pivot
        public static int partition_r(int[] arr, int low,
                                      int high)
        {
            // Generate a random number in between
            // low .. high
            Random rnd = new Random();
            int random = low + rnd.Next(high - low);
            // Swap A[random] with A[high]
            swap(arr, random, low);
            return partition(arr, low, high);
        }
        // The main function that implements QuickSort
        // arr[] --> Array to be sorted,
        // low  --> Starting index,
        // high  --> Ending index
        public static void quickSort(int[] arr, int low,
                                     int high)
        {
            if (low < high) {
                // pi is partitioning index,
                // arr[p] is now at right place
                int pi = partition_r(arr, low, high);
                // Separately sort elements before
                // partition and after partition
                quickSort(arr, low, pi);
                quickSort(arr, pi + 1, high);
            }
        }
        // Function to print an array
        public static void printArray(int[] arr, int n)
        {
            for (int i = 0; i < n; i++)
                Console.Write("{0} ", arr[i]);
            Console.Write("\n");
        }
        public static void swap(int[] arr, int i, int j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    输出

    已排序数组:
    1 5 7 8 9 10

    时间复杂度: O(N*N)

    辅助空间: O(N) // 由于递归调用栈

    使用 generateRandomPivot 函数实现

    如果不想被霍尔和洛穆托的细节束缚,其实还有一种更直接的方式:单独写一个随机生成枢轴的函数,然后手动完成分区逻辑。思路也很清晰:随机选一个位置,把它和最后一个元素交换,然后遍历数组,把小于枢轴的元素都移到左边,最后把枢轴放回正确的位置。这种方法本质上和洛穆托分区相差不大,但代码更直观,适合初学者理解随机枢轴的核心思想。

    使用随机枢轴而不进行分区实现快速排序:

    using System;
    class Program {
      // Function to swap two elements
      static void Swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
      // Function to generate a random pivot index
      static int GenerateRandomPivot(int low, int high) {
        Random random = new Random();
        return low + random.Next(high - low + 1);
      }
      // Function to perform QuickSort
      static void QuickSort(int[] arr, int low, int high) {
        if (low < high) {
          int pivotIndex = GenerateRandomPivot(low, high);
          int pivotValue = arr[pivotIndex];
          // Swap the pivot element with the last element
          Swap(arr, pivotIndex, high);
          int i = low - 1;
          for (int j = low; j < high; j++) {
            if (arr[j] < pivotValue) {
              i++;
              Swap(arr, i, j);
            }
          }
          // Swap the pivot element back to its final position
          Swap(arr, i+1, high);
          // Recursively sort the left and right subarrays
          QuickSort(arr, low, i);
          QuickSort(arr, i+2, high);
        }
      }
      static void Main() {
        int[] arr = {5, 2, 7, 3, 1, 6, 4, 8};
        int n = arr.Length;
        Console.Write("Original array: ");
        for (int i = 0; i < n; i++) {
          Console.Write(arr[i] + " ");
        }
        QuickSort(arr, 0, n-1);
        Console.Write("\nSorted array: ");
        for (int i = 0; i < n; i++) {
          Console.Write(arr[i] + " ");
        }
      }
    }

    输出

    原始数组:5 2 7 3 1 6 4 8
    排序后数组:1 2 3 4 5 6 7 8

    一句话总结,随机枢轴并不能完全消除最坏情况,但它让最坏情况发生的概率变得极低。在实际应用中,它的期望时间复杂度稳稳地落在O(N log N),这就足够了。不过,事情没那么简单——最坏情况下的复杂度仍然是O(N²),所以当你面对极端数据(比如所有元素都相等,或者高度有序的数据)时,还需要额外注意。毕竟,随机化是改善性能的有效手段,但并不是万能的银弹。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    下一篇: 编程的收获
    相关文章 更多
    QQ影音怎么加速播放视频课程
    QQ影音怎么加速播放视频课程

    播放时右键选播放速度,或点控制条倍速,1.25 到 1.5 倍看课最舒服;公式代码类内容别超过 1.25 倍。

    企业微信创建企业提示失败怎么办 实名与填写检查
    企业微信创建企业提示失败怎么办 实名与填写检查

    先看提示属于哪类:名称占用就加后缀,实名不一致就重填本人信息,证件不清晰就重拍。统一社会信用代码逐位核对,连续三次失败别改材料重投,直接联系客服人工核。

    Modern Web Guidance 的 legacy-scan 反转建议应该怎样判断?
    Modern Web Guidance 的 legacy-scan 反转建议应该怎样判断?

    说明源码提交对字符串、生成器和数组的识别边界,以及扫描命令与发行包核验限制。

    Codex 0.170.0 正式版的语音与连接更新,适用范围有哪些限制?
    Codex 0.170.0 正式版的语音与连接更新,适用范围有哪些限制?

    0.170.0 的语音更新限于终端通话协商能力的明确新增,同名工具服务器跨环境支持仍标注实验性质;连接部分则修复大请求回退、认证竞态和云端重连等具体问题。这份正式版公告不足以证明所有账户、所有客户端都已具备完整语音功能。

    Hy4 flash 三种权重怎么选,安装和授权要注意哪些条件?
    Hy4 flash 三种权重怎么选,安装和授权要注意哪些条件?

    了解Hy4 flash、FP8与base的适用任务,阅读官方安装及图文代码,并核对资源和MaaS许可条件。

    OpenAI Python SDK 3.55.0 升级看点:Live MCP 服务配置与预算接口变化
    OpenAI Python SDK 3.55.0 升级看点:Live MCP 服务配置与预算接口变化

    OpenAI Python SDK 3.55.0 升级看点:Live MCP 服务配置与预算接口变化。说明已核实的更新范围、类型兼容性和本地版本确认方法。

    OpenAI Java SDK 4.108.0 的两项新增能力适合哪些项目?
    OpenAI Java SDK 4.108.0 的两项新增能力适合哪些项目?

    OpenAI Java SDK 4.108.0 面向 Live MCP 工具接入与 Managed Agents 预算状态处理,说明新增模型、事件含义、正式发布范围和适用限制。

    Free Claude Code 6.19.37 如何兼顾网页搜索与普通工具调用?
    Free Claude Code 6.19.37 如何兼顾网页搜索与普通工具调用?

    Free Claude Code 6.19.37 在自动搜索时保留客户端工具及选择条件,代理执行搜索后仍返回普通调用。说明适用场景、历史信息保留、请求约束与第三方项目的版本边界。

    Google GenAI Go SDK 1.78.0 的 v1beta 配置优先级怎样判断?
    Google GenAI Go SDK 1.78.0 的 v1beta 配置优先级怎样判断?

    Google GenAI Go SDK 1.78.0 将 Gemini Developer API 默认改为 v1,可用 HTTPOptions.APIVersion 或环境变量保留 v1beta,Vertex AI 默认值不变。

    Google GenAI SDK 3.5.0实时交互值得哪些项目升级评估?
    Google GenAI SDK 3.5.0实时交互值得哪些项目升级评估?

    解释实验性实时支持、环境检查与生产评估中需要验证的条件。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。