文档章节

常用的排序算法(一)

eatnothing
 eatnothing
发布于 2016/02/14 12:31
字数 1271
阅读 198
收藏 4

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

评论(0)

写完这个排序算法,老板就叫我滚蛋…

(给算法爱好者加星标,修炼编程内功) 最近贴吧有个神奇的帖子,有一程序员网友发称: 然后附上他的排序算法代码,如下: 他也附上了输出结果: 乍一看,没毛病呀~ 发帖人还感叹:「现在的老...

程序员的那些事_
2018/11/09
0
0
03--STL算法(常用算法)

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

osc_bquv1gtr
2019/04/30
1
0
Python 常用排序算法(一)

常用的排序算法 常用的排序算法包含两大类,一类是基础比较模型的,也就是排序的过程,是建立在两个数进行对比得出大小的基础上,这样的排序算法又可以分为两类:一类是基于数组的,一类是基...

osc_bswpz1oi
2018/01/15
7
0
排序算法Java代码实现(一)—— 选择排序

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

osc_ap8rqrw7
2019/08/11
4
0
八种常用排序算法(Java语言描述)

八种常用排序算法(Java语言描述) TOC 各种排序算法的时间、空间复杂度、稳定性对比分析 1、冒泡排序 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要...

osc_9yc7q9oq
03/08
5
0

没有更多内容

加载失败,请刷新页面

加载更多

Python基础-04元组

4.元组     元组的主要特性为: 1.元组在创建之后,具有不可以更改的特性,因此不能直接给元组的元素赋值 2.元组的元素类型可以为任意类型,如字典、字符串、列表等 3.元组常用于在程序的整...

osc_b2jll5m6
36分钟前
22
0
怎么在流程图中插入超链接?迅捷画图带你两步解决!

怎么在流程图中插入超链接?如何在WORD中插入超链接很多人都知道,但是对于陌生的流程图,很多人在进行流程图展示和讲解的时候,都会选择提前将需要的网页打开,然后手动进行更换。 这种手动...

真不莲
37分钟前
19
0
直播中音视频处理的一般流程

数据采集→数据编码→数据传输(流媒体服务器) →解码数据→播放显示 1、数据采集: 摄像机及拾音器收集视频及音频数据,此时得到的为原始数据 涉及技术或协议: 摄像机:CCD、CMOS 拾音器:声...

图玩智能科技
38分钟前
27
0
IntelliJ中的main函数和System.out.println()快捷键

https://blog.csdn.net/shijiebei2009/article/details/44726433

诗书易经
38分钟前
19
0
python 数据可视化实战(1)折线图绘制

  本篇博客新开一个数据分析后的数据可视化的例子讲解,每一篇博客是一个例子。   这节课学习如何绘制一个折线图。题目如下:   代码如下: import matplotlib.pyplot as pltimport m...

osc_xdc1vjza
38分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部