常見排序算法的實現

插入排序基本思想：

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

直接插入排序

? ? 當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移
代碼實現：

void InsertSort(int* a, int n) {
? ? // [0,end]有序，把end+1位置的插入到前序序列
? ? // 控制[0,end+1]有序
? ? for (int i = 0; i < n - 1; i++)
? ? {
? ? ? ? int end = i;
? ? ? ? int tmp = a[end + 1];
? ? ? ? while (end >= 0)
? ? ? ? {
? ? ? ? ? ? if (tmp < a[end])//如果小于則將a[end]復制覆蓋到后一位，tmp保存被覆蓋的值
? ? ? ? ? ? {
? ? ? ? ? ? ? ? a[end + 1] = a[end];
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }

? ? ? ? ? ? --end;//每次都往前比較
? ? ? ? }

? ? ? ? a[end + 1] = tmp;//將tmp保存值插入比它小的值的前面一位
? ? }
}

直接插入排序的特性總結：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩定的排序算法
4. 穩定性：穩定
5. 代碼實現

6. void ShellSort(int* a, int n) {
   ? ? int gap = n;
   ? ? while (gap > 1)//當gap<=1則說明已經進行了最后的插入排序
   ? ? {
   ? ? ? ? gap = gap / 3 + 1;//gap每次縮小相應倍數，使得排序越來越接近有序，
   ? ? ? ? //+1使得gap最后一次排序為直接插入排序

   ? ? ? ? for (int i = 0; i < n - gap; ++i)
   ? ? ? ? {
   ? ? ? ? ? ? int end = i;//end為該次排序起始位置下標
   ? ? ? ? ? ? int tmp = a[end + gap];//每次間隔gap個位置進行比較
   ? ? ? ? ? ??
   ? ? ? ? ? ? while (end >= 0)//此處為直接插入思想
   ? ? ? ? ? ? {
   ? ? ? ? ? ? ? ? if (tmp < a[end])
   ? ? ? ? ? ? ? ? {
   ? ? ? ? ? ? ? ? ? ? a[end + gap] = a[end];
   ? ? ? ? ? ? ? ? ? ? end -= gap;
   ? ? ? ? ? ? ? ? }
   ? ? ? ? ? ? ? ? else
   ? ? ? ? ? ? ? ? {
   ? ? ? ? ? ? ? ? ? ? break;
   ? ? ? ? ? ? ? ? }
   ? ? ? ? ? ? }
   ? ? ? ? ? ? //
   ? ? ? ? ? ? a[end + gap] = tmp;
   ? ? ? ? }
   ? ? }
   }希爾排序的特性總結：
   穩定性：不穩定
   希爾排序是對直接插入排序的優化。
   當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這就會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。*
   希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定