C#排序演算法怎樣快速排序呢?下面小編為大家整理了C#排序演算法之快速排序,希望能幫到大家!
快速排序實現:
複製程式碼 程式碼如下:
namespace QuickSort
{
class QuickSort
{
public static void Sort(int[] array)
{
DoSort(array,0, th-1);
}
private static void DoSort( int[] array, int start, int end)
{
if( start < end)
{
int temp = Partition(array, start, end);
DoSort(array, start, temp-1);
DoSort(array, temp + 1, end);
}
}
private static int Partition(int[] array,int start, int end)
{
int index = start - 1;
for( var i=start; i< end; i++)
{
if( array[i] < array[end])
{
index++;
Swap(array, index, i);
}
}
Swap(array, index +1, end);
return index + 1;
}
private static void Swap(int[] array, int index1, int index2)
{
var temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
}
以上即為快速排序的程式碼,這裡有兩個重要的方法:
1、Partition:該方法是以陣列的某個元素為參考元素(軸元素或主元素),將陣列劃分成三個區域:
【<=參考元素】【參考元素】【>=參考元素】
2. DoSort:該方法會呼叫Partition將陣列分割槽,並在新產生的子陣列上遞迴呼叫最終達到有序的目的。
上面給出的程式碼是以陣列最後一個元素作為參考元素,這僅是參考元素選取的方式之一。我們也可以隨即選取陣列的元素或者陣列中間的元素作為參考元素。事實上參考元素的選取對快速排序的效能有很大影響。如果每次選取的參考元素能將陣列分成相對均衡的`區域,快速排序將成為最快的排序演算法;但在另一種極端情形下,每次分成的陣列都是1和n-1的關係,快速排序又會變的很慢。具體的效能資料後面再來討論研究。