Shell排序

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

算法思想：先比较距离远的元素，而不想简单交换排序算法那样先比较相邻的元素。这样可以快速减少大量的无序情况，从而减轻后续工作。被比较的元素之间的距离之间的距离逐步减少，直到减少为1，这时排序变成了相邻元素的互换。  
  
  
Shell排序是比较排序，时间复杂度O(n^a),1<a<2,平均a约为1.3，空间复杂对O(1)，非稳定排序。

<table> 
 <tbody> 
  <tr> 
   <td> <p>Shell排序</p> </td> 
   <td> <p>比较排序</p> </td> 
   <td> <p>O(n^a),1&lt;a&lt;2,平均a约为1.3</p> </td> 
   <td> <p>O(1)</p> </td> 
   <td> <p>非稳定排序</p> </td> 
  </tr> 
 </tbody> 
</table>

算法实现ShellSort.h

#include <iostream>
    
    using namespace std;
    
    template<class T>
    void ShellSort(T a[],int n);
    template<class T>
    void Output(T a[],int n);
    
    template<class T>
    void ShellSort(T a[],int n)
    {
    	int gap, i, j;
    
    	for (gap = (n+1)/2; gap > 0; gap /= 2)
    	{
    		for (i = gap; i < n; i++)
    		{
    			for (j = i-gap; j >= 0 && a[j] > a[j+gap]; j -= gap)
    				swap(a[j],a[j+gap]);
    		}
    	}
    }
    
    template<class T>
    void Output(T a[],int n)
    {
    	for (int i = 0; i < n; i++)
    		cout << a[i] <<" ";
    	cout << endl;
    }

测试用例：main.cpp

#include "ShellSort.h"
    
    #define size(a) sizeof(a)/sizeof(a[0])
    
    int main()
    {
    	int a[] = {-5,-11,4,2,21,56,9,-11,9,333};
    	int n = size(a);
    	//int n = sizeof(a)/sizeof(a[0]);
    	cout << "排序之前：" << endl;
    	Output(a,n);
    	ShellSort(a,n);
    	cout << "排序之后：" << endl;
    	Output(a,n);
    	return 0;
    }

结果：

![0_13125370244M64.gif][]

[0_13125370244M64.gif]: /images/20220618/551b819dd30a478990b492e5e213b62c.png

发表评论取消回复

表情：

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

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

相关阅读

相关希尔排序(Shell Sort)

是插入排序经过改进之后的高效版本，也称缩小增量排序。 1959 年提出，是突破时间复杂度 O(n2) 的第一批算法之一。缩小增量排序的最优增量选择是一个数学难题，一般采用

约定不等于承诺〃/ 2023年07月25日 05:26/ 0 赞/ 14 阅读

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

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

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

相关排序5-shell

在插入排序中，数组项只移到相邻位置。当项与正确的有序位置距离较远时，它必须进行很多次这样的移动。所以当数组完全无序时，插入算法效率不高，但当数组基本有序时，插入法有很好

╰+哭是因爲堅強的太久メ/ 2022年11月21日 01:19/ 0 赞/ 22 阅读

相关排序——希尔排序（Shell Sort）

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对

ゞ浴缸里的玫瑰/ 2022年08月20日 11:18/ 0 赞/ 149 阅读

相关 Shell排序

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

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

相关算法-->shell排序

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

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

相关 shell排序java

shell排序java public static <AnyType extends Comparable<? super AnyType>> void shel

客官°小女子只卖身不卖艺/ 2022年06月07日 09:49/ 0 赞/ 33 阅读

相关 Shell 选择排序

举例 !/bin/bash echo "please input a number list:" read -a arrs for((i=0;

迈不过友情╰/ 2022年05月21日 12:38/ 0 赞/ 54 阅读

相关 Shell 冒泡排序

举例 !/bin/bash echo "please input a number list:" read -a arrs for((i=0;

曾经终败给现在/ 2022年05月21日 12:38/ 0 赞/ 72 阅读

相关排序算法---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 阅读