直接插入排序

插入排序（insert sort）是一種簡單的排序算法，它的工作原理與手動整理一副牌的過程非常相似。

具體來說，我們在未排序區間選擇一個基準元素，將該元素與其左側已排序區間的元素逐一比較大小，并將該元素插入到正確的位置。

代碼示例

void insert_sort(int* arr,int n)
{for (int i = 0; i < n - 1; ++i){//將end+1的數據插入到[0.end]的有序區間int end = i;int tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

性能分析

• 時間復雜N^2)
• 空間復雜度:O(1)

希爾排序

希爾排序(Shell Sort)是插入排序的一種，它是針對直接插入排序算法的改進。

希爾排序又稱縮小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通過比較相距一定間隔的元素來進行，各趟比較所用的距離隨著算法的進行而減小，直到只比較相鄰元素的最后一趟排序為止。

代碼示例

void shell_sort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//保證最后一次 gap==1//多組并排for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

性能分析

• 時間復雜度不好計算，需要進行推導，推導出來平均時間復雜度： O(N^1.3— N^2）
• 空間復雜度：O(1)