解析shell排序的实现代码

代码如下:

#include <iostream>
using namespace std;
void ShellQin(int A[],int n)
{
    int gap=n/2;
    int i,j;
    for(;gap>0;gap=gap/2)//设置初始gap，按照gap进行分组，gap按照gap/2递减
    {
        //设置好gap以后，从gap开始一直到最后一个元素，为每一个元素在其对应的组进行插入排序。gap应该是该组所在位置的第2个元素，第一个元素位置是0
        for(i=gap;i<n;i++)
        {
            j=i;
            //对一组进行插入排序
            if(A[j-gap]>A[j])
            {
                /*如果A[j]>A[j-gap]意味着A[j]大于其所在组的前一个位置，那么将
                  A[j]保存在temp中，将从组中所有大于A[j]的数后移，最后空出来的位置
                  存放A[j]
                */
                int temp=A[j];//保存A[J]
                do
                {
                    A[j]=A[j-gap];
                    j=j-gap;
                }while(j>=0&&temp<A[j]);//后移每一个大于A[j]的数
                A[j+gap]=temp;//将A[j]插入到合适的位置
            }
        }
    }
    for(i=0;i<n;i++)
    {
        cout<<*(A+i)<<" ";
    }
}
int main1()
{
    int a[]= {5,4,3,21,1,100,93,1,3,2,4};
    ShellQin(a,11);
    return 0;
}

和朋友讨论过后，虽然希尔和插排最坏的情况都是n平方，认为希尔效率要比插排好的原因是，时间复杂度前面的系数要小于插排，特别是逆序的时候，很明显的减少了比较的次数。就如同快排之于堆排，快排前的系数远小于堆排，加上简单易用所以称为程序员们最爱。
下面的这种算法也叫做shell排序，与上面的区别在于进行插入排序的时候用交换相邻两个数据代替了移位（即先取出key关键字，将大于key的值向后移位）


代码如下:

//交换两个小数
void swapdouble(double *a,double *b){
   double temp=*a;
   *a=*b;
   *b=temp;
}
void Shell(double* p,int n)
{
    int gap=n/2;
    int i,j;
    for(;gap>0;gap=gap/2)
    {
        for(i=gap;i<=n-1;i++)//从gap开始为所在的每个组进行插入排序，i=gap是该组的第二个元素
        {
            j=i;
            if(*(p+j)<*(p+j-gap))
            {
                while(j>=gap && *(p+j)<*(p+j-gap))
                {
                    swapdouble(p+j,p+j-gap);
                    j=j-gap;
                }
            }
        }
    }
}

赞 (0)

相关推荐

  • 解析shell排序的实现代码

    复制代码 代码如下: #include <iostream> using namespace std; void ShellQin(int A[],int n) {     int gap=n/2;     int i,j;     for(;gap>0;gap=gap/2)//设置初始gap,按照gap进行分组,gap按照gap/2递减     {         //设置好gap以后,从gap开始一直到最后一个元素,为每一个元素在其对应的组进行插入排序.gap应该是该组所在位置的第2

  • shell中的排序算法示例代码

    shell中的排序算法示例代码

    目录 冒泡排序法 基本思想: 算法思路 直接选择排序 基本思想: 反转排序 基本思想: 直接插入算法 基本思想: 希尔算法 基本思想 冒泡排序法 类似旗袍上涌的动作,会将数据在数组中从小大大或者从大到小不断的向前移动. 基本思想: 冒泡排序的基本思想是对比相邻的两个元素值,如果满足条件就交换元素值,把较小的元素移动到数组前面,把大的元素移动到数组后面(也就是交换两个元素的位置),这样较小的元素就像气泡一样从底部上升到顶部. 算法思路 冒泡算法由双层循环实现,其中外部循环用于控制排序轮数,一般为要

  • python3实现常见的排序算法(示例代码)

    python3实现常见的排序算法(示例代码)

    冒泡排序 冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. def mao(lst): for i in range(len(lst)): # 由于每一轮结束后,总一定有一个大的数排在后面 # 而且后面的数已经排好了 # 即i轮之后,就有i个数字被排好 # 所以其 len-1 -i到

  • 利用正则表达对IP进行排序的实现代码

    1.补零,使得可以按照字符串顺序进行比较. 2.截取保留后三位(ip地址最多就3位). 3.利用Arrays.sort()方法对截取的字符串进行排序.. 4.去除多余的0,回复ip原样. 5.实现代码: package IPSort; import java.util.Arrays; /** * 利用正则表达对IP进行排序,分四步 * @author tiger * */ public class IPSortTest { public static void main(String[] arg

  • Python实现各种排序算法的代码示例总结

    Python实现各种排序算法的代码示例总结

    在Python实践中,我们往往遇到排序问题,比如在对搜索结果打分的排序(没有排序就没有Google等搜索引擎的存在),当然,这样的例子数不胜数.<数据结构>也会花大量篇幅讲解排序.之前一段时间,由于需要,我复习了一下排序算法,并用Python实现了各种排序算法,放在这里作为参考. 最简单的排序有三种:插入排序,选择排序和冒泡排序.这三种排序比较简单,它们的平均时间复杂度均为O(n^2),在这里对原理就不加赘述了.贴出来源代码. 插入排序: def insertion_sort(sort_lis

  • C语言基本排序算法之shell排序实例

    本文实例讲述了C语言基本排序算法之shell排序.分享给大家供大家参考,具体如下: shell排序是对直接插入方法的改进方法. /*------------------------------------------------------------------------------------- Shell_sort.h shell排序是对直接插入方法的改进,它并不是对相邻元素进行比较,而是对一定间隔的元素比较. 选择增量序列的几种方法:(为方便,本例采用第一种增量序列) 1. h[1]=

  • iOS对数组进行排序的实例代码

    一,代码. - (void)viewDidLoad { [super viewDidLoad]; // Do any additional setup after loading the view, typically from a nib. //直接排序对象 NSSortDescriptor *descriptor = [NSSortDescriptor sortDescriptorWithKey:nil ascending:YES]; NSArray *descriptors = [NSAr

  • JavaScript 冒泡排序和选择排序的实现代码

    废话不多说了,直接给大家贴代码了,具体代码如下所述: var array = [1,2,3,4,5]; // ---> 服务 //效率 ---> 针对一个有序的数组 效率最高 //标志 true false for(var j = 0; j < array.length - 1;j++ ){ //- j 每次排序完成之后 后面减少比较的次数 var isTrue = true; //如果数组本身就是升序,则直接输出 for(var i = 0; i < array.length -

  • Java实现对中文字符串的排序功能实例代码

    废话不多说了,直接给大家代码分享代码了. 具体代码如下所示: package test; /** * * @Title 书的信息类 * @author LR * @version . * @since -- */ public class Book { private String book_id; private String book_name; private String publishing_house; public Book(String book_id, String book_

  • c语言5个常用的排序算法实例代码

    1.插入排序 基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕. void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); ++i) { int temp = nums[i]; int j = i; for (; j > 0 && temp < nums[j-1]; --j) nums[j] =

随机推荐