文档章节

常用的排序算法(一)

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

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
昌平
程序员
涨姿势,图文带你了解 8 大排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部排序算法有...

Java架构
07/25
0
0
各种基本算法实现小结(六)—— 查找算法

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

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

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

Corwien
2016/06/17
41
0
8个常用算法的超常剖析

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

gitchat
2017/11/30
0
0
java排序之快速排序、归并排序、基数排序

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

野小疯
06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

C++ gflags

###定义参数 gflags主要支持的参数类型包括bool,int32, int64, uint64, double, string等,定义参数通过DEFINE_type宏实现, 该宏的三个参数含义分别为命令行参数名,参数默认值,以及参数的...

SibylY
17分钟前
0
0
intellij IDEA Properties中文unicode转码问题

在IDEA中创建了properties文件,发现默认中文不会自动进行unicode转码。如下 在project settings - File Encoding,在标红的选项上打上勾,确定即可 效果图如下: unicode转码后效果...

muzi1994
18分钟前
0
0
Java IO类库之PipedWriter

一、PipedWriter介绍 PipedWriter是字符管道输出流,继承自Writer,功能与PipedOutputStream类似,通过与PipedReader组合使用实现类似管道的功能,在多线程环境下,一个线程使用PipedWriter...

老韭菜
22分钟前
0
0
精简分页组件(手写)

需要引入CSS(没错就是这4行) .pagelist { text-align: center; color: #666; width: 100%; clear: both; margin: 20px 0; padding-top: 20px }.pagelist a { color: #666; margin: 0 2px;......

AK灬
23分钟前
3
0
29 岁成为阿里巴巴 P8,工作前 5 年完成晋升 3 连跳,他如何做到?

泡泡是我的好朋友。今年 31 岁,毕业后就进了阿里巴巴,工作五年内从 P4 晋升至 P6、P7、P8。 和他很少聊到工作,但总觉得他有很棒的职场心得,应该分享出来,于是有了这次采访。希望对职场新...

Java填坑之路
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部