数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用递归实现快速排序的 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("
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;
}
}
更新于: 2020年6月26日
5K+ 浏览量
广告