插入类排序-----希尔排序

偏执的太偏执、 2022-05-03 01:30 250阅读 0赞

//希尔排序：取增量d1的分为一组，共分成d1组分别进行插入排序，然后每组对应元素放在一起，然后取d2...知道d=1 
    //希尔排序的代码可以近乎看成把1换成dk
    /*我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数
    即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部
    元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至
    为1，最后使用直接插入排序完成排序。*/
    # include<stdio.h>//时间复杂度 O(n^3/2)  不稳定 
    void ShellSort(int a[], int n){
    	int i, j, dk;
    	for(dk = n/2; dk > 0; dk /= 2){
    		for(i = dk; i <= n; i++){
    		if(a[i] < a[i-dk]){
    			a[0] = a[i];
    			for(j = i-dk; a[j]>a[0] && j>=0; j -= dk)
    			a[j+dk] = a[j];
    			a[j+dk] = a[0];
    		}
    	 }
      }		
    } 
    
    
    int main(){
    	int n;
    	printf("请输入你要排序的数的个数:"); 
    	scanf("%d", &n);
    	int *a = new int[n+1];//申请一个整型变量空间,没有赋初值，并定义一个整型指针a指向该地址空间 
    	for(int i = 1; i <= n; i++)
    	scanf("%d", &a[i]);
    	ShellSort(a, n);
    	printf("排序后:"); 
    	for(int j = 1; j <= n; j++)
    	printf("%6d", a[j]);
    	delete []a;//回收数组a的空间 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，250人围观）

还没有评论，来说两句吧...

相关阅读

相关冒泡排序、插入排序、希尔排序、选择排序

一、排序协议的定义在博客的开头的，我们先给出排序协议的定义。因为我们本篇博客含有多种排序方式，为了使每种排序方法对外调用方式一致，我们需要定义一个排序的相关协议。所有排序的

谁借莪１个温暖的怀抱￠/ 2023年10月12日 13:17/ 0 赞/ 49 阅读

相关【算法】【排序】【插入类】希尔排序 ShellSort

include<stdio.h> include <time.h> include<stdlib.h> int main(){

曾经终败给现在/ 2023年10月10日 09:33/ 0 赞/ 25 阅读

相关排序算法 - 希尔排序（插入）

排序算法概览 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9

谁践踏了优雅/ 2022年12月04日 07:32/ 0 赞/ 178 阅读

相关插入排序：希尔排序

希尔排序(Shell’s Sort) 是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版

╰+哭是因爲堅強的太久メ/ 2022年10月16日 02:58/ 0 赞/ 172 阅读

相关排序 - 插入排序 [2 - 希尔排序]

在上一篇中我说了基本插入排序的基本算法，不知道你是不是花了正好20分钟。这一篇我说下对基本插入排序的改进算法，希尔排序。shell sort. 为什么

墨蓝/ 2022年10月02日 02:00/ 0 赞/ 156 阅读

相关选择排序、插入排序、希尔排序总结

本来昨天想写最小生成树的kruskal算法，但是其中需要将图的边集数组进行排序，要用到排序算法，所以暂时先将kruskal算法放一下，把排序算法好好复习和总结一遍以下的排序

╰+哭是因爲堅強的太久メ/ 2022年09月28日 11:57/ 0 赞/ 187 阅读

相关插入排序和希尔排序

几种常见排序的动画演示：[常见排序的动画演示][Link 1] 插入排序：由N-1趟排序组成，第i趟排序保证位置0到i-1上元素是已经排好序的。在该算法代码实现中使

逃离我推掉我的手/ 2022年08月06日 04:12/ 0 赞/ 163 阅读

相关希尔插入排序:

按一定跨度d两两进行比对并按序交换位置，进行完一轮比对后跨度缩小再进行下一轮，经过几轮后先将整个序列变成部分有序，然后再进行直接插入排序，减少直接插入排序的开销。 ![Cen

Myth丶恋晨/ 2022年06月04日 07:45/ 0 赞/ 203 阅读

相关插入类排序-----希尔排序

//希尔排序：取增量d1的分为一组，共分成d1组分别进行插入排序，然后每组对应元素放在一起，然后取d2...知道d=1 //希尔排序的代码可以近乎看成把1换成

偏执的太偏执、/ 2022年05月03日 01:30/ 0 赞/ 251 阅读

相关插入排序——希尔排序

/ 算法思想：先将整个待排序元素序列分割成若干子序列，对每个子序列分别进行直接插入排序。当整个待排序元素序列“基本有序”时，再

悠悠/ 2022年03月20日 02:52/ 0 赞/ 247 阅读