資料結構中插入排序的了解

一·插入排序：

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

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

void InsertSort(int *arr,int size)
{//升序
    //assert(arr);
	int i=0;
	int key=0;
	int j=0;
    for(i=1;i<size;i++)
	{
		key=arr[i];
		j=i-1;
		while(j>=0&&key<arr[j])
		{
		  arr[j+1]=arr[j];
		  j--;
		}
		
		arr[j+1]=key;
	}
	
}
           

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

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

4. 穩定性：穩定

   希爾排序也是插入排序(一種優化的插入排序)，其基本思想：先標明一個整數gap，把待排序檔案中所有記錄分成gap個組，所有距離為gap的記錄分在同一組内，并對每一組内的記錄進行排序。然後，取gap–(讓gap減小的表達式)，重複上述分組和排序的工作。當到達gap=1時，所有記錄在統一組内排好序。

   

void ShellSort(int * arr,int size)
{
  int gap=size/3+1;
  int i=0;
  while(gap>0)
  {
  for(i=0;i<size;i++)
  {
     if(i+gap<size&&arr[i]>arr[i+gap])
		 swap(&arr[i],&arr[i+gap]);//swap函數隻做兩個數的交換，這裡不展示代碼
  }
    gap--;
  }
}
           

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優化。
2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。我們實作後可以進行性能測試的對比。
3. 希爾排序的時間複雜度不好計算，推導出來平均時間複雜度： O(N^1.3—— N^2）
4. 穩定性：不穩定