直接插入排序 希尔排序
直接插入排序：
对数组 int arr1[] ={1,4,2,7,9,8,3,6};
第一个元素看作有序，后面元素看作无序：
【1】4 2 7 9 8 3 6
插入过程
【】内表示有序，按照从小到大排序
【1 4】 2 7 9 8 3 6 每次插入一个元素，插入4
【1 2 4】 7 9 8 3 6 插入2，2与4比较，2比4小，交换2和4
【1 2 4 7】 9 8 3 6
【1 2 4 7 9】 8 3 6
【1 2 4 7 8 9】 3 6 插入8，8比9小，交换8和9
【1 2 3 4 7 8 9】 6 插入3， 3和 9 交换，3和8交换， 3和7交换， 3和4交换
【1 2 3 4 6 7 8 9】
插入排序时间复杂度 最好 O（n） 最坏 O（n^2）
希尔排序：
由于直接插入排序插入到后面，有序元素越来越多，插入时间越来越多，希尔对这种算法改良，让元素分组进行插入排序
定义步长gap = n/2 ; gap<n;gap/=2
对数组 int arr1[] ={1,4,2,7,9,8,3,6};
一开始 【1，9】【4，8】【2，3】【7，6】四组，组内进行排序，只有7和6要交换
接下来分成 gap=n/2/2=2 组 【1，2，9，3】【4，6，8，7】（注意交换过了）两组，进行组内排序
直到gap = 1.
关于希尔排序 increment（增量）的取法。 增量increment的取法有各种方案。最初shell提出取increment=n/2向下取整，increment=increment/2向下取整，直到increment=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取increment=n/3向下取整+1.还有人提出都取奇数为好，也有人提出increment互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。 （参考razor_edge）
#include <bits/stdc++.h>
using namespace std;
void swap(int &a,int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void Insert_sort(int *arr1,int n)
{
for(int i=1;i<n;i++)
{
int j = i;
while( j-1>=0&&(*(arr1+j)<*(arr1+j-1)) )
{
swap( *(arr1+j),*(arr1+j-1) );
j--;
}
}
}
void Shell_sort(int *arr2,int n)
{
for(int gap = n/2;gap>0;gap/=2)//增量gap , 逐步减小gap
{
for(int i=gap;i<n;i++)
{
int j = i ;
while( j-gap>=0 &&*(arr2+j)<*(arr2+j-gap) )
{
swap( *(arr2+j), *(arr2+j-gap) );
j-=gap;
}
}
}
}
int main()
{
int arr1[] ={1,4,2,7,9,8,3,6};
Insert_sort(arr1,8);
printf("Insert_sort:\n");
for(int i = 0; i < 8; i++)
{
printf("%d ",arr1[i]);
}
int arr2[] ={1,4,2,7,9,8,3,6};
Shell_sort(arr2,8);
printf("\nShell_sort:\n");
for(int i = 0; i < 8; i++)
{
printf("%d ",arr2[i]);
}
return 0;
} 腾讯云开发者
