排序算法---Shell排序

朱雀 2022-03-11 04:24 56阅读 0赞

基本思路：

先把数组分成差量为d 的几组，即：

a\[1\],a\[1+d\] ,a\[1+d+d\] ... 为一组；

a\[2\],a\[2\+d\] ,a\[2\+d+d\] ... 为一组；

然后依次对每组进行插入排序。

各组排完序后 在 取第二个增量d2 < d 重复上述 分组和排序。

直到 增量 d = 1； 即 所有的数都放在同一组中进行插入排序。

下面是 c语言实现

#include <stdio.h>
     
    void shellInsertSort(int a[] ,int n){
     	int i,j,d;
     	d = n/2;
     	while(d>=1){
    	 	for(i = d+1 ;i<=n ;i++){
    	 		j = i-d;
    	 		while(j>0){
    		 		if(a[j]>a[j+d]){
    		 			a[0] = a[j];
    		 			a[j] = a[j+d];
    		 			a[j+d] = a[0];
    		 			j = j-d;
    		 		}else{
    		 			j = 0;
    		 		}
    		 	}
    	 	}
    	 	d=d/2;
     	}
    }
    
    void shellSortPass(int a[],int d){
    	for(int i = d+1 ;i<=8 ;i++){
    		if(a[i]<a[i-d]){
    			a[0] = a[i];
    			int j = i-d;
    			do{
    				a[j+d] = a[j];
    				j = j-d;
    			}while(j>0&&a[0]<a[j]);
    			a[j+d] = a[0];
    		}
    	}
    }
    void shellSort(int a[]){
    	int d = 8;
    	do{
    		d = d/2;
    		shellSortPass(a,d);
    	}while(d>1);
    	
    }
    void print(int a[] ,int n)
    {
        for (int i = 1;i<n;i++)
        {
            printf("%d  ",a[i]);
        }  
        printf("\n");
    }
     
     
    int main(int argc, char *argv[])
    {
     	int a[]=
        {
            0,59,48,75,98,86,23,37,60
        };
        print(a,9);
        shellSort(a);
        //shellInsertSort(a,9);
        print(a,9);
     	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关算法-排序算法：希尔排序（Shell Sort）【O(n^2)】

希尔排序（Shell Sort）：1959年Shell发明，第一个突破O(n2)的排序算法，是插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序

逃离我推掉我的手/ 2023年10月04日 04:50/ 0 赞/ 11 阅读

相关排序算法-希尔排序(Shell Sort)

文章目录希尔排序法介绍希尔排序法算法时间复杂度稳定性其

灰太狼/ 2023年07月02日 04:25/ 0 赞/ 14 阅读

相关 java shell算法_排序算法复习（Java实现）(三）：插入，冒泡，选择，Shell,快速排序...

packagealgorithms;importjava.util.Arrays;/\\\@authoryovn \\/publicclassRadixSorter \{pu

冷不防/ 2022年11月11日 14:47/ 0 赞/ 45 阅读

相关【算法】希尔排序算法Shell Sort

原理基本思想：希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组

- 日理万妓/ 2022年11月01日 04:26/ 0 赞/ 156 阅读

相关 Shell排序

算法思想：先比较距离远的元素，而不想简单交换排序算法那样先比较相邻的元素。这样可以快速减少大量的无序情况，从而减轻后续工作。被比较的元素之间的距离之间的距离逐步减少，直到减少为

ゝ一纸荒年。/ 2022年06月17日 23:25/ 0 赞/ 48 阅读

相关算法-->shell排序

shell排序算法严格来说是基于插入排序的思想，又称为希尔排序，或缩小增量排序：将又n个元素的数组分成n/2个数字序列，第一个数据和n/2+1个数据为一对

妖狐艹你老母/ 2022年06月12日 05:29/ 0 赞/ 35 阅读

相关图解排序算法及实现——希尔排序（Shell Sort）

希尔排序（ShellSort）也称增量递减排序算法，即跨多步版的InsertionSort，是InsertionSort基础上的改进版。InsertionSort可以看作She

红太狼/ 2022年05月14日 05:39/ 0 赞/ 209 阅读

相关排序算法--------Shell排序（希尔排序/缩小增量排序）

Shell排序（希尔排序/缩小增量排序） 1.简介 2.改进了什么？ 3.思想的体现 4.算法复杂度的分析 5.举个例子 6.java

浅浅的花香味﹌/ 2022年04月23日 01:58/ 0 赞/ 135 阅读

相关排序算法---Shell排序

基本思路：先把数组分成差量为d 的几组，即： a\[1\],a\[1+d\] ,a\[1+d+d\] ... 为一组； a\[2\],a\[2\+d\] ,a\[2\+

朱雀/ 2022年03月11日 04:24/ 0 赞/ 57 阅读

相关算法排序-4、希尔排序（Shell Sort）

希尔排序（Shell Sort） 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素

妖狐艹你老母/ 2021年09月28日 09:24/ 0 赞/ 312 阅读