文档章节

常用排序算法(二)

eatnothing
 eatnothing
发布于 2016/02/16 10:49
字数 531
阅读 39
收藏 1

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

####希尔排序

  • 时间复杂度:
  • 空间复杂度:
  • 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
粉丝 39
博文 128
码字总数 68736
作品 0
昌平
程序员
私信 提问
加载中

评论(0)

03--STL算法(常用算法)

一:常用的查找算法 (一)adjacent_find():邻接查找 在iterator对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的迭代器。否则返回past-the-end vector<int> ...

osc_bquv1gtr
2019/04/30
1
0
排序算法Java代码实现(一)—— 选择排序

以下几篇随笔都是记录的我实现八大排序的代码,主要是贴出代码吧,讲解什么的都没有,主要是为了方便我自己复习,哈哈,如果看不明白,也不要说我坑哦! 本片分为两部分代码: 常用方法封装 ...

osc_ap8rqrw7
2019/08/11
4
0
各种基本算法实现小结(六)—— 查找算法

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

长平狐
2013/01/06
148
0
(笔记整合)冒泡排序、插入排序、选择排序

一、排序方法与复杂度归类 1.几种最经典、最常用的排序方法:冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。 2.复杂度归类 冒泡排序、插入排序、选择排序...

JokerDa
04/01
0
0
软件设计师【数据结构与算法基础知识及相关试题】

一.图          二.树                三.排序算法   1.稳定排序算法&不稳定排序算法      2.插入排序         3.选择排序      4.交换排序         ...

osc_foipyam7
2018/07/21
2
0

没有更多内容

加载失败,请刷新页面

加载更多

在Git存储库中查找并恢复已删除的文件 - Find and restore a deleted file in a Git repository

问题: Say I'm in a Git repository. 假设我在Git存储库中。 I delete a file and commit that change. 我删除文件并提交更改。 I continue working and make some more commits. 我继续工作......

javail
15分钟前
15
0
基于Centos7系统一键部署EFK服务

最近平台EFK版本均作了升级,平台采用EFK(ElasticSearch-7.6.2 + FileBeat-7.6.2 + Kibana-7.6.2)架构。这里建议三个组件主次版本保持一致。考虑到服务器比较多,所以写成脚本来批量部署。 ...

linuxprobe2020
今天
23
0
检查键是否存在于JavaScript对象中? - Checking if a key exists in a JavaScript object?

问题: How do I check if a particular key exists in a JavaScript object or array? 如何检查JavaScript对象或数组中是否存在特定键? If a key doesn't exist, and I try to access it, ......

fyin1314
今天
27
0
jasypt-spring-boot提示Failed to bind properties

1 问题描述 在Spring Boot中使用jasypt-spring-boot进行加密,但是提示: Description:Failed to bind properties under 'spring.datasource.password' to java.lang.String: Reason:......

氷泠
今天
29
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部