插入排序(直接插入排序、希尔排序)

发布时间:2016-12-9 6:31:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"插入排序(直接插入排序、希尔排序)",主要涉及到插入排序(直接插入排序、希尔排序)方面的内容,对于插入排序(直接插入排序、希尔排序)感兴趣的同学可以参考一下。

直接插入排序                       基本思想:      假设待排序的数存放在数组arr[1...n]中。初始时,arr[1]自成1个有序区,无序区为arr[2...n]。从i=2起直至i=n为止,依次将arr[i]插入当前的有序区arr[1..i-1]中,生成含n个记录的有序区。 算法复杂度:      对于具有n个记录的文件,要进行n-1次排序      各种状态下的时间复杂度: ┌─────────┬─────┬──────┬──────┐ │ 初始文件状态     │   正序   │     反序   │无序(平均)  │ ├─────────┼─────┼──────┼──────┤ │ 第i趟的关键      │   1      │     i+1    │ (i-2)/2  │ │ 字比较次数       │          │            │            │ ├─────────┼─────┼──────┼──────┤ │总关键字比较次数  │   n-1    │(n+2)(n-1)/2│ ≈n2/4     │ ├─────────┼─────┼──────┼──────┤ │第i趟记录移动次数 │   0      │ i+2        │ (i-2)/2  │ ├─────────┼─────┼──────┼──────┤ │总的记录移动次数  │   0      │(n-1)(n+4)/2│ ≈n2/4     │ ├─────────┼─────┼──────┼──────┤ │时间复杂度        │  0(n)  │ O(n2)    │ O(n2)    │ 代码: void InsertSort(int *arr,int num) { if(NULL == arr) return; int i,j; for(i = 1;i < num;i++){ if(arr[i] < arr[i-1]){ int temp = arr[i]; for(j = i-1;arr[j] > temp;j--) { arr[j+1] = arr[j]; } arr[j+1] = temp; } } } 希尔排序                                    基本思想       先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;      然后取d2<d1,重复上述分组和排序操作;      直至di=1,即所有记录放进一个组中排序为止      算法复杂度        希尔排序是不稳定的,希尔排序的执行时间依赖于增量序列,其平均时间复杂度为O(n^1.3). 代码 void Shell(int A[],int n) //Shell 排序 { int i,j,k,t; (n/2)%2 == 0 ? k = n/2+1 : k = n/2; // 保证增量为奇数 while(k > 0) { for(j=k;j<n; j++) { //组内进行插入排序 t = A[j]; i = j - k; while(i>=0 && A[i]>t) { A[i+k]=A[i]; i=i-k; } A[i+k]=t; } if(k == 1) break ; (k/2)%2 ==0 ? k=k/2+1 : k=k/2; } }

上一篇:hdu-1018-Big Number
下一篇:Main函数

相关文章

相关评论