資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽量
廣告