文档章节

常用排序算法(二)

eatnothing
 eatnothing
发布于 2016/02/16 10:49
字数 531
阅读 38
收藏 1
点赞 1
评论 0

####希尔排序

  • 时间复杂度:
  • 空间复杂度:
  • method:将需要排序的的序列划分为若干个较小的序列,对这些序列进行直接插入排序.
void shellsort(int A[],int n);
void shellsort(int A[],int n){

    int d,i,x,j;
    d = n /2 ;
    while(d>=1){
        for(i =d ;i<n;i++){
            x = A[i];
            j = i-d;
            while (j>=0&&A[j]>x) {
                A[j+d] = A[j];
                j = j -d;
            }
            A[j+d] = x;
        }
        d = d /2;
    }   
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int A[9] = {12,34,54,2,1,4,3,5,6};
    shellsort(A, 9);

    for(int i = 0;i<9;i++){
        printf("%d",A[i]);
    }
    return 0;
}

####堆排序法

  • 堆是一个完全二叉树,首先
  • 1:将无序的数据构成堆,(既用无序的数据生成满足堆定义的完全二叉树)
  • 2:利用堆排序,(既将上一步生成的堆输出,得到排序后的有序数据)
  • 时间复杂度:o(nlog2^n)
  • 空间复杂度:o(1)
void HeapAdjust(int A[] , int s ,int n){
    int j,t;
    while(2*s+1<n){
        j = 2*s +1;
        if((j+1)<n){
            if(A[j]<A[j+1])
                j++;
        }
        if(A[s]<A[j]){
            t    = A[s];
            A[s] = A[j];
            A[j] = t;
            s = j;
        }else break;

    }

}
void HeapSort(int A[],int  n){

    int t ,i;
    int j;
    for(i = n / 2 -1;i >= 0; --i){
        HeapAdjust(A,i,n);
    }
    for(i = n - 1;i > 0;i--){
        t    = A[0];
        A[0] = A[i];
        A[i] = t;
        HeapAdjust(A,0,i);

    }

}

####桶排序

  • 桶排序是稳定的
  • 桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
  • 桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法
//获得桶排序的MAX值
int GetMaxVal(int * arr,int len){

    int maxVal = arr[0];
    for(int i = 1; i<len;i++){
        if(arr[i]>maxVal){
            maxVal = arr[i];
        }

    }
    return maxVal;
}
void BucketSort(int * arr,int len){
    int tempArrlen = GetMaxVal(arr, len)+1;
    int tempArr[tempArrlen];    //获得空桶大小
    int i,j;
    for(i =0;i<tempArrlen;i++){     //空桶初始化
        tempArr[i] = 0;
    }
    for(i = 0;i<len;i++){
        tempArr[arr[i]]++;
    }
    for(i=0,j=0;i<tempArrlen;i++){

        while(tempArr[i]!=0){
            arr[j] = i;
            j++;
            tempArr[i]--;

        }
    }

}
int main(int argc, const char * argv[]) {
    // insert code here...

    int A[10] = {3,123,4,4,1,23,534,21,12,4};

    BucketSort(A, 10);

    for(int i =0;i<10;i++){

        printf("%d,",A[i]);
    }
    printf("Hello, World!\n");
    return 0;
}

© 著作权归作者所有

共有 人打赏支持
eatnothing
粉丝 36
博文 128
码字总数 68736
作品 0
昌平
程序员
各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(六)—— 查找算法 (均已测试通过) =================================================================== 1、简单查找 在一组无序数列中,查找特定某个数值,并返...

长平狐
2013/01/06
75
0
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
06/05
0
0
各种基本算法实现小结(二)—— 堆 栈

各种基本算法实现小结(二)—— 堆 栈 (均已测试通过) ============================================================== 栈——数组实现 测试环境:Win - TC #include char stack[512];i...

长平狐
2013/01/06
238
0
排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien
2016/06/17
41
0
常用数据结构以及数据结构的排序算法

数组 (Array)   在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可...

