1 插入排序

1.1基本思想：

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

1.2直接插入排序：

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

1. 元素集合越接近有序，直接插入排序算法的時間效率越高

2. 時間復雜度：O(N^2)

3. 空間復雜度：O(1)，它是一種穩定的排序算法

4. 穩定性：穩定

?寫排序算法的一種好習慣就是先寫一個單趟排序，再使用循環來實現整體。假設實現一個升序，首先創建一個變量end=0，然后tmp保存a[end+1]的值，寫一個while循環，結束條件是end<0，進入循環判斷tmp和a[end]的大小，如果tmp小則將a[end]的值覆蓋到a[end+1]，然后end--，跳出循環，此時將tmp插入到a[end+1]也就是a[0]這個位置。如果tmp>=a[end]，直接退出循環。然后將tmp的值插入到a[end+1]這個位置。然后最外層套一層循環，每次單趟結束后end++。

// 插入排序
void InsertSort(int* a, int n)
{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 + 1] = a[end];}else{break;}end--;}a[end + 1] = tmp;}
}

2.希爾排序( 縮小增量排序 )

void ShellSort1(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}
}

void ShellSort2(int* a, int n)
{int gap = n;while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

4. 穩定性：不穩定 ?。

今天的分享到這里就結束了，感謝大家的閱讀！