在這篇文章中，我會向大家展示一些排序算法的可視化過程。我還寫了一個工具，大家可對比查看某兩種排序算法。
引言
首先，我認為是最重要的是要理解什么是“排序算法”。根據維基百科，排序算法（Sorting algorithm）是一種能將一串數據依照特定排序方式進行排列的一種算法。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法（例如搜索算法與合并算法）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字數據以及產生人類可讀的輸出結果。
接下來，我會說明一些算法。所有算法皆由C#代碼實現，大部分的算法思想都可以在維基百科上找到。 所呈現的算法有：
- 雙向冒泡排序
- 冒泡排序
- 桶排序
- 梳排序
- 循環排序
- 地精排序
- 堆排序
- 插入排序
- 歸并排序
- 奇偶排序
- 鴿籠排序
- 快速排序
- 使用冒泡的快排
- 選擇排序
- 希爾排序
我已經決定要創建GUI可視化的排序算法。該項目還允許用戶保存為GIF圖像及設置動畫輸出排序速度。
使用代碼
該解決方案由兩個項目組成。第一個項目稱為組件提供的創建GIF動畫圖像類。該項目是基于NGIF項目的。關于這個項目的更多信息可以在這里找到。
第二個項目可以稱為排序比較，它是解決方案的主要組成部分。其中，通過一個名為frmMain的結構可以選擇排序算法，設置你想要排序，排序的速度，排序數量，并選擇是否要創建動態圖片。在窗體上放置兩個面板稱為pnlSort1和pnlSort2，其中分揀可視化的呈現方式。
每個算法都都通過自己的排序方式進行命名，并接受一個IList參數，并返回一個IList對象。
DrawSamples方法可以在面板上進行繪圖。產生的隨機樣本之后就會調用它。通過點擊隨機按鈕生成的樣本會保存在數組中。
private void DrawSamples()
{
g.Clear(Color.White);
for (int i = 0; i < array.Count; i++)
{
int x = (int)(((double)pnlSamples.Width / array.Count) * i);
Pen pen = new Pen(Color.Black);
g.DrawLine(pen, new Point(x, pnlSamples.Height),
new Point(x, (int)(pnlSamples.Height - (int)array[i])));
}
}</pre>
該方法隨機產生數據放于數組中。
public void Randomize(IList list)
{
for (int i = list.Count - 1; i > 0; i--)
{
int swapIndex = rng.Next(i + 1);
if (swapIndex != i)
{
object tmp = list[swapIndex];
list[swapIndex] = list[i];
list[i] = tmp;
}
}
}
在排序過程中，當復選框創建的動畫被選中，數組中兩個數交換的話就會產生圖像。此圖像索引從0到n，其中n代表交換的次數。
private void SavePicture()
{
ImageCodecInfo myImageCodecInfo = this.getEncoderInfo("image/gif");
EncoderParameter myEncoderParameter = new EncoderParameter(
System.Drawing.Imaging.Encoder.Compression, (long)EncoderValue.CompressionLZW);
EncoderParameter qualityParam =
new EncoderParameter(System.Drawing.Imaging.Encoder.Quality, 0L);
EncoderParameters myEncoderParameters = new EncoderParameters(1);
EncoderParameters encoderParams = new EncoderParameters(2);
encoderParams.Param[0] = qualityParam;
encoderParams.Param[1] = myEncoderParameter;
string destPath =
System.IO.Path.Combine(txtOutputFolder.Text, imgCount + ".gif");
bmpsave.Save(destPath, myImageCodecInfo, encoderParams);
imgCount++;
}</pre>
排序算法
冒泡排序也被稱為下沉排序，是一個簡單的排序算法，通過多次重復比較每對相鄰的元素，并按規定的順序交換他們，最終把數列進行排好序。一直重復下去，直到結束。該算法得名于較小元素“氣泡”會“浮到”列表頂部。由于只使用了比較操作，所以這是一個比較排序。
冒泡排序算法的運作如下：
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。
- 針對所有的元素重復以上的步驟，除了最后一個。
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
由于它的簡潔，冒泡排序通常被用來對于程序設計入門的學生介紹算法的概念。但同樣簡單的插入排序比冒泡排序性能更好，所以有些人認為不需要再教冒泡排序了。
public IList BubbleSort(IList arrayToSort)
{
int n = arrayToSort.Count - 1;
for (int i = 0; i < n; i++)
{
for (int j = n; j > i; j--)
{
if (((IComparable)arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
{
object temp = arrayToSort[j - 1];
arrayToSort[j - 1] = arrayToSort[j];
arrayToSort[j] = temp;
RedrawItem(j);
RedrawItem(j - 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
}
return arrayToSort;
}
| Worst case performance: |
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>O(n)</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1) auxiliary</td>
</tr>
</tbody>
</table>
雞尾酒排序，也稱為雙向冒泡排序、調酒器排序、攪拌排序（可以參考選擇排序的一個變種）、紋波排序、接送排序，或歡樂時光排序。它由冒泡排序變化而來，是一種穩定的比較排序算法。該算法不同于冒泡排序，它在排序上由兩個方向同時進行。該排序算法只是比冒泡排序稍難實現，但解決了冒泡排序中的“烏龜問題”（數組尾部的小值）。
首先從左向右方向為大元素移動方向，從右向左方向為小元素移動方向，然后每個元素都依次執行。在第 i 次移動后，前 i 個元素和后個 i 元素都放到了正確的位置，也不需要在檢查一次。每次縮短已排序的那部分列表，都可以減半操作次數。
但是在亂數序列的狀態下，雙向冒泡排序與冒泡排序的效率都很差勁。
public IList BiDerectionalBubleSort(IList arrayToSort)
{
int limit = arrayToSort.Count;
int st = -1;
bool swapped = false;
do
{
swapped = false;
st++;
limit--;
for (int j = st; j < limit; j++)
{
if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
{
object temp = arrayToSort[j];
arrayToSort[j] = arrayToSort[j + 1];
arrayToSort[j + 1] = temp;
swapped = true;
RedrawItem(j);
RedrawItem(j + 1);
pnlSamples.Refresh();
if(chkCreateAnimation.Checked)
SavePicture();
}
}
for (int j = limit - 1; j >= st; j--)
{
if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
{
object temp = arrayToSort[j];
arrayToSort[j] = arrayToSort[j + 1];
arrayToSort[j + 1] = temp;
swapped = true;
RedrawItem(j);
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
} while (st < limit && swapped);
return arrayToSort;
}</pre>
| Worst case performance: |
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>O(n)</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1) auxiliary</td>
</tr>
</tbody>
</table>
桶排序，或稱為箱排序，是一種把數列劃分成若干個桶的排序算法。在每個桶內各自排序，或者使用不同的排序算法，或通過遞歸方式繼續使用桶排序算法。這是一個分布排序，是最能體現出數字意義的一種基數排序。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
桶排序的流程：
- 設置一個定量的數組當作空桶子。
- 尋訪串行，并且把項目一個一個放到對應的桶子去。
- 對每個不是空的桶子進行排序。
- 從不是空的桶子里把項目再放回原來的串行中。
public IList BucketSort(IList arrayToSort)
{
if (arrayToSort == null || arrayToSort.Count == 0) return arrayToSort;
object max = arrayToSort[0];
object min = arrayToSort[0];
for (int i = 0; i 0)
{
max = arrayToSort[i];
}
if (((IComparable)arrayToSort[i]).CompareTo(min) < 0)
{
min = arrayToSort[i];
}
}
ArrayList[] holder = new ArrayList[(int)max - (int)min + 1];
for (int i = 0; i < holder.Length; i++)
{
holder[i] = new ArrayList();
}
for (int i = 0; i < arrayToSort.Count; i++)
{
holder[(int)arrayToSort[i] - (int)min].Add(arrayToSort[i]);
}
int k = 0;
for (int i = 0; i 0)
{
for (int j = 0; j < holder[i].Count; j++)
{
arrayToSort[k] = holder[i][j];
RedrawItem(k);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
k++;
}
}
}
return arrayToSort;
}</pre>
| Worst case performance: |
<td>O(n<sup>2</sup>.k)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n.k)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(n.k)</td>
</tr>
</tbody>
</table>
梳排序
梳排序是一個相對簡單的排序算法，最初它由Wlodzimierz Dobosiewicz于1980年設計出來。后來由斯蒂芬和理查德重新發現和推廣。他們的文章在1991年4月發表在字節雜志上。梳排序改善了冒泡排序和類似快速排序的競爭算法。其要旨在于消除烏龜，亦即在陣列尾部的小數值，這些數值是造成冒泡排序緩慢的主因。相對地，兔子，亦即在陣列前端的大數值，不影響冒泡排序的效能。
在冒泡排序中，任何兩個元素進行比較時，他們總是距離彼此為1。梳排序的基本思想是可以不是1。
梳排序中，開始時的間距設定為列表長度，然后每一次都會除以損耗因子(一般為1.3)。必要的時候，間距可以四舍五入，不斷重復，直到間距變為1。然后間距就保持為1，并排完整個數列。最后階段就相當于一個冒泡排序，但此時大多數烏龜已經處理掉，此時的冒泡排序就高效了。
public IList CombSort(IList arrayToSort)
{
int gap = arrayToSort.Count;
int swaps = 0;
do
{
gap = (int)(gap / 1.247330950103979);
if (gap 0)
{
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[i + gap];
arrayToSort[i + gap] = temp;
RedrawItem(i);
RedrawItem(i + gap);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
swaps = 1;
}
i++;
} while (!(i + gap >= arrayToSort.Count));
} while (!(gap == 1 && swaps == 0));
return arrayToSort;
}</pre>
| Worst case performance: |
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1)</td>
</tr>
</tbody>
</table>
圈排序
Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.
Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written zero times, if it’s already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.
它是一個就地、不穩定的排序算法，根據原始的數組，一種理論上最優的比較，并且與其它就地排序算法不同。它的思想是把要排的數列分解為圈，即可以分別旋轉得到排序結果。
不同于其它排序的是，元素不會被放入數組的中任意位置從而推動排序。每個值如果它已經在其正確的位置則不動，否則只需要寫一次即可。也就是說僅僅最小覆蓋就能完成排序。
public IList CycleSort(IList arrayToSort)
{
int writes = 0;
for (int cycleStart = 0; cycleStart < arrayToSort.Count; cycleStart++)
{
object item = arrayToSort[cycleStart];
int pos = cycleStart;
do
{
int to = 0;
for (int i = 0; i < arrayToSort.Count; i++)
{
if (i != cycleStart && ((IComparable)arrayToSort[i]).CompareTo(item) < 0)
{
to++;
}
}
if (pos != to)
{
while (pos != to && ((IComparable)item).CompareTo(arrayToSort[to]) == 0)
{
to++;
}
object temp = arrayToSort[to];
arrayToSort[to] = item;
RedrawItem(to);
item = temp;
RedrawItem(cycleStart);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
writes++;
pos = to;
}
} while (cycleStart != pos);
}
return arrayToSort;
}</pre>
| Worst case performance: |
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1)</td>
</tr>
</tbody>
</table>
地精排序
地精排序（gnome sorting，大部分地方翻成“侏儒排序”，“地精排序”明明更好聽呀，本文就這么用了。）最初由哈米德在2000年的時候提出，當時稱為傻瓜排序，之后被迪克說明并且命名為“地精排序”。除了某個元素是經過一系列的互換（類似冒泡排序）才到了它的正確位置之外，它和插入排序挺相似。
它在概念上很簡單，不需要嵌套循環。運行時間是O(n2)，如果列表基本有序，則時間為O(n)。實際上，它和插入排序一樣，平均運行時O(n2)。
The algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. It takes advantage of the fact that performing a swap can introduce a new out-of-order adjacent pair only right before or after the two swapped elements. It does not assume that elements forward of the current position are sorted, so it only needs to check the position directly before the swapped elements.
地精算法總是發現第一個 【兩個相鄰元素存在錯誤的順序】，然后把他們交換。原理是，交換一對亂序元素后，會產生一對新的無序相鄰元素，而這兩個元素要么交換前有序，要么交換后有序。它不認為元素當前的位置是有序的，所以它只需要在交換元素前直接檢查位置。
public IList GnomeSort(IList arrayToSort)
{
int pos = 1;
while (pos = 0)
{
pos++;
}
else
{
object temp = arrayToSort[pos];
arrayToSort[pos] = arrayToSort[pos - 1];
RedrawItem(pos);
arrayToSort[pos - 1] = temp;
RedrawItem(pos - 1);
RefreshPanel(pnlSamples);
if (savePicture)
SavePicture();
if (pos > 1)
{
pos--;
}
}
}
return arrayToSort;
}</pre>
| Worst case performance: |
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1)</td>
</tr>
</tbody>
</table>
堆排序是從數據集構建一個數據堆，然后提取最大元素，把它放到部分有序的數組的末尾。提取最大元素后，重新構建新堆，然后又接著提取新堆這的最大元素。重復這個過程，直到堆中沒有元素并且數組已排好。堆排序的基本實現需要兩個數組：一個用于構建堆，另一個是存放有序的元素。
堆排序把輸入數組插入到一個二叉堆的數據結構中。最大值（大根堆）或最小值（小根堆）會被提取出來，直到堆空為止，提取出來的元素，是已經排好序的。每次提取后，堆中沒變換的元素依然保留了，所以（堆排序的）唯一消耗就是提取過程。
在提取過程中，所需要的空間，就是用于存放堆的空間。為了實現恒定的空間開銷，堆是存儲在輸入數組中還沒有完成排序的那部分空間中。堆排序使用了兩個堆操作：插入和根刪除。每個提取的元素放到數組的最后一個空位置。數組剩余位置存放待排元素。
public IList HeapSort(IList list)
{
for (int i = (list.Count - 1) / 2; i >= 0; i--)
Adjust(list, i, list.Count - 1);
for (int i = list.Count - 1; i >= 1; i--)
{
object Temp = list[0];
list[0] = list[i];
list[i] = Temp;
RedrawItem(0);
RedrawItem(i);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
Adjust(list, 0, i - 1);
}
return list;
}
public void Adjust(IList list, int i, int m)
{
object Temp = list[i];
int j = i * 2 + 1;
while (j <= m)
{
if (j < m)
if (((IComparable)list[j]).CompareTo(list[j + 1]) < 0)
j = j + 1;
if (((IComparable)Temp).CompareTo(list[j]) < 0)
{
list[i] = list[j];
RedrawItem(i);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
i = j;
j = 2 * i + 1;
}
else
{
j = m + 1;
}
}
list[i] = Temp;
RedrawItem(i);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}</pre>
| Worst case performance: |
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1)</td>
</tr>
</tbody>
</table>
插入排序的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
具體算法描述如下：
- 從第一個元素開始，該元素可以認為已經被排序
- 取出下一個元素，在已經排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟2~5
public IList InsertionSort(IList arrayToSort)
{
for (int i = 1; i < arrayToSort.Count; i++)
{
object val = arrayToSort[i];
int j = i - 1;
bool done = false;
do
{
if (((IComparable)arrayToSort[j]).CompareTo(val) > 0)
{
arrayToSort[j + 1] = arrayToSort[j];
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
j--;
if (j < 0)
{
done = true;
}
}
else
{
done = true;
}
} while (!done);
arrayToSort[j + 1] = val;
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
return arrayToSort;
}</pre>
| Worst case performance: |
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>O(n)</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1)</td>
</tr>
</tbody>
</table>
從概念上講，歸并排序的工作原理如下：
- 如果列表的長度是0或1，那么它已經有序。否則：
- 未排序的部分平均劃分為兩個子序列。
- 每個子序列，遞歸使用歸并排序。
- 合并兩個子列表，使之整體有序。
歸并排序包含兩個主要觀點，以改善其運行時：
- 一個小列表排序的花費少于大列表。
- 把兩個有序表合并，要比直接排列一個無序表花費更少的步驟。例如，您只需要遍歷每個有序列表一次即可(見下面的合并功能)。
歸并操作的過程如下：
- 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
- 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
- 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
- 重復步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接復制到合并序列尾
public IList MergeSort(IList a, int low, int height)
{
int l = low;
int h = height;
if (l >= h)
{
return a;
}
int mid = (l + h) / 2;
MergeSort(a, l, mid);
MergeSort(a, mid + 1, h);
int end_lo = mid;
int start_hi = mid + 1;
while ((l <= end_lo) && (start_hi <= h))
{
if (((IComparable)a[l]).CompareTo(a[start_hi]) < 0)
{
l++;
}
else
{
object temp = a[start_hi];
for (int k = start_hi - 1; k >= l; k--)
{
a[k + 1] = a[k];
RedrawItem(k + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
a[l] = temp;
RedrawItem(l);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
l++;
end_lo++;
start_hi++;
}
}
return a;
}</pre>
| Worst case performance: |
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td><br />
</td>
</tr>
</tbody>
</table>
奇偶排序
Odd-even sort is a relatively simple sorting algorithm. It is a comparison sort based on bubble sort with which it shares many characteristics. It functions by comparing all (odd, even)-indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for (even, odd)-indexed pairs (of adjacent elements). Then it alternates between (odd, even) and (even, odd) steps until the list is sorted. It can be thought of as using parallel processors, each using bubble sort but starting at different points in the list (all odd indices for the first step). This sorting algorithm is only marginally more difficult than bubble sort to implement.
奇偶排序是一個相對簡單的排序算法。它是一種基于冒泡排序的比較算法，它們有著許多共同點。它通過比較所有相鄰的(奇數偶)對進行排序，如果某對存在錯誤的順序(第一個元素大于第二個)，則交換。下一步針對｛偶奇對｝重復這一操作。然后序列就在(奇，偶)和(偶，奇)之間變換，直到列表有序。它可以看作是是使用并行處理器，每個都用了冒泡排序，但只是起始點在列表的不同位置(所有奇數位置可做第一步)。這個排序算法實現起來只是略微比冒泡排序復雜一些。
public IList OddEvenSort(IList arrayToSort)
{
bool sorted = false;
while (!sorted)
{
sorted = true;
for (var i = 1; i < arrayToSort.Count - 1; i += 2)
{
if (((IComparable)arrayToSort[i]).CompareTo(arrayToSort[i + 1]) > 0)
{
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[i + 1];
RedrawItem(i);
arrayToSort[i + 1] = temp;
RedrawItem(i+1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
sorted = false;
}
}
for (var i = 0; i < arrayToSort.Count - 1; i += 2)
{
if (((IComparable)arrayToSort[i]).CompareTo(arrayToSort[i + 1]) > 0)
{
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[i + 1];
arrayToSort[i + 1] = temp;
RedrawItem(i);
RedrawItem(i+1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
sorted = false;
}
}
}
return arrayToSort;
}</pre>
鴿巢排序，也被稱為 count sort （不要和 counting sort 搞混了），當數組元素的元素數量（n）和可能的鍵值數（key value，N）大約相同時，這種排序算法實用。它的時間復雜度為O(n+N)。
（在不可避免遍歷每一個元素并且排序的情況下效率最好的一種排序算法。但它只有在差值(或者可被映射在差值)很小的范圍內的數值排序的情況下實用。）
算法流程如下：
- Given an array of values to be sorted, set up an auxiliary array of initially empty “pigeonholes”, one pigeonhole for each key through the range of the original array. 假設有個一個待排序的數組，給它建立了一個空的輔助數組（稱為“鴿巢”）。把原始數組中的每個值作為一個key(“格子”)。
- Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key. 遍歷原始數組，根據每個值放入輔助數組對應的“格子”
- Iterate over the pigeonhole array in order, and put elements from non-empty pigeonholes back into the original array. 順序遍歷“鴿巢”數組（輔助數組），把非空鴿巢中的元素放回原始數組。
public IList PigeonHoleSort(IList list)
{
object min = list[0], max = list[0];
foreach (object x in list)
{
if (((IComparable)min).CompareTo(x) > 0)
{
min = x;
}
if (((IComparable)max).CompareTo(x) < 0)
{
max = x;
}
Thread.Sleep(speed);
}
int size = (int)max - (int)min + 1;
int[] holes = new int[size];
foreach (int x in list)
holes[x - (int)min]++;
int i = 0;
for (int count = 0; count < size; count++)
while (holes[count]-- > 0)
{
list[i] = count + (int)min;
RedrawItem(i);
i++;
RefreshPanel(pnlSamples);
Thread.Sleep(speed);
}
return list;
}</pre>
| Worst case performance: |
<td>O(n+2<sup>k</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n+2<sup>k</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(2<sup>k</sup>)</td>
</tr>
</tbody>
</table>
快速排序采用分而治之的策略，把一個列表劃分為兩個子列表。步驟是：
- 從列表中，選擇一個元素，稱為基準（pivot）。
- 重新排序列表，把所有數值小于樞軸的元素排到基準之前，所有數值大于基準的排基準之后(相等的值可以有較多的選擇)。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
- 分別遞歸排序較大元素的子列表和較小的元素的子列表。
遞歸的結束條件是列表元素為零或一個，即已不需要排序。
public IList QuickSort(IList a, int left, int right)
{
int i = left;
int j = right;
double pivotValue = ((left + right) / 2);
int x = (int)a[int.Parse(pivotValue.ToString())];
while (i <= j)
{
while (((IComparable)a[i]).CompareTo(x) < 0)
{
i++;
}
while (((IComparable)x).CompareTo(a[j]) < 0)
{
j--;
}
if (i <= j)
{
object temp = a[i];
a[i] = a[j];
RedrawItem(i);
i++;
a[j] = temp;
RedrawItem(j);
j--;
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
if (left < j)
{
QuickSort(a, left, j);
}
if (i < right)
{
QuickSort(a, i, right);
}
return a;
}</pre>
| Worst case performance: |
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n log n)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(log n)</td>
</tr>
</tbody>
</table>
使用冒泡的快速排序
public IList BubbleSort(IList arrayToSort, int left, int right)
{
for (int i = left; i < right; i++)
{
for (int j = right; j > i; j--)
{
if (((IComparable)arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
{
object temp = arrayToSort[j - 1];
arrayToSort[j - 1] = arrayToSort[j];
RedrawItem(j-1);
arrayToSort[j] = temp;
RedrawItem(j);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
}
return arrayToSort;
}
public IList QuickSortWithBubbleSort(IList a, int left, int right)
{
int i = left;
int j = right;
if (right - left <= 6)
{
BubbleSort(a, left, right);
return a;
}
double pivotValue = ((left + right) / 2);
int x = (int)a[int.Parse(pivotValue.ToString())];
a[(left + right) / 2] = a[right];
a[right] = x;
RedrawItem(right);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
while (i <= j)
{
while (((IComparable)a[i]).CompareTo(x) < 0)
{
i++;
}
while (((IComparable)x).CompareTo(a[j]) < 0)
{
j--;
}
if (i <= j)
{
object temp = a[i];
a[i++] = a[j];
RedrawItem(i - 1);
a[j--] = temp;
RedrawItem(j + 1);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
}
if (left < j)
{
QuickSortWithBubbleSort(a, left, j);
}
if (i < right)
{
QuickSortWithBubbleSort(a, i, right);
}
return a;
}</pre>
原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
算法過程如下：
- 找到列表中的最小值，
- 把它和第一個位置的元素交換，
- 列表其余部分重復上面的步驟(從第二個位置開始，且每次加1).
列表被有效地分為兩個部分：從左到右的有序部分，和余下待排序部分。
public IList SelectionSort(IList arrayToSort)
{
int min;
for (int i = 0; i < arrayToSort.Count; i++)
{
min = i;
for (int j = i + 1; j < arrayToSort.Count; j++)
{
if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[min]) < 0)
{
min = j;
}
}
object temp = arrayToSort[i];
arrayToSort[i] = arrayToSort[min];
arrayToSort[min] = temp;
RedrawItem(i);
RedrawItem(min);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
return arrayToSort;
}</pre>
| Worst case performance: |
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n<sup>2</sup>)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1)</td>
</tr>
</tbody>
</table>
希爾排序
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。
假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用復雜度為O(n2)的排序（冒泡排序或插入排序），可能會進行n次的比較和交換才能將該數據移至正確位置。而希爾排序會用較大的步長移動數據，所以小數據只需進行少數比較和交換即可到正確位置。
一個更好理解的希爾排序實現：將數組列在一個表中并對列排序（用插入排序）。重復這過程，不過每次用更長的列來進行。最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變為：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）。
public IList ShellSort(IList arrayToSort)
{
int i, j, increment;
object temp;
increment = arrayToSort.Count / 2;
while (increment > 0)
{
for (i = 0; i < arrayToSort.Count; i++)
{
j = i;
temp = arrayToSort[i];
while ((j >= increment) &&
(((IComparable)arrayToSort[j - increment]).CompareTo(temp) > 0))
{
arrayToSort[j] = arrayToSort[j - increment];
RedrawItem(j);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
j = j - increment;
}
arrayToSort[j] = temp;
RedrawItem(j);
pnlSamples.Refresh();
if (chkCreateAnimation.Checked)
SavePicture();
}
if (increment == 2)
increment = 1;
else
increment = increment * 5 / 11;
}
return arrayToSort;
}</pre>
| Worst case performance: |
<td>-</td>
</tr>
<tr>
<td align="right"><strong>Best case performance:</strong></td>
<td>n</td>
</tr>
<tr>
<td align="right"><strong>Average case performance:</strong></td>
<td>O(n log<sup>2</sup> n)</td>
</tr>
<tr>
<td align="right"><strong>Worst case space complexity:</strong></td>
<td>O(1)</td>
</tr>
</tbody>
</table>
最后，感謝給與我幫助的人，有了你們的幫助，本文的質量有了更大的提高，謝謝！
原文鏈接： Kanasz Robert 翻譯： 伯樂在線 - smilesisi
譯文鏈接： http://blog.jobbole.com/72850/
本文由用戶
jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
sesese色