一：排序的概念
1.排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
2.穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
3.内部排序：資料元素全部放在記憶體中的排序。
4.外部排序：資料元素太多不能同時放在記憶體中，根據排序過程的要求不能在内外存之間移動資料的排序。
二：常見的排序方法：
三：各種排序算法的實作原理：`
（1）插入排序的基本思想：
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
**
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即将array[i]插入，原來位置上的元素順序後移。
直接插入排序的特性總結：
- 元素集合越接近有序，直接插入排序算法的時間效率越高
- 時間複雜度：O(N^2)
- 空間複雜度：O(1)，它是一種穩定的排序算法
- 穩定性：穩定
（2）希爾排序( 縮小增量排序 )
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先標明一個整數，把待排序檔案中所有記錄分成個組，所有距離為的記錄分在同一組内，并對每一組内的記錄進行排序。然後，取，重複上述分組和排序的工作。當到達=1時，所有記錄在統一組内排好序。
希爾排序的特性總結：
- 希爾排序是對直接插入排序的優化。
-
當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就
會很快。這樣整體而言，可以達到優化的效果。我們實作後可以進行性能測試的對比。
- 希爾排序的時間複雜度不好計算，需要進行推導，推導出來平均時間複雜度： O(N^1.3—N^2）
- 穩定性：不穩定
（3） 選擇排序
基本思想：
每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的
資料元素排完 。
直接選擇排序:
在元素集合array[i]--array[n-1]中選擇關鍵碼最大(小)的資料元素
若它不是這組元素中的最後一個(第一個)元素，則将它與這組元素中的最後一個（第一個）元素交換
在剩餘的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重複上述步驟，直到集合剩餘1個元素
直接選擇排序的特性總結：
- 直接選擇排序思考非常好了解，但是效率不是很好。實際中很少使用
- 空間複雜度：O(1)
（4）堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇資料。需要注意的是排升序要建大堆，排降序建小堆。
堆排序使用堆來選數，效率就高了很多。
- 時間複雜度：O(N*logN)
（5）冒泡排序
基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：将鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
冒泡排序的特性總結：
- 冒泡排序是一種非常容易了解的排序
- 快速排序整體的綜合性能和使用場景都是比較好的，是以才敢叫快速排序
- 空間複雜度：O(logN)
- 歸并的缺點在于需要O(N)的空間複雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
- 空間複雜度：O(N)