C# · 12月 25, 2021

c# 快速排序算法

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

步骤为:

1.从数列中挑出一个元素,称为 “基准”(pivot),

2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

平均时间复杂度

快速排序通常明显比其他Ο(nlogn) 算法更快


复制代码 代码如下:
public static void Sort(int[] numbers)
{
QuickSort(numbers,numbers.Length – 1);
}
private static void QuickSort(int[] numbers,int left,int right)
{
if (left < right)
{
int middle = numbers[(left + right) / 2];
int i = left – 1;
int j = right + 1;
while (true)
{
while (numbers[++i] < middle) ;

while (numbers[–j] > middle) ;

if (i >= j)
break;

Swap(numbers,i,j);
}

QuickSort(numbers,left,i – 1);
QuickSort(numbers,j + 1,right);
}
}

private static void Swap(int[] numbers,int i,int j)
{
int number = numbers[i];
numbers[i] = numbers[j];
numbers[j] = number;
}

调用:

复制代码 代码如下:
int[] y = new int[] {4,8,2222,2,1,121,13,434,56,1111,65,7,8 };
Sort(y);
foreach (var item in y)
{
Console.WriteLine(item);
} // 1 2 4 7 8 8 13 56 65 121 434 1111 2222