C#程序使用递归执行快速排序

快速排序是一种使用分而治之方法的排序算法。它带有一个枢轴元件并将其放置在正确的位置。然后，再次使用“快速排序”对枢轴元素左右两侧的数组进行排序。直到完成整个数组的排序为止。

给出了一个演示使用C#中的递归进行快速排序的程序，如下所示-

示例

using System;
namespace QuickSortDemo {
   class Example {
      static public int Partition(int[] arr, int left, int right) {
         int pivot;
         pivot = arr[left];
         while (true) {
            while (arr[left] < pivot) {
               left++;
            }
            while (arr[right] > pivot) {
               right--;
            }
            if (left < right) {
               int temp = arr[right];
               arr[right] = arr[left];
               arr[left] = temp;
            } else {
               return right;
            }
         }
      }
      static public void quickSort(int[] arr, int left, int right) {
         int pivot;
         if (left < right) {
            pivot = Partition(arr, left, right);
            if (pivot > 1) {
               quickSort(arr, left, pivot - 1);
            }  
            if (pivot + 1 < right) {
               quickSort(arr, pivot + 1, right);
            }
         }
      }
      static void Main(string[] args) {
         int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
         int n = 10, i;
         Console.WriteLine("Quick Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         quickSort(arr, 0, 9);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

输出结果

上面程序的输出如下。

Quick Sort
Initial array is: 67 12 95 56 85 1 100 23 60 9
Sorted Array is: 1 9 12 23 56 60 67 85 95 100

现在让我们了解上面的程序。

在main()函数中，首先显示初始数组。然后，quickSort()调用该函数以对数组执行快速排序。为此的代码片段如下-

int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
int n = 10, i;
Console.WriteLine("Quick Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
quickSort(arr, 0, 9);

在函数中quickSort()，通过调用Partition()函数选择枢轴元素。然后quickSort()使用取决于数据透视表值的参数再次调用。为此的代码片段如下-

if (left < right) {
   pivot = Partition(arr, left, right);
   if (pivot > 1) {
      quickSort(arr, left, pivot - 1);
   }
   if (pivot + 1 < right) {
      quickSort(arr, pivot + 1, right);
   }
}

在Partition()方法中，枢轴元素被选为所提供数组的最左侧元素，然后将其设置为数组中的正确位置。演示此步骤的所有代码段如下所示。

int pivot;
pivot = arr[left];
while (true) {
   while (arr[left] < pivot) {
      left++;
   }
   while (arr[right] > pivot) {
      right--;
   }
   if (left < right) {
      int temp = arr[right];
      arr[right] = arr[left];
      arr[left] = temp;
   } else {
      return right;
   }
}