文档章节

常用的排序算法(一)

eatnothing
 eatnothing
发布于 2016/02/14 12:31
字数 1271
阅读 184
收藏 3
点赞 1
评论 0

Date: 2016-02-14 #####排序算法的学习 ####冒泡排序

  • 时间复杂度:当顺序为正序的时候,为最好状态时间复杂度为O(N),平均时间复杂的为O(N^2)
  • 因为没有创建新的存储结构所以空间复杂度为O(1)
  • 冒泡排序是一种稳定的排序算法

#include <stdio.h>
void Bubble_sort(int A[],int n);

void Bubble_sort(int A[],int n){
    int i,j,temp;
    for(i= 0 ;i < n - 1 ;i++){
        for(j = 0;j< n -1 - i;j++){
            if(A[j] > A[j+1]){
                temp = A[j+1];
                A[j+1] = A[j];
                A[j] = temp;

            }

        }
    }

}

int main(int argc, const char * argv[]) {

    int A[7]={3,1,2,4,6,8,1};

    Bubble_sort(A, 7);

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

    }

}

####改进的冒泡排序

  • 使用冒泡排序对N个数据进行排序,一共需要进行n-1次比较,本来是正常顺序的数据也需要进行n-1次排序,所以当判断所有的数据为有序的时候不在进行排序直接跳出循环,
void Bubble_sort(int A[],int n){
    int i,j,temp,flag=0;
    for(i= 0 ;i < n - 1 ;i++){
        for(j = 0;j< n -1 - i;j++){
            if(A[j] > A[j+1]){
                temp = A[j+1];
                A[j+1] = A[j];
                A[j] = temp;
                flag = 1;

            }
        }
        if(flag== 0){
            break;
        }else{
            flag = 0;
        }
    }

}

####快速排序法

  • 算法时间复杂度:最差时间为(O(n^2))),平均时间复杂度为O(n*log2n)
  • 算法空间复杂度:O(log2n)~O(n)
  • 快速排序法是通过一遍排序将需要排序的数据分为两部分,使其中一部分数据比另一部分数据小,然后在分别对这两部分数据进行这种排序,直到每个部分为空或者只含有一个数的时候,排序结束
  • 快速排序是一种分治策略,将大批数据逐步分解,可以使用递归的方式便携程序

method: 变量left保存数组最小序号0,数组right保存数组最大(序号)长度n,在变量base 中保存A[0]为基准,从数组右侧开始逐个取出元素与base比较,如果小于base的值则将该数保存到A[left]中(A[0])元素中,接下来从数组左侧开始逐个取出元素与base比较知道找到比base大的数据,(left随着比较的位数自增),将这个比基准大的数存到A[right]中,接下来递归进行同样的操作

int Division(int a[],int left,int right){
    int base = a[left];     //取左侧元素为基准元素
    while(left<right){      //左侧元素的序号小于右侧
    while (left<right&&a[right]>base)  //当序号小于右侧并且数组末尾的值大于基准,则向前挪一位(right-1)
        --right;
        a[left] = a[right];         //当找到了右侧比基准小的数的时候令A[LEFT] 为右侧的值
    while(left<right&&a[left]<base)     //当序号小于右侧时候,如果左侧的数值比基准小则向后挪一位(left+1)
        ++left;
        a[right] = a[left];             //当找到左侧比基准大的数字的时候,让这个数字为数组的末尾元素()
        }
    a[left] = base;             //保存基准数
    return left;        //返回左侧的值
}

