傳回
排序
比較排序常見的快速排序、歸并排序、堆排序、冒泡排序；在排序結果中，元素之間的次序依賴于它們之間的比較，每個數都必須和其他數進行比較，才能确定自己的位置。
非比較排序常見的計數排序、基數排序、桶排序；通過确定每個元素之前應該有多少個元素來排序，針對數組arr，計算arr[i]之前有多少個元素，則唯一确定了arr[i]在排序後數組中的位置。
對比非比較排序時間複雜度低，但由于非比較排序需要占用空間來确定唯一位置，是以對資料規模和資料分布有一定的要求。
冒泡排序比較相鄰的元素，如果前一個比後一個大，就交換他們兩個。數值大的元素放到後面。一趟循環能确定未排序的數組中的最大值（大的元素往後縮）
1 public static int[] GetOrderArr(int[] arr)
2 {
3 if (arr.Length == 0) return arr;
4 for(var i = 0; i < arr.Length; i++)
5 {
6 for(var j = 0; j < arr.Length - 1 - i; j++)
7 {
8 var current = arr[j];
9 var next = arr[j + 1];
10 if (current > next)
11 {
12 var temp = arr[j];
13 current = next;
14 next = temp;
15 arr[j] = current;
16 arr[j + 1] = next;
17 }
18 }
19 }
20 return arr;
21 } 示例代碼
選擇排序最穩定的排序算法，首先在未排序數組中找到最小（大）的元素下标，存在到排序數組的起始位置，然後在從未排序的數組中繼續找最小（大）元素下标，然後存放到已排序數組的末尾，以此類推。。。
1 public static int[] GetOrderArr(int[] arr)
2 {
3 if (arr.Length == 0) return arr;
4 for (var i = 0; i < arr.Length; i++)
5 {
6 var minIndex = i;
7 for (var j = i; j < arr.Length; j++)
8 if (arr[j] < arr[minIndex])
9 minIndex = j;
10 var temp = arr[i];
11 arr[i] = arr[minIndex];
12 arr[minIndex] = temp;
13 }
14 return arr;
15 } 示例代碼
插入排序從第一個元素開始，該元素可以認為是已排序，取未排序數組的第一個元素和已排序的數組元素從後到前逐個比較，如果該元素小于已排序數組元素，則調換位置，直到該元素大于已排序數組元素，以此類推。。。（把未排序數組第一個元素作為已排序數組最後一個元素，用該元素向前逐一比較大小）
1 public static int[] GetOrderArr(int[] arr)
2 {
3 if (arr.Length == 0) return arr;
4 for (var i = 1; i < arr.Length; i++)
5 {
6 //arr[i]是未排序數組的第一個元素，可作為已排序數組的最後一個元素，将該元素向前逐一比較
7 for (var j = i; j > 0; j--)
8 {
9 if (arr[j] < arr[j - 1])
10 {
11 var temp = arr[j];
12 arr[j] = arr[j - 1];
13 arr[j - 1] = temp;
14 }
15 }
16 }
17 return arr;
18 } 示例代碼
希爾排序希爾排序（縮小增量排序）也是一種插入排序，更高效的插入排序算法（未能了解，因為最後一次還要進行一次全新的插入排序，還不如直接進行插入排序呢）；對原始數組進行分組（分組數是arr.length/2/2/2...，直到分組為1時，不要求arr.length必須是偶數，因為最後還要進行一次插入排序），對分組内元素進行插入排序。？？？
1 public static int[] GetOrderArr(int[] arr)
2 {
3 if (arr.Length == 0) return arr;
4 //擷取初始增量(分組數)
5 var gap = arr.Length / 2;
6 //分組規則：第gap個元素和第gap-gap個元素比較或反過來比較
7 while (gap > 0)
8 {
9 //循環增量(分組數)次
10 for (var i = gap; i < arr.Length; i++)
11 {
12 //對每組元素進行插入排序
13 for (var j = i; j > 0; j--)
14 {
15 if (arr[j] < arr[j - 1])
16 {
17 var temp = arr[j];
18 arr[j] = arr[j - 1];
19 arr[j - 1] = temp;
20 }
21 }
22 }
23 //增量減半
24 gap /= 2;
25 }
26 return arr;
27 } 示例代碼
歸并排序是利用歸并的思想實作的排序方法，該算法采用經典的分治政策（分治法将問題分成一些小的問題然後遞歸求解，而治的階段則将分的階段得到的各答案“修補”在一起，即分而治之）
1 public static int[] GetOrderArr(int[] arr)
2 {
3 var length = arr.Length;
4 if (length < 2) return arr;
5 var leftLength = length / 2;
6 var rightLength = length - leftLength;
7 int[] left = new int[leftLength];
8 int[] right = new int[rightLength];
9 for (var i = 0; i < length; i++)
10 {
11 if (i < leftLength)
12 left[i] = arr[i];
13 else
14 right[i - leftLength] = arr[i];
15 }
16 var result = Merge(GetOrderArr(left), GetOrderArr(right));
17 return result;
18 }
19
20 public static int[] Merge(int[] left, int[] right)
21 {
22 int[] result = new int[left.Length + right.Length];
23 var i = 0;
24 var j = 0;
25 for (int index = 0; index < result.Length; index++)
26 {
27 if (i >= left.Length)
28 result[index] = right[j++];
29 else if (j >= right.Length)
30 result[index] = left[i++];
31 else if (left[i] > right[j])
32 result[index] = right[j++];
33 else
34 result[index] = left[i++];
35 }
36 return result;
37 } 示例代碼
快速排序通過一趟排序将待排記錄分隔成獨立的兩部分，其中一份記錄的關鍵字均比另一部分的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序（從數列中挑出一個元素，稱為“基準”、重新排序 數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值到的擺在基準的後面，這個分區退出之後，該基準就處于數列的中間位置，這個稱為分區操作；遞歸的把小于基準值元素的子數列和大于基準值元素的子數列排序）。
1 /// <summary>
2 /// 快速排序
3 /// </summary>
4 /// <param name="array"></param>
5 /// <param name="low">第一次是0</param>
6 /// <param name="high">第一次是array.length-1</param>
7 public static void sort(int[] array, int low, int high)
8 {
9 if (low >= high)
10 return;
11 /*完成一次單元排序*/
12 int index = sortUnit(array, low, high);
13 /*對左邊單元進行排序*/
14 sort(array, low, index - 1);
15 /*對右邊單元進行排序*/
16 sort(array, index + 1, high);
17 }
18 private static int sortUnit(int[] array, int low, int high)
19 {
20 int key = array[low];
21 while (low < high)
22 {
23 /*從後向前搜尋比key小的值*/
24 while (array[high] >= key && high > low)
25 --high;
26 /*比key小的放左邊*/
27 array[low] = array[high];
28 /*從前向後搜尋比key大的值，比key大的放右邊*/
29 while (array[low] <= key && high > low)
30 ++low;
31 /*比key大的放右邊*/
32 array[high] = array[low];
33 }
34 /*左邊都比key小，右邊都比key大。//将key放在遊标目前位置。//此時low等于high */
35 array[low] = key;
36 return high;
37 } 示例代碼
堆排序堆排序是指利用堆這種資料結構所涉及的一種排序算法，堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子節點的鍵值或索引總是小于（或大于）它的父節點。
計數排序計數排序的核心在于将輸入的數值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間複雜度的排序，基數排序要求輸入的資料必須是有确定範圍的整數。計數排序是一種穩定的排序算法，計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等于i的元素的個數。然後根據資料C來将A中的元素排到正确的位置。它隻能對整數進行排序。
找出待排序的數組中最大和最小是元素；統計數組中每個值為i的元素出現的次數，存入數組C的第i項；對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；方向填充沒押镖數組，将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1。
1 public static int[] CountingSort(int[] array)
2 {
3 if (array.Length == 0) return array;
4 int bias, min = array[0], max = array[0];
5 //擷取數組中最大值和最小值
6 for (var a = 1; a < array.Length; a++)
7 {
8 if (array[a] > max)
9 max = array[a];
10 if (array[a] < min)
11 min = array[a];
12 }
13 bias = 0 - min;
14 //建立最大值和最小值區間大小的數組
15 int[] bucket = new int[max - min + 1];
16 //計算每個元素出現的次數
17 for (int j = 0; j < array.Length; j++)
18 bucket[array[j] + bias]++;
19 int index = 0, i = 0;
20 //回填資料組成有序數組
21 while (index < array.Length)
22 {
23 if (bucket[i] != 0)
24 {
25 array[index] = i - bias;
26 bucket[i]--;
27 index++;
28 }
29 else
30 i++;
31 }
32 return array;
33 } 示例代碼
桶排序桶排序是計數排序的更新版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的确定。工作的原理：假設輸入資料服從均勻分布，将資料分到有限數量的桶裡，每個桶再分别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排。
算法描述：
- 人為設定一個BucketSize，作為每個桶所能放置多少個不同數值（例如當BucketSize==5時，該桶可以存放｛1,2,3,4,5｝這幾種數字，但是容量不限，即可以存放100個3）；
- 周遊輸入資料，并且把資料一個一個放到對應的桶裡去；
- 對每個不是空的桶進行排序，可以使用其它排序方法，也可以遞歸使用桶排序；
- 從不是空的桶裡把排好序的資料拼接起來。
注意，如果遞歸使用桶排序為各個桶排序，則當桶數量為1時要手動減小BucketSize增加下一循環桶的數量，否則會陷入死循環，導緻記憶體溢出。
基數排序基數排序也是非比較的排序算法，對每一位進行排序，從最低位開始排序，複雜度為O(kn),為數組長度，k為數組中的數的最大的位數；基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分别排序，分别收集，是以是穩定的。
算法描述：
- 取得數組中的最大數，并取得位數；
- arr為原始數組，從最低位開始取每個位組成radix數組；
- 對radix進行計數排序（利用計數排序适用于小範圍數的特點）；
分别取出個位數、十位數、百位數進行排序。