希尔插入排序法 -- C语言

71 阅读 0 评论 47 点赞

我是靠谱客的博主清新毛衣，最近开发中收集的这篇文章主要介绍希尔插入排序法 -- C语言，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

排序原理：

希尔（ Shell）排序算法先将要排序的一组数按某个增量 d 分成若干组，每组中记录的下标相差 d 对每组中全部元素进行排序，然后用一个较小的增量对它进行再次分组，并对每个新组重新进行排序。当增量减到 1 时，整个要排序的数被分成一组，排序完成。因此希尔排序实质上是一种分组插入方法。

当数组初始状态基本有序时，直接插入排序所需的比较和移动次数均较少。当 n 值较小时， n 和 n2 的差别也较小，即直接插入排序的最好时间复杂度 O( n) 和最坏时间复杂度 0( n2) 差别不大。在希尔排序开始时，增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量 d 逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多。但由于已经按 d- 1 作为距离排过序，数组较接近于有序状态，所以新的一趟排序过程也较快。

另外，由于分组的存在，相等的元素可能会分在不同组，导致它们的次序可能发生变化，因此希尔排序是不稳定的。

草稿笔记

代码实现

代码实现需要十分注意的一点，是判断的时候需要 j >= 0; 而不是 j >0; 否则对第0个元素就没有排序了

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


#define SUCCESS		0
#define PARAM_ERR	-1

int ShellSort(int * array, int size){
	if(NULL == array){
		printf("%s para error", __func__);
		return PARAM_ERR;
	}

	int i = 0, j =0;   /*插入排序使用*/ 
	int m = 0, n = 0;  /*按dist分组使用*/
	int insert = 0;
	int dist = 0; /*希尔步距*/
#ifdef DEBUG
	int k = 0; /*debug 输出*/
#endif

	for(dist = size/2; dist > 0; dist--){ /*步距逐步减小*/		
#ifdef DEBUG		
		printf("n ========  distance = %d =============n", dist);
#endif		
		for(m =0; m < dist; m++) { //当前dist下，分别插入排序 dist -1 组

			/*对每组进行插入排序*/
			for(i = m; i < size ; i = i + dist) {
				insert = array[i];

				/*有序区, 没有找到合适的位置，向后移动*/
				for(j = i - dist; j >= 0; j = j - dist){
					if(array[j] >= insert){
						array[j + dist] = array[j];
					} else {
						break;
					}
				}
				
				/*插入到合适的位置*/
				array[j + dist] = insert;					
			}
#ifdef DEBUG			
			printf("n ------ another group -----------n");
			printf("[");
			for(k =m; k < size; k = k + dist){
				printf("  %d  ", array[k]);
			}				
			printf("]n");
			printf("n");
#endif			
		}		
	}
	


	return SUCCESS;
	
}


int main(int argc, char ** argv){
	int array[10] = {7,3,5,8,0,9,1,2,4,6};
	int i = 0;

	printf("Before sort: n");
	for(i = 0; i < 10; i++){
		printf("  %d  ", array[i]);
	}
	printf("n");
	

	ShellSort(array, 10);

	printf("after sort: n");
	for(i = 0; i < 10; i++){
		printf("  %d  ", array[i]);
	}
	printf("n");
	
	return 0;
}

编译

gcc ShellSort.c -DDEBUG

调试输出

Before sort:
  7    3    5    8    0    9    1    2    4    6

 ========  distance = 5 =============

 ------ another group -----------
[  7    9  ]


 ------ another group -----------
[  1    3  ]


 ------ another group -----------
[  2    5  ]


 ------ another group -----------
[  4    8  ]


 ------ another group -----------
[  0    6  ]


 ========  distance = 4 =============

 ------ another group -----------
[  0    7    8  ]


 ------ another group -----------
[  1    6    9  ]


 ------ another group -----------
[  2    3  ]


 ------ another group -----------
[  4    5  ]


 ========  distance = 3 =============

 ------ another group -----------
[  0    3    4    9  ]


 ------ another group -----------
[  1    5    7  ]


 ------ another group -----------
[  2    6    8  ]


 ========  distance = 2 =============

 ------ another group -----------
[  0    2    4    5    8  ]


 ------ another group -----------
[  1    3    6    7    9  ]


 ========  distance = 1 =============

 ------ another group -----------
[  0    1    2    3    4    5    6    7    8    9  ]

after sort:
  0    1    2    3    4    5    6    7    8    9