以下是C#語言中快速排序算法的實現:
public static void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
int pivotIndex = Partition(arr, left, right);
QuickSort(arr, left, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, right);
}
}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
while (left < right)
{
while (left < right && arr[right] >= pivot)
{
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot)
{
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
在上述代碼中,QuickSort()
方法是快速排序的主方法,它接受一個整數數組arr
以及數組的左右邊界left
和right
作為參數。在QuickSort()
方法中,我們首先判斷左邊界是否小于右邊界,如果是,則調用Partition()
方法對數組進行劃分,并返回劃分點的索引。然后,我們遞歸地對數組的左半部分和右半部分進行快速排序。
Partition()
方法是快速排序的關鍵步驟,它接受一個整數數組arr
以及數組的左右邊界left
和right
作為參數。在Partition()
方法中,我們首先選擇數組的第一個元素作為基準值(pivot)。然后,我們使用兩個指針left
和right
分別從數組的左側和右側開始遍歷數組,將大于等于基準值的元素移到數組的左側,將小于基準值的元素移到數組的右側。最后,我們將基準值放到正確的位置上,并返回該位置的索引。
要使用上述代碼對數組進行快速排序,只需調用QuickSort()
方法即可。例如:
int[] arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
QuickSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.Write(num + " ");
}
上述代碼將輸出排序后的數組:1 1 2 3 3 4 5 5 5 6 9
。