C#排序算法之快速排序
更新時(shí)間：2010年09月28日 08:57:38 作者：
下面給出的代碼是以數(shù)組最后一個(gè)元素作為參考元素，這僅是參考元素選取的方式之一。
快速排序?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;
}
}
}
以上即為快速排序的代碼，這里有兩個(gè)重要的方法：
1、Partition:該方法是以數(shù)組的某個(gè)元素為參考元素（軸元素或主元素），將數(shù)組劃分成三個(gè)區(qū)域：
【<=參考元素】【參考元素】【>=參考元素】
2. DoSort:該方法會(huì)調(diào)用Partition將數(shù)組分區(qū)，并在新產(chǎn)生的子數(shù)組上遞歸調(diào)用最終達(dá)到有序的目的。
上面給出的代碼是以數(shù)組最后一個(gè)元素作為參考元素，這僅是參考元素選取的方式之一。我們也可以隨即選取數(shù)組的元素或者數(shù)組中間的元素作為參考元素。事實(shí)上參考元素的選取對(duì)快速排序的性能有很大影響。如果每次選取的參考元素能將數(shù)組分成相對(duì)均衡的區(qū)域，快速排序?qū)⒊蔀樽羁斓呐判蛩惴?；但在另一種極端情形下，每次分成的數(shù)組都是1和n-1的關(guān)系，快速排序又會(huì)變的很慢。具體的性能數(shù)據(jù)后面再來(lái)討論研究。
復(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;
}
}
}
以上即為快速排序的代碼，這里有兩個(gè)重要的方法：
1、Partition:該方法是以數(shù)組的某個(gè)元素為參考元素（軸元素或主元素），將數(shù)組劃分成三個(gè)區(qū)域：
【<=參考元素】【參考元素】【>=參考元素】
2. DoSort:該方法會(huì)調(diào)用Partition將數(shù)組分區(qū)，并在新產(chǎn)生的子數(shù)組上遞歸調(diào)用最終達(dá)到有序的目的。
上面給出的代碼是以數(shù)組最后一個(gè)元素作為參考元素，這僅是參考元素選取的方式之一。我們也可以隨即選取數(shù)組的元素或者數(shù)組中間的元素作為參考元素。事實(shí)上參考元素的選取對(duì)快速排序的性能有很大影響。如果每次選取的參考元素能將數(shù)組分成相對(duì)均衡的區(qū)域，快速排序?qū)⒊蔀樽羁斓呐判蛩惴?；但在另一種極端情形下，每次分成的數(shù)組都是1和n-1的關(guān)系，快速排序又會(huì)變的很慢。具體的性能數(shù)據(jù)后面再來(lái)討論研究。
相關(guān)文章
C# WinForm實(shí)現(xiàn)窗體上控件自由拖動(dòng)功能示例
這篇文章主要介紹了C# WinForm實(shí)現(xiàn)窗體上控件自由拖動(dòng)功能,涉及WinForm控件屬性及事件響應(yīng)相關(guān)操作技巧,需要的朋友可以參考下2017-07-07
本篇文章主要分享的是3個(gè)免費(fèi)的二維碼接口的對(duì)接代碼和測(cè)試得出的注意點(diǎn)及區(qū)別。具有很好的參考價(jià)值，需要的朋友一起來(lái)看下吧2016-12-12
C#基于面向過(guò)程計(jì)算加權(quán)平均分的方法
這篇文章主要介紹了C#基于面向過(guò)程計(jì)算加權(quán)平均分的方法,涉及C#數(shù)學(xué)運(yùn)算的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
C# Winform 分頁(yè)功能的實(shí)現(xiàn)
本文主要介紹了C# Winform 分頁(yè)功能的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
這篇文章主要介紹了C# 線程相關(guān)知識(shí)，文中講解非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
這篇文章介紹了C#線程池ThreadPool的用法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06
這篇文章主要給大家介紹C# winform快捷鍵設(shè)置技巧，涉及到C winform快捷鍵相關(guān)知識(shí)，對(duì)C winform知識(shí)感興趣的朋友可以參考下本篇文章2015-10-10
C#操作SQLite數(shù)據(jù)庫(kù)方法小結(jié)(創(chuàng)建,連接,插入,查詢,刪除等)
這篇文章主要介紹了C#操作SQLite數(shù)據(jù)庫(kù)方法,包括針對(duì)SQLite數(shù)據(jù)庫(kù)的創(chuàng)建,連接,插入,查詢,刪除等操作,并提供了一個(gè)SQLite的封裝類(lèi),需要的朋友可以參考下2016-07-07
C#在新建線程中使用Timer無(wú)效問(wèn)題及解決
這篇文章主要介紹了C#在新建線程中使用Timer無(wú)效問(wèn)題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-08-08
C#調(diào)用RabbitMQ實(shí)現(xiàn)消息隊(duì)列的示例代碼
這篇文章主要介紹了C#調(diào)用RabbitMQ實(shí)現(xiàn)消息隊(duì)列的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12