1 插入排序
1.1基本思想：
直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。
1.2直接插入排序：
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高2. 時(shí)間復(fù)雜度：O(N^2)3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法4. 穩(wěn)定性：穩(wěn)定
?寫排序算法的一種好習(xí)慣就是先寫一個(gè)單趟排序，再使用循環(huán)來實(shí)現(xiàn)整體。假設(shè)實(shí)現(xiàn)一個(gè)升序，首先創(chuàng)建一個(gè)變量end=0，然后tmp保存a[end+1]的值，寫一個(gè)while循環(huán)，結(jié)束條件是end<0，進(jìn)入循環(huán)判斷tmp和a[end]的大小，如果tmp小則將a[end]的值覆蓋到a[end+1]，然后end--，跳出循環(huán)，此時(shí)將tmp插入到a[end+1]也就是a[0]這個(gè)位置。如果tmp>=a[end]，直接退出循環(huán)。然后將tmp的值插入到a[end+1]這個(gè)位置。然后最外層套一層循環(huán)，每次單趟結(jié)束后end++。
// 插入排序
void InsertSort(int* a, int n)
{
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 + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = tmp;
}
}2.希爾排序( 縮小增量排序 )
void ShellSort1(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
}當(dāng)然也可以在單趟外只套一層循環(huán)，巧妙地控制i。
void ShellSort2(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap = gap / 2;
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}1. 希爾排序是對(duì)直接插入排序的優(yōu)化。2. 當(dāng) gap > 1 時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng) gap == 1 時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就 會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測試的對(duì)比。3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)?/span> gap 的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的 希爾排序的時(shí)間復(fù)雜度都不固定。
4. 穩(wěn)定性：不穩(wěn)定 ?。文章來源：http://www.zghlxwxcb.cn/news/detail-754099.html
今天的分享到這里就結(jié)束了，感謝大家的閱讀！文章來源地址http://www.zghlxwxcb.cn/news/detail-754099.html
到了這里，關(guān)于排序算法-插入/希爾排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
