常用排序算法的比较(7)

0。0 第一次写了10KB+的代码略感动。 虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

high = m-1; else low = m +1; } for( j = i-1; j > high ; j--)//将找到的待插入值应在的位置腾出（往后移动其他数据） { p[j+1] = p[j]; } p[high +1] = p[0];//插入值 }

代码中，有外层for循环负责Num – 1次扫描，完成寻找序列中所有记录的插入位置，内层的while循环就是通过折半查找的方法定位当前元素在有序段中的位置。为了把当前元素复制到有序断种，需要把大于当前元素关键字的元素往后移动，内层的for循环就是移动大于当前元素关键字的元素，最后在外循环里将当前元素的值插入到正确位置。

2.3.3希尔排序

希尔排序是对直接插入排序算法的改进，通过减少元素的移动来优化算法，提高算法的效率。其基本思想是，将待排序的记录分成几组，每组中元素都比原来的序列少，从而减少参与直接插入排序的数据量，在各组中分别进行直接插入排序。通过几次排序之后，记录的排列已经基本上有序，这时候再对所有的记录实施直接插入排序。

ShellSort（）：

for( d = (Num+1) / 2; d >= 1; d = d/2) //设置排序的步长d，每次步长减半，直到减到1

{ for( i = d+1; i <= Num; i++)//定位到每个元素 { p[0] = p[i]; j = i - d; while( j > 0 && p[0] < p[j]) { p[j +d] = p[j]; j = j - d; } p[j + d] = p[0]; } }

具体步骤描述：待排序的记录为Num个，先选取整数 d (d<n),将所有距离为d的记录构成一组，从而将整个待排序记录序列分割成为d个子序列，对每个分组分别进行直接插入排序，然后再缩小间隔d至d的一半，重复上述的步骤，直到最后取d = 1，即将所有记录放在一组进行最后一次直接插入排序，最终将