C#排序算法之快速排序
更新時間：2010年09月28日 08:57:38 作者：
下面給出的代碼是以數(shù)組最后一個元素作為參考元素，這僅是參考元素選取的方式之一。
快速排序?qū)崿F(xiàn):
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:該方法是以數(shù)組的某個元素為參考元素（軸元素或主元素），將數(shù)組劃分成三個區(qū)域：
【<=參考元素】【參考元素】【>=參考元素】
2. DoSort:該方法會調(diào)用Partition將數(shù)組分區(qū)，并在新產(chǎn)生的子數(shù)組上遞歸調(diào)用最終達到有序的目的。
上面給出的代碼是以數(shù)組最后一個元素作為參考元素，這僅是參考元素選取的方式之一。我們也可以隨即選取數(shù)組的元素或者數(shù)組中間的元素作為參考元素。事實上參考元素的選取對快速排序的性能有很大影響。如果每次選取的參考元素能將數(shù)組分成相對均衡的區(qū)域，快速排序?qū)⒊蔀樽羁斓呐判蛩惴?；但在另一種極端情形下，每次分成的數(shù)組都是1和n-1的關(guān)系，快速排序又會變的很慢。具體的性能數(shù)據(jù)后面再來討論研究。
復(fù)制代碼 代碼如下:
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:該方法是以數(shù)組的某個元素為參考元素（軸元素或主元素），將數(shù)組劃分成三個區(qū)域：
【<=參考元素】【參考元素】【>=參考元素】
2. DoSort:該方法會調(diào)用Partition將數(shù)組分區(qū)，并在新產(chǎn)生的子數(shù)組上遞歸調(diào)用最終達到有序的目的。
上面給出的代碼是以數(shù)組最后一個元素作為參考元素，這僅是參考元素選取的方式之一。我們也可以隨即選取數(shù)組的元素或者數(shù)組中間的元素作為參考元素。事實上參考元素的選取對快速排序的性能有很大影響。如果每次選取的參考元素能將數(shù)組分成相對均衡的區(qū)域，快速排序?qū)⒊蔀樽羁斓呐判蛩惴?；但在另一種極端情形下，每次分成的數(shù)組都是1和n-1的關(guān)系，快速排序又會變的很慢。具體的性能數(shù)據(jù)后面再來討論研究。
相關(guān)文章
學(xué)習(xí)Winform文本類控件(Label、Button、TextBox)
這篇文章主要和大家一起學(xué)習(xí)Winform文本類控件，包含標簽控件(Label)，按鈕控件(Button)，文本框控件(TextBox)和格式文本控件(RichTextBox)，感興趣的小伙伴們可以參考一下2016-05-05
C# 使用PictureBox實現(xiàn)圖片按鈕控件的示例步驟
這篇文章主要介紹了C# 使用PictureBox實現(xiàn)圖片按鈕控件的示例步驟，幫助大家更好的理解和使用c#，感興趣的朋友可以了解下2021-02-02
這篇文章主要給大家介紹了關(guān)于WPF自定義實現(xiàn)IP地址輸入控件的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用WPF具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06
本篇文章是對C#中如何刪除文件目錄或文件的解決方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
WPF技術(shù)的主要特點是數(shù)據(jù)驅(qū)動UI,所以在使用WPF技術(shù)開發(fā)的過程中是以數(shù)據(jù)為核心的，WPF提供了數(shù)據(jù)綁定機制，當數(shù)據(jù)發(fā)生變化時，WPF會自動發(fā)出通知去更新UI，這篇文章通過示例讓大家體驗下WPF MVM，有需要的朋友可以參考下2015-08-08
本篇文章主要對jC#中的小寫string與大寫String進行詳細介紹，相信對大家學(xué)習(xí)會有很好的幫助，需要的朋友一起來看下吧2016-12-12
這篇文章介紹了C#中間語言及ILDASM工具用法，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-01-01
這篇文章主要為大家詳細介紹了C#實現(xiàn)winform版的計算器功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
C#判斷一個字符串是否是數(shù)字或者含有某個數(shù)字的方法
這篇文章主要介紹了C#判斷一個字符串是否是數(shù)字或者含有某個數(shù)字的方法，本文給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2018-06-06
這篇文章介紹了C#獲取全部目錄和文件的簡單實例，有需要的朋友可以參考一下2013-10-10