排序算法——希尔排序

2023-12-22 06:45:38
  • 实际上是对插入排序的优化。在插入排序的基础上,引入步长的概念,将元素分为几个组,在组内进行插入排序,在各组内进行插入排序后,再逐渐缩短步长进而继续进行插入排序,直到步长为1停止排序,此时全部元素排序完成。通过这种方法可以尽可能地减少元素位置变换次数
     66		43		89		98		12		18		15		23		33		50
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		
    //①初始步长为len/2也就是[10/2]=5,则
    a[0]a[5]一组 a[1]a[6]一组 a[2]a[7]一组 a[3]a[8]一组 a[4]a[9]一组,共5组
    //首先在5组内分别进行插入排序,变为
     18		15		23		33		12		66		43		89		98		50
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
    //这轮排序,元素位置变化次数为8次
    //②进行第一轮排序后,步长变为len/4向下取整也就是[10/4]=2,则
    a[0]a[2]a[4]a[6]a[8]一组 a[1]a[3]a[5]a[7]a[9]一组,共2组
    //在2组内分别进行插入排序,变为
     12		15		18		33		23		50		43		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		0
    //这轮排序,元素位置变化次数为6次
    //③排序后,步长继续变化,变为len/8向下取整也就是[10/8]=1,此时就是插入排序,变为
     12		15		18		33		23		50		43		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		1
     12		15		18		33		23		50		43		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		2
     12		15		18		33		23		50		43		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		3
     12		15		18		23		33		50		43		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		4
     12		15		18		23		33		50		43		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		5
     12		15		18		23		33		43		50		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		6
     12		15		18		23		33		43		50		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		7
     12		15		18		23		33		43		50		66		98		89
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		8
     12		15		18		23		33		43		50		66		89		98
    a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		9
    //此轮排序中,元素位置变化只有第4、6、9次各变化了2个元素的位置,元素位置变化共有6次
    
    //①②③轮结束后,元素位置变化次数总共有8+6+6=20次,相比较插入排序32次元素位置变化次数节省了32-20=12次,12/32=3/8=0.375=37.5%,优化了大概37.5%的元素位置变化次数
    
    代码:
    //希尔排序
    void shell_sort(int* a, int len){
    	int step = len / 2;
    
    	int temp;
    	int j;
    	while (step){//根据步长来分组
    		//组内作插入排序
    
    		for (int i = step; i < len; i++){//从step开始  len-1-step轮
    			temp = a[i];//临时保存待插数据
    
    			for (j = i - step; j >= 0; j -= step){//待插数据前一个开始往前循环(越界循环结束)
    				if (a[j]>temp){//比待插数据大则往后覆盖
    					a[j + step] = a[j];
    				}
    				else{
    					break;
    				}
    			}
    			//用待插数据覆盖回来(第二步结束后下标的下一个位置)
    			a[j + step] = temp;
    		}
    		step >>= 1;//step = step / 2;
    	}
    }

文章来源:https://blog.csdn.net/qq_59470001/article/details/135119965
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。