排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次
序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排
序算法是穩定的；否則稱為不穩定的。兩個數相等時，第一個數排序前在另外一個數之前，拍完序之后還在另外一個數之前。

內部排序：數據元素全部放在內存中的排序。

外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

常見的幾大類排序

基數排序，數據約束比較明顯，這七種排序比較通用

插入類排序

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一
個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

每次遍歷到一個數，找到前面小于等于它時候的位置

			因為前面已經排好的全部時有序數列，最大的數已經時有序數列中最后的那個數如果正好和前一個數相等或者大于前一個數，則直接end+1回到待排序數的下標，等于keyi跳到下一個數繼續判斷如果小于的話，往后移動，則從end下標開始，遍歷整個有序數列，找到key>某個數的時候，直接讓end+1=key，原來的end+1位置的數已經移動到end+2位置所以直接讓直接讓end+1=key，完成插入，如果end=-1表示，有序數列中最小的數都比key小，則end+1下標回到0，數組第一個元素的位置就是key

希爾排序為了解決直接插入排序的一些缺點，希爾排序，通過分組的方法，讓數據在每次進行直接插入排序的時候都是接近有序的。對直接插入排序進行更改。

以前直接插入時，end+1，其實就是希爾排序中分組間隔為一時候的情況
現在，有分組間隔，所以每回在組內搬運元素，每回end+分組間隔gap就行每個小組排完序后數組接近有序，分組間隔減一，再排序，最后一次插入排序，整個數組接近有序
最后一次插入排序，整個數組接近有序，直接插入最快