直接插入排序
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好的序列的有序數(shù)據(jù)中欧啤，從而得到一個(gè)新的褪秀、個(gè)數(shù)加1的有序數(shù)據(jù)怀樟，算法適用于少量數(shù)據(jù)的排序。 ** 時(shí)間復(fù)雜度為O(n^2),是穩(wěn)定的排序方法筑舅。插入算法把要排序的數(shù)組分成兩部分：
第一部分包含了這個(gè)數(shù)組的所有元素座慰，但將最后一個(gè)元素排除(讓數(shù)組多一個(gè)空間才有插入的位置)，而第二部分就只包含一個(gè)元素(即待插入元素)翠拣。在第一部分排序完成后版仔，再將這個(gè)最后元素插入到已排好序的第一部分中。
void insert_sort(int* a, int len) {
for (int i = 1; i < len; ++i) {
int j = i - 1;
int temp = a[i];
while (temp < a[j] && j >= 0) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
希爾排序
也稱(chēng)縮小增量排序误墓，是直接插入排序算法一種更高效的改進(jìn)版本蛮粮。 ** 希爾排序是非穩(wěn)定排序算法。 **
希爾排序是把記錄按下標(biāo)的一定增量分組谜慌，對(duì)每組使用直接插入排序算法排序然想。隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多欣范，當(dāng)增量減至1時(shí)又沾，整個(gè)文件恰被分成一組，算法便終止熙卡。
void shell_sort(int* a, int len) {
int step = len / 2;
int temp;
while (step > 0) {
for (int i = step; i < len; ++i) {
temp = a[i];
int j = i - step;
while (j >= 0 && temp < a[j]) {
a[j + step] = a[j];
j -= step;
}
a[j + step] = temp;
}
step /= 2;
}
}
