折半排序

比眉伴天荒 2022-06-13 02:37 111阅读 0赞

一、简介

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

二、原理

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比 较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

排序过程：

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

三、实例

![Center][]

#include <stdio.h>
    void shell_sort(int *a, int n)
    {
    	int i, j, flag, temp;
    	int gap = n;
    
    	while(gap > 1)
    	{
    		gap = gap/2; //增量缩小，每次减半(折半)
    		do
    		{
    			flag = 0;
    			//n-gap是控制上限不让越界
    			for(i = 0; i < n-gap; i++)
    			{
    				j = i + gap; //相邻间隔的前后值进行比较
    				if(a[i] > a[j])
    				{
    					temp = a[i];
    					a[i] = a[j];
    					a[j] = temp;
    					flag = 1;
    				}
    			}
    		}while(flag != 0);
    	}
    }
    
    int main(int argc, char *argv[])
    {
    	int a[] = {2, 8, 1, 9, 7, 5, 4, 0, 6, 3};
    	int n = sizeof(a)/sizeof(a[0]); //数组元素个数
    	shell_sort(a, n); //希尔排序
    	return 0;
    }

[Center]: /images/20220613/a002f202e80c461785eae2fad8f45fa5.png