即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

排序之二:希尔排序(C语言实现)

编程语言 TECH_PRO 9℃ 0评论

希尔排序的基本思想是:先将整个待排序列分割成若干子序列分别进行进行直接插入排序,等到整个待排序列基本有序时,再对全体记录依次进行直接插入排序。希尔排序也叫缩小增量排序,是1959年由D.L.Shell提出来的。

希尔排序的具体实现方法和步骤:

        a、选择一个步长序列d1,d2,d3,…,dk,其中,di > dj,dk = 1;

        b、按步长序列个数K对序列进行K趟排序

        c、每趟排序,根据对应的步长di进行分组,即将待排序的记录序列所有距离为di的记录放在同一组中,如此可将待排序列分割成若干个长度为m的子序列,分别对各组进行直接插入排序。当dk=1时,整个序列作为一个表来处理,表长度即为整个序列的长度,整个排序结束。

具体的希尔排序函数实现如下(按照逐渐递增来进行排序):

/* 希尔排序算法的简单实现
 *  array[] : 要排序的数组
 *  length  : 要排序的数组的长度
 *  d[]     : 增量值数组
 *  number  : 增量值个数
 */
void shell_sort(int array[], int length, int d[], int number)
{
 int i, j, k, m;
 int span; // 用于存放具体增量的数值
 int temp; // 用于存放临时的待排序元素的值

 for(m = 0; m < number; m++)
 {
  span = d[m]; // 获取增量值
  for(k = 0; k < span; k++)
  {
   for(i = k; i < length-1; i += span)
   {
    temp = array[i + 1];
    j = i;
    while((j > -1) && (temp < array[j]))
    {
     array[j + 1] = array[j];
     j--;
    }
    array[j + 1] = temp;
   }
  }
 }
}

测试函数的实现如下:

/* 程序的入口函数 */
int main()
{
 int a[ARRAY_LENGTH];
 int i;

 int d[3] = {5, 3, 1}; // 定义一个表示增量值的数组

 /* 输入10个整形元素 */ 
 printf("Input %d numbers : \n", ARRAY_LENGTH);
 for(i = 0; i < ARRAY_LENGTH; i++)
 {
  scanf("%d", &a[i]);
 }

 printf("****************************************************************\n");

 /* 把排序前元素都打印出来 */
 printf("The elements before sort is : \n");
 for(i = 0; i< ARRAY_LENGTH; i++)
 {
  printf("%d ", a[i]);
 }
 printf("\n");

 printf("****************************************************************\n");

 /* 对元素进行有小到大的直接插入排序 */
 shell_sort(a, ARRAY_LENGTH, d, sizeof(d)/sizeof(d[0]));

 /* 把排序后元素都打印出来 */
 printf("The elements after sort is : \n");
 for(i = 0; i < ARRAY_LENGTH; i++)
 {
  printf("%d ", a[i]);
 }
 printf("\n");

 return 0; 
}

编译运行结果如下所示:






转载请注明:CodingBlog » 排序之二:希尔排序(C语言实现)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情