欢迎来到军工软件开发人才培养基地——学到牛牛

十大排序——希尔排序

时间:2024-05-06 07:01:10 来源:学到牛牛

希尔排序是一种特殊的插入排序,是对直接插入排序的升级改进。所以在学习希尔排序之前,一定要先弄清楚直接插入排序算法。

基本思路:

设一个序列里有n个待排序的元素,将间隔相同距离的元素分为一组进行比较,这里的间隔称之为增量,增量(gap)通常为n/2(奇数偶数都可以),随着算法的进行增量慢慢缩小,直到相邻的元素比较完,结束排序。

详细步骤:

首先,列出一组待排序的元素组成一个数组(如图1-1所示),数组长度len为8,增量gap可为4,2,1(每结束一轮排序,增量减半),首先增量为4时,将间隔相同距离的元素分为一组进行比较

图1-1

 

相同颜色的元素即为一组进行比较(如图1-2所示)

图1-2

第一组:8和6进行比较,8 > 6两个元素交换位置(进行升序排序,小元素在前,大元素在后),如图1-3所示:

图1-3

第二组:1和2进行比较,1 < 2两个元素位置不变

第三组:5和3进行比较,5 > 3两个元素交换位置

第四组:4和7进行比较,4 < 7两个元素位置不变

第一轮比较结束,结果如图1-4所示:

 

图1-4

接下来增量为2重新对数组进行分组排序,共分为两组,如图1-5所示:

图1-5

第一组:6、3、8、5进行比较,小的元素在前,大的元素在后,结果为3、5、6、8。

第一组:1、4、2、7进行比较,小的元素在前,大的元素在后,结果为1、2、4、7。

第二轮比较结束,结果如图1-6所示:

图1-6

接下来继续缩小增量,当增量为1时,就是直接插入排序,如果不太清楚的同学可以看看之前插入排序算法的文章,最后一轮排序结束后就可以得到一个完整的升序数组(如图1-7所示)。

图1-7

代码实现:

#include <stdio.h>

 

void shellSort(int *a, int len) 

{

   int i, j, k, temp, gap;  // gap 为增量

   for (gap = len / 2; gap > 0; gap /= 2)   // 增量初始化为数组长度的一半,每次遍历后增量减半

 {  

for (i = 0; i < gap; ++i)     // 变量 i 为每次分组的第一个元素下标 

 for (j = i + gap; j < len; j += gap) //对增量为gap的元素进行直插排序,当gap为1时,就是直插排序

{

                     temp = a[j];  // 备份a[j]的值

                     k = j - gap;  // j初始化为i的前一个元素(与i相差gap长度)

                     while (k >= 0 && a[k] > tmp) 

{

                          a[k + gap] = a[k]; // 将在a[i]前且比temp的值大的元素向后移动一位

                           k -= gap;

                     }

                       a[k + gap] = temp; 

                }

            }

        }

}

 

int main(  )

{

        int i;

        int a[8]={8,1,5,4,6,2,3,7};

        int len = 8;

        shellSort(a, len);        // 调用希尔排序函数

        printf("希尔升序排列后结果为:\n");

        for (i = 0; i < len; i++)

 {                   

            printf("%d\t",a[i]);      // 排序后的结果的输出

        }

        printf("\n");

 

        return 0;

}