利用希尔排序进行将数组序列从小到大排序

管理员

1 题目

功能:希尔排序
描述:利用希尔排序进行将数组序列从小到大排序

2 思路

希尔排序是在直接插入排序的基础上做的改进,将要排序的序列按固定增量分成若干组,等距离者在同一组中,然后再程纽内进行直接插入排序。

这里面的固定增量从n/2开始,以后每次缩小到原来的一半.

3 代码

#include <stdio.h> 
#include <stdlib.h>

/**
功能:希尔排序
描述:利用希尔排序进行将数组序列从小到大排序
**/

void shsort(int s[], int n)	{
    int i, j, d;
    d = n / 2;													// 确定固定增量值
    while (d >= 1){
        for (i = d + 1; i <= n; i++) {							// 数组下标从d+1开始进行直接插入排序
            s[0] = s[i];										// 设置监视哨
            j = i - d;											// 确定要进行比较的元素的最右边位置
            while ((j > 0) && (s[0] < s[j])) {
                s[j + d] = s[j];								// 数据右移
                j = j - d;										// 向左移d个位置
            }
            s[j + d] = s[0];									// 在确定的位置插入s[i]
        }
        d = d / 2;												// 增量变为原来的一半
    }
}

int main(int argc, char const *argv[]) {

    int a[11], i;												// 定义数组及变量为基本整型
    printf("请输入10个数据:n");
    for (i = 1; i <= 10; i++)
        scanf("%d", &a[i]);										// 从键盘中输入10个数据
    shsort(a, 10);												// 调用shsort()函数
    printf("排序后的顺序是:n");
    for (i = 1; i <= 10; i++)
        printf("%5d", a[i]);									// 将排好序的数组输出
	printf("n");
}

示例结果:

$ gcc ex059.c -o demo
$ ./demo
请输入10个数据:
34
15
56
12
90
43
9
7
93
100
排序后的顺序是:
    7    9   12   15   34   43   56   90   93  100