在C#中,快速排序法(QuickSort)是一種高效的排序算法,其核心在于選擇一個(gè)基準(zhǔn)元素(Pivot),然后將數(shù)組分為兩部分:一部分包含小于基準(zhǔn)的元素,另一部分包含大于或等于基準(zhǔn)的元素。這個(gè)過程稱為分區(qū)(Partition)。
以下是選擇基準(zhǔn)元素的幾種常見方法:
在C#中實(shí)現(xiàn)快速排序時(shí),可以根據(jù)具體需求和數(shù)據(jù)特點(diǎn)選擇合適的基準(zhǔn)元素。下面是一個(gè)使用中間元素作為基準(zhǔn)的簡單快速排序示例:
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]; // 選擇中間元素作為基準(zhǔn)
int i = left + 1;
int j = right;
while (true)
{
while (i <= j && arr[i] < pivot)
{
i++;
}
while (i <= j && arr[j] > pivot)
{
j--;
}
if (i <= j)
{
Swap(arr, i, j);
}
else
{
break;
}
}
Swap(arr, left, j);
return j;
}
private static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
請(qǐng)注意,這個(gè)示例僅用于演示目的,實(shí)際應(yīng)用中可能需要根據(jù)具體情況進(jìn)行調(diào)整和優(yōu)化。