c#-快速排序-算法

快速排序使用分治法（Divide and conquer）政策來把一個串行（list）分為兩個子串行（sub-lists）。

步驟為：

1.從數列中挑出一個元素，稱為 "基準"（pivot），

2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作。

3.遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的疊代（iteration）中，它至少會把一個元素擺到它最後的位置去。

平均時間複雜度

 快速排序通常明顯比其他Ο(n log n) 算法更快

<code>public</code> <code>static</code> <code>void</code> <code>Sort(</code><code>int</code><code>[] numbers)</code>

<code>{</code>

<code>    </code><code>QuickSort(numbers, 0, numbers.Length - 1);</code>

<code>}</code>

<code>private</code> <code>static</code> <code>void</code> <code>QuickSort(</code><code>int</code><code>[] numbers,</code><code>int</code> <code>left,</code><code>int</code> <code>right)</code>

<code>    </code><code>if</code> <code>(left &lt; right)</code>

<code>    </code><code>{</code>

<code>        </code><code>int</code> <code>middle = numbers[(left + right) / 2];</code>

<code>        </code><code>int</code> <code>i = left - 1;</code>

<code>        </code><code>int</code> <code>j = right + 1;</code>

<code>        </code><code>while</code> <code>(</code><code>true</code><code>)</code>

<code>        </code><code>{</code>

<code>            </code><code>while</code> <code>(numbers[++i] &lt; middle) ;</code>

<code>            </code><code>while</code> <code>(numbers[--j] &gt; middle) ;</code>

<code>            </code><code>if</code> <code>(i &gt;= j)</code>

<code>                </code><code>break</code><code>;</code>

<code>            </code><code>Swap(numbers, i, j);</code>

<code>        </code><code>}</code>

<code>        </code><code>QuickSort(numbers, left, i - 1);</code>

<code>        </code><code>QuickSort(numbers, j + 1, right);</code>

<code>    </code><code>}</code>

<code>private</code> <code>static</code> <code>void</code> <code>Swap(</code><code>int</code><code>[] numbers,</code><code>int</code> <code>i,</code><code>int</code> <code>j)</code>

<code>    </code><code>int</code> <code>number = numbers[i];</code>

<code>    </code><code>numbers[i] = numbers[j];</code>

<code>    </code><code>numbers[j] = number;</code>

　　

調用：

<code>int</code><code>[] y =</code><code>new</code> <code>int</code><code>[] {4,8,2222,2,1,121,13,434,56,1111,65,7,8 };</code>

<code>Sort(y);</code>

<code>foreach</code> <code>(</code><code>var</code> <code>item</code><code>in</code> <code>y)</code>

<code>    </code><code>Console.WriteLine(item);</code>

<code>}&lt;br&gt;</code><code>// 1 2 4 7 8 8 13 56 65 121 434 1111 2222</code>

    本文轉自曾祥展部落格園部落格，原文連結：http://www.cnblogs.com/zengxiangzhan/p/3305296.html，如需轉載請自行聯系原作者