C#排序算法之快速排序

相關推薦

C#排序算法之快速排序

　　C#排序算法怎樣快速排序呢？下面小編為大家整理了C#排序算法之快速排序，希望能幫到大家！

　　快速排序實現:

　　復制代碼代碼如下:

　　namespace QuickSort

　　{

　　class QuickSort

　　{

　　public static void Sort(int[] array)

　　{

　　DoSort(array,0, array.Length-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的關系，快速排序又會變的很慢。具體的性能數據后面再來討論研究。

【C#排序算法之快速排序】相關文章：

C語言中使用快速排序算法對元素排序的實例06-20