看了幾天的排序內容，現在和大家分享一些常見的排序方法。
啥是排序？
個人理解的排序：通過對數組中的值進行對比，交換位置最終得到一個有序的數組。排序分為內存排序和外部排序。本次分享排序方法都為內存排序。
啥是排序的穩定性？
假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序後的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
常見排序：
冒泡排序，選擇排序，直接插入排序，希爾排序，堆排序，歸並排序，快速排序。
來張圖展示一下種排序的關系：
排序思想：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。
復雜度：O(n^2)。
穩定性：穩定。
冒泡排序是我最早接觸的排序算法，理解起來比較簡單。排序入門級，容易理解，通過不斷交換位置來排序。
代碼實例：
int[] list = { 50, 10, 90, 30, 70, 40, 20 };
int temp;
for (int i = 0; i < list.Length; i++)
{
for (int j = i + 1; j < list.Length; j++)
{
if (list[i] > list[j])
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
}
Console.WriteLine("冒泡排序的結果:{0}", string.Join(",", list));
第一個for循環取數據中一個值list[i]，第二個for循環已第一個for循環中的下一個值(j=i+1)開始取值list[j]。然後依次對比兩值的大小list[i] > list[j]，如果數組中前面的值大於後面的值，替換他兩的位置。始終保持數組中左邊的值小於右邊的值。
冒泡排序還有其他很多版本這裡就不一一分享。
排序思想：每一趟在n-i+1（i=1，2，…n-1）個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。
復雜度：O(n^2)。
穩定性：穩定。
代碼實例：
int[] list = { 50, 10, 90, 30, 70, 40, 20 };
int minIndex, temp;
for (int i = 0; i < list.Length; i++)
{
minIndex = i; /*把當前循環的值認為是最小值*/
for (int j = i + 1; j < list.Length; j++)
{
if (list[j] < list[minIndex])
{
minIndex = j; /*進過N次循環我們找到最小值並賦值給minIndex*/
}
}
if (minIndex!=i)
{
temp = list[minIndex]; /*把當前循環出的最小值和list[i]替換。實現左邊數據比右邊數據要小*/
list[minIndex] = list[i];
list[i] = temp;
}
}
Console.WriteLine("選擇排序的結果:{0}", string.Join(",", list));
第一個for循環數組中元素list[i],把當前循環的值默認為是最小值。記錄下標賦值給minIndex。第二個for循環已第一個for循環中的下一個值(j=i+1)開始取值list[j]。然後依次和list[minIndex]對比，如果list[j]<list[minIndex]把循環中j的下標賦值給minIndex(保持minIndex為循環中最小值的下標)。到第二個for循環結束，然後替換當前循環的值list[i]和list[minIndex]的位置。始終保持數組中左邊的值小於右邊的值。
選擇排序相對冒泡排序交換位置次數少，排序性能略優冒泡排序。
排序思想：
每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。
第一趟比較前兩個數，然後把第二個數按大小插入到有序表中；
第二趟把第三個數據與前兩個數從前向後掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。
復雜度：O(n^2)。
穩定性：穩定。
代碼實例：
int[] list = { 50, 10, 90, 30, 70, 40, 20 };
int temp, j;
for (int i = 1; i < list.Length; i++) /*從數據第二位開始循環 [無序序列] */
{
if (list[i] < list[i - 1])
{
temp = list[i];
for (j = i - 1; j >= 0 && temp < list[j]; j--) /*[有序序列] */
{
list[j + 1] = list[j];
}
list[j + 1] = temp;
}
}
Console.WriteLine("直接插入排序的結果:{0}", string.Join(",", list));
第一個for循環(從數組第二位置開始循環)數組中元素list[i]，如果循環的當前值list[i]比數組中上一個值list[i-1]要小,聲明臨時變量temp記錄list[i]。然後根據第一個for循環的i值，反向循環數組,查詢小於list[i]的下標位置。然後替換list[j+1]的值。
