平时做技术实践时，很多问题不是概念不会，而是细节没串起来。拿“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 函数实现：
结合项目来看，这里提供了一种不采用 Hoare 和 Lomuto 分区方案的实现方法。
采用随机枢轴而不进行分区实现更快排序：
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^2 )。
结合项目来看，以上就是C#采用随机枢轴实现更快排序的方法的详细内容，更多关于C#随机枢轴实现更快排序的资料请关注脚本之家其它相关文章！
您可能感兴趣的文章:
- C#实现更快排序算法
- C#排序算法之更快排序解析
- c#实现最简洁的更快排序（你绝对能够看懂）
- C#递归算法之更快排序
- 逐步讲解更快排序算法及C#版的实现示例