户外运动网站模板,h5页面导入 WordPress,深圳电子厂,网站mip怎么做1.算法思想
希尔排序:先追求表中元素部分有序再逐渐逼近全局有序.
希尔排序∶先将待排序表分割成若干形如 L [ i , i d , i 2 d . . . . , i k d ] L[i,i d,i 2d ...., i kd] L[i,id,i2d....,ikd]的“特殊”子表#xff0c; 对各个子表分别进行直接插入排序。缩小增量…1.算法思想
希尔排序:先追求表中元素部分有序再逐渐逼近全局有序.
希尔排序∶先将待排序表分割成若干形如 L [ i , i d , i 2 d . . . . , i k d ] L[i,i d,i 2d ...., i kd] L[i,id,i2d....,ikd]的“特殊”子表 对各个子表分别进行直接插入排序。缩小增量d重复上述过程直到d1为止。 希尔本人建议:每次将增量缩小一半。 分析每一趟排序后的状态 2.算法实现
//希尔排序
void Shellsort(int A[], int n) {int d, i, j;//A[0]只是暂存单元不是哨兵当j0时插入位置已到for (d n / 2; d 1; d d / 2)//步长变化for (i d 1; i n; i)if (A[i] A[i - d]) {//需将A[i]插入有序增量子表A[0] A[i];//暂存在A[0]for (j i - d; j 0 A[0] A[j]; j - d)A[j d] A[j];//记录后移查找插入的位置A[j d] A[0];//插入}//if
}3.算法性能分析
1.空间复杂度 O ( 1 ) O(1) O(1)
2.时间复杂度
时间复杂度∶和增量序列 d 1 , d 2 , d 3... d1, d2, d3... d1,d2,d3...的选择有关目前无法用数学手段证明确切的时间复杂度。 最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)当n在某个范围内时可达 O ( n 1.3 ) O(n^{1.3}) O(n1.3)
稳定性:不稳定! 适用性:仅适用于顺序表不适用于链表.
