面试复习(C++)之希尔排序

#include<iostream>
using namespace std;

void Shellsort(int *a,int len)
{
    int gap;
    for(gap=3;gap>0;gap--)
    {
        for(int i=0;i<gap;i++)
            for(int j=i+gap;j<len;j=j+gap)
            {
                if(a[j]<a[j-gap])
                {
                    int temp=a[j];
                    int k=j-gap;
                    while(k>=0&&a[k]>temp)
                    {
                        a[k+gap]=a[k];
                        k=k-gap;
                    }
                    a[k+gap]=temp;
                }
            }
    }
}
int main()
{
    int n=5;
    int a[10];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    Shellsort(a,n);
    for(int j=0;j<n;j++)
    {
        cout<<a[j]<<" ";
    }
}
时间: 10-03

面试复习(C++)之希尔排序的相关文章

希尔排序Shell sort

希尔排序Shell Sort是基于插入排序的一种改进,同样分成两部分, 第一部分,希尔排序介绍 第二部分,如何选取关键字,选取关键字是希尔排序的关键 第一块希尔排序介绍 准备待排数组[6 2 4 1 5 9] 首先需要选取关键字,例如关键是3和1(第一步分成三组,第二步分成一组),那么待排数组分成了以下三个虚拟组: [6 1]一组 [2 5]二组 [4 9]三组 看仔细啊,不是临近的两个数字分组,而是3(分成了三组)的倍数的数字分成了一组, 就是每隔3个数取一个,每隔三个再取一个,这样取出来的数

算法练习--直接插入排序、希尔排序

背景: 原来虽然有学过数据结构,排序一些,但是没有好好学,现在复习一下. 正题: 1.直接插入排序 直接贴一下百科:每次取出无序数组中的一个数,把他和有序数组中的数比较,插到适当位置,直到无序表为空,有序表满. 原理很简单,就我而言,首先想到的是新建一个new_list数组,充当有序表,然后一步一步将无序表里的值拿出来放到新的数组中.但是,写完之后,看了看书上的实例, 上面直接用单数组也可以,虚拟划分数组为两部分.代码简便多.于是很我也修改了一下自己的代码. 代码如下: <?php functi

(转载)经典排序算法-希尔排序

经典排序算法 - 希尔排序Shell sort 希尔排序Shell Sort是基于插入排序的一种改进,同样分成两部分, 第一部分,希尔排序介绍 第二部分,如何选取关键字,选取关键字是希尔排序的关键 第一块希尔排序介绍 准备待排数组[6 2 4 1 5 9] 首先需要选取关键字,例如关键是3和1(第一步分成三组,第二步分成一组),那么待排数组分成了以下三个虚拟组: [6 1]一组 [2 5]二组 [4 9]三组 看仔细啊,不是临近的两个数字分组,而是3(分成了三组)的倍数的数字分成了一组, 就是每

算法 希尔排序

希尔排序 Shell Sort 介绍: 希尔排序(Shell Sort)也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率比直接插入排序有较大提高. 执行流程: 首先

算法学习#09--用简单的思维理解选择、插入、冒泡和希尔排序

选择排序 1.原理 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 2.特点 ①运行时间与输入无关. 无论输入初始状态如何,是否有序,都需要遍历数组来找出最小的元素.其他算法则更善于利用输入的初始状态来优化时间. ②数据移动次数最小. 如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进

奔走在算法的大路上(一)排序之希尔排序

希尔排序是插入排序的一种更高效的改进版本.它的作法不是每次一个元素挨一个元素的比较.而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置:然后增量缩小:最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率.希尔排序对增量序列的选择没有严格规定. 希尔排序最关键的是选对增量,关于增量的选择,建议参考:http://zh.wikipedia.org/wiki/希尔排序  中的步长序列. 希尔排序的核心思想是:由一定规则将带排序的长序列切割成多个子序列,子序列进行内部插入排序,如

排序算法——希尔排序

希尔排序 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法. 该方法因DL.Shell于1959年提出而得名. 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多, 当增量减至1时,整个文件恰被分成一组,算法便终止. 代码实现 void shellsort(int a[],int n) { int gap=0,i=0,temp=0,j=0; for(

排序算法之希尔排序

文章转载自http://www.cnblogs.com/chengxiao/ 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法.希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一.本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现. 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序.希尔排序.选择排序.冒泡排序.归并排序.快速排序.堆排序.基数排序等.用一张图概括: 关于时间复杂度: 1.     平方阶 (O(n2)) 排序各类简单排序:直接插入.直接选择和冒泡排序. 2.     线性对数阶 (O(nlog2n)) 排序快速排序.堆排序和归并排序: 3.     O(n1+§))排序,§ 是介于 0 和 1 之间的常数.希尔排序 4.     线性阶 (O(n)) 排序基数排序,此外还有桶.箱排序. 关于稳定性: 稳定的排序算法:冒泡排序

希尔排序算法实现(1099)

p { margin-bottom: 0.25cm; line-height: 120% } 描述 编程实现希尔排序算法,按照非递减排序,测试数据为整数. input 第一行是待排序数据元素的个数n: 第二行是待排序的数据元素. output 一趟希尔排序后的结果. 样例输入 10 50 36 41 19 23 4 20 18 12 22 样例输出 4 20 18 12 22 50 36 41 19 23 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一