前言

本博客插入排序動圖和希爾排序視頻參考大佬java技術愛好者，如有侵權，請聯系刪除。

直接插入排序

基本思想

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
實際中我們玩撲克牌時，就用了插入排序的思想：

當插入第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. 穩定性：穩定

代碼實現

#include<stdio.h>//直接插入排序
//時間復雜度最好為O(N) -- 順序有序,最壞為O(N^2) -- 逆序,空間復雜度為O(1)
void insertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1, tmp = a[i];//單趟排序,[0,end]有序，插入tmpwhile (end >= 0)//從后向前比較{if (a[end] > tmp)a[end + 1] = a[end--];else break;}a[end + 1] = tmp;//兩種情況，a[end]<=tmp以及tmp最小}for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}int main()
{int arr[] = { 1,2,-9,-6,8,9,4,3,0 };insertSort(arr, sizeof(arr) / sizeof(int));return 0;
}

希爾排序

算法思想

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數gap，把待排序文件中所有記錄分成個組，所有距離為gap的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取重復上述分組和排序的工作。當gap==1完成最后的直接插入排序時，所有記錄在統一組內排好序。

特性總結

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優化。
2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些書中給出的希爾排序的時間復雜度都不固定：
   《數據結構(C語言版)》— 嚴蔚敏
   
   《數據結構-用面相對象方法與C++描述》— 殷人昆
   
   因為本人的gap是按照Knuth提出的方式取值的，而且Knuth進行了大量的試驗統計，我們暫時就按照：O(N^1.25)到O(1.6*N^1.25)來算。
4. 穩定性：不穩定

代碼實現

#include<stdio.h>//void shellSort(int* a, int n)
//{
//	//1.預排序 -- 接近有序
//	int gap = 3;
//	for (int i = 0; i < gap; i++)//優化寫法,效率相同
//	{
//		for (int j = i; j < n - gap; j += gap)
//		{
//			int end = j;
//			int tmp = a[end + gap];//記錄需要插入的值
//			while (end >= 0)
//			{
//				if (a[end] > tmp)
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else break;
//			}
//			a[end + gap] = tmp;
//		}
//	}
//}void printArr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void shellSort(int* a, int n)//希爾排序
{//1.預排序 -- 接近有序//2.gap == 1 直接插入排序int gap = n;while (gap > 1){gap = gap / 3 + 1;//+1可以保證最后一次一定是1for (int j = 0; j < n - gap; j++){int end = j;int tmp = a[end + gap];//記錄需要插入的值while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else break;}a[end + gap] = tmp;}}
}int main()
{int arr[] = { 7,1,9,8,0,3,2,5,4,6,10,-1 };printArr(arr, sizeof(arr) / sizeof(int));shellSort(arr, sizeof(arr) / sizeof(int));printArr(arr, sizeof(arr) / sizeof(int));return 0;
}