常見排序算法的實現(xiàn)

插入排序基本思想：

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

直接插入排序

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

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]復(fù)制覆蓋到后一位，tmp保存被覆蓋的值
? ? ? ? ? ? {
? ? ? ? ? ? ? ? a[end + 1] = a[end];
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }

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

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

直接插入排序的特性總結(jié)：

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

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

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