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)

// 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

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;
? ? }
}

已排序數(shù)組：
1 5 7 8 9 10

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