使用递归执行快速排序的 C# 程序
csharpprogrammingserver side programming
快速排序是一种使用分而治之方法的排序算法。它采用枢轴元素并将其放置在正确的位置。然后再次使用快速排序对枢轴元素左侧和右侧的数组进行排序。这样做直到整个数组都排序完毕。
下面给出了一个使用 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("
Sorted 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;
}
}