void QuickSort(int a[],int left,int right){

    int i, j;
    if(left<right){
        i = Division(a, left, right);
        QuickSort(a,left,i-1);  //左侧的数进行递归排序
        QuickSort(a,i+1,right);     //右侧的数进行递归排序
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int A[10]={94,84,54,80,62,83,37,24,67,29};

    QuickSort(A,0,9);

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

####简单选择排序算法

  • 时间复杂度:O(n2)
  • 空间复杂的:O(1) method:对N个记录进行扫描,选择最小的记录,将其输出,接着在剩下的N-1个记录中扫描,选择最小的输出,不断重复这个过程,直到只剩一个记录为止
void selectSort(int A[],int n );

void selectSort(int A[],int n){
    int i,j,k,t;
    for(i = 0 ;i< n -1 ;i++){   //n-1位开始比较
        k = i;                  //获取当前位数
        for(j =i+1 ;j< n;j++){
            if(A[k]>A[j]){      //如果当前位数大于数组[K,N]的任何一位则,当前该数为[K,N]中最小的数
                k = j;
            }
        }
        t = A[i];       //进行交换
        A[i] =  A[k];
        A[k] = t;

    }
}
int main(int argc, const char * argv[]) {
    int A[8]={15,2,8,3,1,9,7,6};
    selectSort(A, 8);
    for(int i =0 ;i<8;i++){
        printf("%d",A[i]);
    }
}

####直接插入排序法

  • 时间复杂度:O(N^2)
  • 空间复杂度:O(1)
  • method:通过构建有序序列,对于未排序的数据,在已排序的序列中从后向前扫描,找到相应的位置并插入该数据,使数据形成有序队列
void insertSort(int A[],int n){
    int i,t,j;
    for(i = 1 ;i<n;i++){
        t= A[i];        //取出一个未排序的数据
        for(j=i-1;j>=0&&t<A[j];j--)     //在排序序列查找数据
            A[j+1] = A[j];              //向后移动数据
        A[j+1] = t;
    }

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

    int A[6]={3,1,8,3,2,5};
    insertSort(A, 6);
    for(int i =0 ;i<6;i++){
        printf("%d",A[i]);
    }
    printf("Hello, World!\n");
    return 0;
}

© 著作权归作者所有

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

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

长平狐 ⋅ 2013/01/06 ⋅ 0

排序算法-09-冒泡排序(Bubble Sort)

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

Corwien ⋅ 2016/06/17 ⋅ 0

8个常用算法的超常剖析

本文来自作者 jack 在 GitChat 上分享「最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析」,「阅读原文」查看交流实录 「文末高能」 「更多同类话题」 「查看全部话题」 编辑 | ...

gitchat ⋅ 2017/11/30 ⋅ 0

java排序之快速排序、归并排序、基数排序

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

野小疯 ⋅ 06/05 ⋅ 0

最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

作者:jack 1. 关于排序 很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如: 数据库脚本,如MSSql, MySq...

小数点 ⋅ 2017/12/04 ⋅ 0

Java程序员的日常—— Arrays工具类的使用

这个类在日常的开发中,还是非常常用的。今天就总结一下Arrays工具类的常用方法。最常用的就是asList,sort,toStream,equals,copyOf了。另外可以深入学习下Arrays的排序算法,这个还是非常有用...

青夜之衫 ⋅ 2017/12/05 ⋅ 0

java冒泡,选择排序及折半(二分)查找

这里选择2个比较常用的排序,简单结合代码了解下,实际开发中,并不需要使用自己的排序算法. 冒泡排序 for( 控制循环比较轮次数组长度-1 次 ){ for(两两比较次数 数组长度-1 -上层循环参数){ if...

qq_28327795 ⋅ 2017/12/01 ⋅ 0

内部排序算法的实现与比较-数据结构课程设计

内部排序算法的实现与比较 1) 问题描述 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移...

zhagoodwell ⋅ 2017/11/06 ⋅ 0

排序(sort)

1、定义 排序 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。 输出:R...

野渡书生 ⋅ 2016/04/29 ⋅ 0

图书馆刘大妈除了要帮我找对象,还教我排序算法

在图书馆偶遇 快速排序算法 一次关于排序的偶遇 今天,在图书馆发生了一件事。 图书馆书架 新来的志愿者小王被安排将归还的书整理回书架,初次被委派工作的小王瞬间充满热情。然而。。。 面对...

超级数学建模 ⋅ 03/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

spring Email

使用spring发Email其实就是使用spring自己封装携带的一个javamail.JavaMailSenderImpl类而已。这个类可以当一个普通的java对象来使用,也可以通过把它配置变成spring Bean的方式然后注入使用...

BobwithB ⋅ 23分钟前 ⋅ 0

spark 整理的一些知识

Spark 知识点 请描述spark RDD原理与特征? RDD全称是resilient distributed dataset(具有弹性的分布式数据集)。一个RDD仅仅是一个分布式的元素集合。在Spark中,所有工作都表示为创建新的...

tuoleisi77 ⋅ 26分钟前 ⋅ 0

思考

时间一天天过感觉自己有在成长吗?最怕的是时光匆匆而过,自己没有收获!下面总结下最近自己的思考。 认识自己 认识另一个自己,人们常说要虚心听取别人意见和建议。然而人往往是很难做到的,...

hello_hp ⋅ 27分钟前 ⋅ 0

IT行业的变革就像世界杯德国对战墨西哥一样难以预测[图]

最近在观看世界杯,尤其是昨天的比赛,上一届卫冕冠军德国队居然0:1告负墨西哥,这创造了历史,首先是墨西哥从来没赢过德国队,其次是德国队36年来首站没输过,再差也是打平,而这次,德国队...

原创小博客 ⋅ 46分钟前 ⋅ 0

解决CentOS6、7,/etc/sysconfig/下没有iptables的问题

一、Centos 6版本解决办法: 1.任意运行一条iptables防火墙规则配置命令: iptables -P OUTPUT ACCEPT 2.对iptables服务进行保存: service iptables save 3.重启iptables服务: service ...

寰宇01 ⋅ 56分钟前 ⋅ 2

数据库备份和恢复

备份:mysqldump -u root -p 数据库>磁盘路径 恢复:mysql -u root -p 数据库<sql脚本的磁盘路径

anlve ⋅ 今天 ⋅ 0

发生了什么?Linus 又发怒了?

在一个 Linux 内核 4.18-rc1 的 Pull Request 中,开发者 Andy Shevchenko 表示其在对设备属性框架进行更新时,移除了 union 别名,这引发了 Linus 的暴怒。 这一次 Linus Torvalds 发怒的原...

问题终结者 ⋅ 今天 ⋅ 0

在树莓派上搭建一个maven仓库

在树莓派上搭建一个maven仓库 20180618 lambo init 项目说明 家里有台树莓派性能太慢。想搭建一个maven私服, 使用nexus或者 jfrog-artifactory 运行的够呛。怎么办呢,手写一个吧.所在这个...

林小宝 ⋅ 今天 ⋅ 0

Spring发展历程总结

转自与 https://www.cnblogs.com/RunForLove/p/4641672.html 目前很多公司的架构,从Struts2迁移到了SpringMVC。你有想过为什么不使用Servlet+JSP来构建Java web项目,而是采用SpringMVC呢?...

onedotdot ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部