带梦想一7飞
2012/09/13
0
0
Python数据结构总结篇

数据结构篇主要是阅读[Problem Solving with Python](http://interactivepython.org/courselib/static/pythonds/index.html)时写下的阅读记录,当然,也结合了部分[算法导论](http://en.wik...

宅男潇涧
2014/07/06
544
0
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
经典排序之 插入排序

Author: bakari Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为插入排序。 插入排序有三种形式: 转载引用请...

chambai
2012/08/11
0
0
面试常考的常用数据结构与算法【简】

数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的时间内考察一个人...

anlve
05/01
0
0
Website collections

一. Framework about. 1. Spring Framework (1)http://projects.spring.io/spring-framework/ Spring的官方网站,包括 Spring Framework reference documentation 以及 API (2)http://re......

pradosoul
2015/10/20
106
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

自定义OkHttp的UA

背景 上次的问题很明显 由于我们的ua清一色OkHttp导致快速定位到内部应用。 既然如此我们是否考虑可以在UA上做点手脚。 自定义我们的UA呢??? 分析 首先UA在 均为okhttp/3.2.0 大概率是由于...

Mr_Qi
21分钟前
0
0
【scikit-learn】01:使用案例对sklearn库进行简单介绍

sklearn学习笔记:Quick Start 源地址:http://scikit-learn.org/stable/tutorial/basic/tutorial.html # -*-coding:utf-8-*-''' Author:kevinelstri Datetime:2017.2.16'''......

wangxuwei
25分钟前
0
0
Linux Kernel 4.16 系列停止维护,用户应升级至 4.17

知名 Linux 内核维护人员兼开发人员 Greg Kroah-Hartman 近日在发布 4.16.18 版本的同时,宣布这是 4.16 系列的最后一个维护版本,强烈建议用户立即升级至 4.17 系列。 Linux 4.16 于 2018 年...

问题终结者
27分钟前
0
0
Apache配置时.htaccess失效不起作用的原因分析

.htaccess 失效的原因 1. 重写规则有问题,检查自己的重写规则 2.Apache配置问题,配置中没有配置启用 rewrite a2enmod rewrite 3.网站配置文件没有启用配置需要配置 000-default.conf <Dire...

TU-DESGIN
47分钟前
1
0
两个求最大公约数C/C++算法实现

#include<stdio.h> #include<time.h> #include <iostream>using namespace std;//求最大公约数 LCD(Largest Common Division)//短除法 //m=8251, n=6105; int LCD_ShortDiv(int m, ......

失落的艺术
53分钟前
1
0
QueryPerformanceCounter

windows的Sleep函数,睡眠线程指定毫秒数,可以用来做毫秒延时。 对于微秒延时,没有一个现成的函数,但是可以通过 QueryPerformanceFrequency QueryPerformanceCounter 来间接实现。原理就是...

开飞色
今天
1
0
log4j2使用AsyncRoot不显示行号问题处理

<AsyncRoot level="info" includeLocation="true"> <AppenderRef ref="File"/></AsyncRoot><!--1.异步logger,还需要在pom.xml中添加disruptor的依赖。2.includeLocation结合异......

小翔
今天
3
0
安卓手机上 K 歌,声音延迟怎么解决?

这篇文章可以为你提供一个解决录音和播放同步问题的思路,而且解决了声音从手机传输到耳机上有延时的问题。 初识音频 在开始之前,我先简单介绍一下音频相关的基础知识,方便下文理解。 我们...

编辑部的故事
今天
2
0
使用token实现在有效期内APP自动登录功能

使用token实现在有效期内APP自动登录功能 http://sevennight.cc/2016/07/19/auto_login_impl.html

风云海滩
今天
2
0
Spring Boot集成RabbitMQ发送接收JSON

默认情况下RabbitMQ发送的消息是转换为字节码,这里介绍一下如何发送JSON数据。 ObjectMapper 最简单发送JSON数据的方式是把对象使用ObjectMapper等JSON工具类把对象转换为JSON格式,然后发送...

小致dad
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部