1.直接插入排序
直接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中的適當位置，直到全部記錄插入完成為止。
設數組為a[0…n-1]。
1. 初始時，a[0]自成1個有序區，無序區為a[1..n-1]。令i=1
2. 將a[i]并入當前的有序區a[0…i-1]中形成a[0…i]的有序區間。
3. i++并重復第二步直到i==n-1。排序完成。
代碼如下：
void InsertSort(int* a, size_t n) //直接插入排序
{
assert(a);
for (int i = 1; i < n; ++i)
{
int tmp = a[i];
int j = i - 1;
while (j >= 0 && a[j] > tmp)
{
a[j + 1] = a[j];
--j;
}
a[j + 1] = tmp;
}
}2.希爾排序
該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。
void shellsort2(int a[], int n)
{
int j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (j = gap; j < n; j++)//從數組第gap個元素開始
if (a[j] < a[j - gap])//每個元素與自己組內的數據進行直接插入排序
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
