C#使用隨機(jī)樞軸實(shí)現(xiàn)快速排序的方法
更新時間：2026年04月15日 08:48:03 作者：hefeng_aspnet
本文探討了如何使用隨機(jī)樞軸實(shí)現(xiàn)快速排序,介紹了Lomuto和Hoare兩種分區(qū)方案,并提出了一種不使用傳統(tǒng)分區(qū)方案的實(shí)現(xiàn)方法,需要的朋友可以參考下
本文將探討如何使用隨機(jī)樞軸實(shí)現(xiàn)快速排序。在快速排序中，我們首先對數(shù)組進(jìn)行原地分割，使得樞軸元素左側(cè)的所有元素都小于樞軸元素，而右側(cè)的所有元素都大于樞軸元素。然后，我們遞歸地對左右兩個子數(shù)組執(zhí)行相同的分割過程。 與歸并排序不同，快速排序不需要合并兩個已排序的數(shù)組。因此，快速排序所需的輔助空間比歸并排序更少，這也是它通常優(yōu)于歸并排序的原因。使用隨機(jī)生成的樞軸可以進(jìn)一步降低快速排序的時間復(fù)雜度。
我們已經(jīng)討論了兩種流行的數(shù)組劃分方法——霍爾劃分方案和洛穆托劃分方案。
建議讀者已經(jīng)閱讀過這篇文章，或者知道如何使用這兩種劃分方案中的任何一種來實(shí)現(xiàn)快速排序。
基于 Lomuto 分區(qū)的隨機(jī)樞軸算法
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 分區(qū)法實(shí)現(xiàn)：
// 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輸出
已排序數(shù)組： 1 5 7 8 9 10
時間復(fù)雜度： O(N*N)
輔助空間： O(N) // 由于遞歸調(diào)用棧
使用霍爾分區(qū)法的隨機(jī)樞軸算法
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)
使用霍爾分區(qū)法的實(shí)現(xiàn)：
// 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;
? ? }
}輸出
已排序數(shù)組： 1 5 7 8 9 10
時間復(fù)雜度： O(N*N)
輔助空間： O(N) // 由于遞歸調(diào)用棧
使用 generateRandomPivot 函數(shù)實(shí)現(xiàn)：
這里提供了一種不使用 Hoare 和 Lomuto 分區(qū)方案的實(shí)現(xiàn)方法。
使用隨機(jī)樞軸而不進(jìn)行分區(qū)實(shí)現(xiàn)快速排序：
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] + " ");
? ? }
? }
}輸出
原始數(shù)組：5 2 7 3 1 6 4 8 排序后數(shù)組：1 2 3 4 5 6 7 8
使用隨機(jī)樞軸，我們將預(yù)期或平均時間復(fù)雜度改進(jìn)為 O (N log N)。最壞情況下的復(fù)雜度仍然是 O ( N^2 )。
以上就是C#使用隨機(jī)樞軸實(shí)現(xiàn)快速排序的方法的詳細(xì)內(nèi)容，更多關(guān)于C#隨機(jī)樞軸實(shí)現(xiàn)快速排序的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C# StringBuilder和string，文章圍繞StringBuilder和string的相關(guān)資料展開內(nèi)容,需要的朋友可以參考一下2021-11-11
c# 實(shí)現(xiàn)MD5,SHA1,SHA256,SHA512等常用加密算法源代碼
c# 如何實(shí)現(xiàn)MD5,SHA1,SHA256,SHA512等常用加密算法,需要的朋友可以參考下2012-12-12
這篇文章主要為大家詳細(xì)介紹了C#中操作文件和注冊表的相關(guān)知識,文中的示例代碼講解詳細(xì),具有一定的借鑒價值,有需要的小伙伴可以參考下2024-03-03
使用數(shù)字簽名實(shí)現(xiàn)數(shù)據(jù)庫記錄防篡改（Java實(shí)現(xiàn)）
本文主要介紹了Java中使用數(shù)字簽名實(shí)現(xiàn)數(shù)據(jù)庫記錄防篡改的方法與步驟。具有很好的參考價值，下面跟著小編一起來看下吧2017-01-01
C#將部分Controls數(shù)據(jù)導(dǎo)入對象并存入ini中的操作方法
在Winform設(shè)計中,經(jīng)常需要將控件數(shù)據(jù)導(dǎo)出到屬性或字段中,本文詳細(xì)介紹了如何優(yōu)化這一過程,包括控件和屬性的遍歷,以及使用FieldInfo的getSet函數(shù)和Ini類庫來實(shí)現(xiàn)數(shù)據(jù)的有效存儲和轉(zhuǎn)換,感興趣的朋友跟隨小編一起看看吧2024-10-10
本文給大家簡單介紹了Devexpress treelist 知識，包括屬性列表，事件及使用方法，非常不錯，具有參考借鑒價值，需要的朋友參考下2016-12-12
C#打包部署并把.net framework框架打到安裝包的方法步驟
打包c(diǎn)#程序時,有時需要添加.net framework組件到安裝包,本文就來介紹一下C#打包部署并把.net framework框架打到安裝包的方法步驟,具有一定的參考價值,感興趣的可以了解一下2023-10-10
c#通過app.manifest使程序以管理員身份運(yùn)行
通常我們使用c#編寫的程序不會彈出這個提示，也就無法以管理員身分運(yùn)行。微軟的操作系統(tǒng)使用微軟的產(chǎn)品方法當(dāng)然是有的，通過app.manifest配置可以使程序打開的時候，彈出UAC提示需要得到允許才可以繼續(xù)，這樣就獲得了管理員的權(quán)限來執(zhí)行程序2015-01-01
C#中使用XmlDocument類來創(chuàng)建和修改XML格式的數(shù)據(jù)文件
這篇文章主要介紹了C#中使用XmlDocument類來創(chuàng)建和修改XML格式的數(shù)據(jù)文件的方法,XmlDocument類被包含在.NET框架中,需要的朋友可以參考下2016-04-04
C#算法函數(shù)：獲取一個字符串中的最大長度的數(shù)字
這篇文章介紹了使用C#獲取一個字符串中最大長度的數(shù)字的實(shí)例代碼，有需要的朋友可以參考一下。2016-06-06