文档章节

常用排序

Ethan-GOGO
 Ethan-GOGO
发布于 2016/10/21 17:33
字数 1118
阅读 1
收藏 0

1.桶排序

四次循环分别循环了m,n,m,n次,所以时间复杂度为O(2*(m+n));

特点:时间复杂度小,但是非常浪费空间,尤其不适用用小数。

void ascending(){
    int a[11],i,j,t;
    
    for (i = 0; i <= 10; i++) {
        a[i] = 0; //将10个桶都清空
    }
    
    for (i = 0; i < 5; i++) {
        printf("输入第%d个小数:",i);
        scanf("%d",&t);
        a[t]++; ////每输入数字,就在数字所在的桶插一个旗子
    }
    
    for (i = 0; i <= 10; i++) {//从左到后数
        for (j = 1; j <= a[i]; j++) {//遍历桶的旗子
            printf("%d",i);
        }
    }
    
}

void descending(){
    
    int arr[1001],i,j,t,n;
    
    for (i = 0; i <= 1000; i++) {
        arr[i] = 0;
    }
    printf("需要排序多少位数字:");
    scanf("%d",&n);
    for (i = 1; i <= n; i++) {
        printf("输入第%d个小数:",i);
        scanf("%d",&t);
        arr[t]++;
    }
    
    for (i = 1000; i >= 0; i--) {//从右到左数

        for (j = 1; j<=arr[i]; j++) {
            printf("%d \n",i);
        }
    }
    
    
}

2.冒泡排序

特点:节省空间,但是双重排序时间复杂度也就是O(N平方),非常高。

void sorting(){

    int arr[100],i,j,t,n;
    printf("需要排序多少位数字:");
    scanf("%d",&n);
    
    //循环读入n个数到数组中
    for (i = 1; i <= n; i++) {
        printf("输入第%d位数字:",i);
        scanf("%d",&arr[i]);
    }
    
    //冒泡排序的核心部分
    for (i = 1; i <= n-1; i++) {//n个数排序,只需进行n-1排序,最后一个数字肯定是最小的
        for (j = 1; j <= n-1; j++) {//和剩下的n-1个数字进行比较
            if (arr[j] > arr[j+1]) {//交换位置,升序降序在这里控制
                t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
    }
    
    for (i = 1; i <= n; i++) {
         printf("%d \n",arr[i]);
        
    }
    
}




//使用结构体,字典排序
struct student{
    char name[21];
    int score;
};

void dicSorting(){
    
    struct student arr[100],t;
    int i,j,n;
    printf("需要排序多少位学生:");
    scanf("%d",&n);
    
    for (i = 1; i <= n; i++) {
        printf("输入第%d位学生信息:",i);
        scanf("%s %d",arr[i].name,&arr[i].score);//name本身是数组类型,数组类型都是以指针形式传入数组的,所以不需要&
    }
    
    //冒泡排序的核心部分
    for (i = 1; i <= n-1; i++) {
        for (j = 1; j <= n-1; j++) {
            if (arr[j].score > arr[j+1].score) {
                t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
    }
    
    for (i = 1; i <= n; i++) {
        printf("%s \n",arr[i].name);
        
    }
    
    
}

3.选择排序

特点:和冒泡选择的查找过程是一样的,但是交换过程不一样。冒泡选择是相邻大于就交互,而选择排序是先记录位置,但排序结束才后交换。时间复杂度稍低于冒泡排序。注意选择排序是不稳定的,举例序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,序列作为vlaue是不影响,如果为key,那么它们的value就会顺序就会变化了(前面key5的value排在后面key为5的后面了)。

    int min;
    //选择排序的核心部分
    for (i = 1; i <= n-1; i++) {
        min = i;//假定arr[i]是最大的数字
        for (j = i+1; j <= n-1; j++) {
            if (arr[j] > arr[min]) {
                min = j;//如果大于,记录j的位置
            }
        }
        if (min != i) {//如果min的位置不位于首位,即i与数字最大的即m位置互换
            t = arr[i];
            arr[i] = arr[min];
            arr[min] = t;
        }
    }

4.快速排序

特点:既解决了桶排序的空间占用,又解决了冒泡的长时间。时间复杂度 最理想 O(nlogn) 最差时间O(n^2)

int a[101],n;


void quickSort(int left,int right){
    
    int i,j,t,temp;
    if (left > right) {//当只剩下2个数字比较的时候,就停止
        return;
    }
    
    temp = a[left];//以最左边的数为基准数
    i = left;
    j = right;
    while (i != j) {//确保不会相遇。
        while (a[j] >= temp && i<j) {//先从右往左找,比基准数小位置
            j--;
        }
        while (a[i] <= temp && i<j) {//再从左往右找,比基准数大位置
            i++;
        }
        //交换数组中这两个位置
        if (i < j) {//如果i和j没有相遇的话
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            
        }
        printf("i:%d,j:%d",i,j);
    }
    
    //此时i == j,两者相遇,将基准数归位到最左边
    a[left] = a[i];
    a[i] = temp;
    
    //继续处理,左右两边
    quickSort(left, i-1);
    quickSort(i+1, right);
    
}



int main(int argc, const char * argv[]) {
    // insert code here...
    
    int i;
    printf("需要排序多少位数字:");
    scanf("%d",&n);
    
    for (i = 1; i <= n; i++) {
        printf("输入第%d位数字:",i);
        scanf("%d",&a[i]);
    }
    
    quickSort(1, n);
    
    for (i = 1; i <= n; i++) {
        printf("%d \n",a[i]);
    }
    
    
    return 0;
}

 

© 著作权归作者所有

Ethan-GOGO
粉丝 13
博文 174
码字总数 82033
作品 0
广州
私信 提问

暂无文章

Java System 类

Java System 类 System 系统类 主要用于获取系统的属性数据。 System类常用的方法: arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 一般 从指定源数...

Hellation
15分钟前
0
0
Nginx源码安装和调优技巧

本文内容 Nginx与apache的对比 实战1:在“腾讯云主机”上源码编译安装Nginx 实战2:Nginx调优之隐藏版本信息防止黑客扫描识别漏洞 实战3:设置网页缓存 实验环境: 使用RHEL6.5/centos6.5 6...

寰宇01
18分钟前
0
0
linux jenkins添加windows节点,实现自动化部署

背景: 要基于jenkins的做代码自动更新部署,现状是jenkins在linux上,目标服务器的tomcat在windows上,如何将代码从linux发送到windows未找到合适方案,并且后续如何远程调用执行windows批处...

shzwork
24分钟前
0
0
MySQL同表更新与查询冲突

MySQL version: 5.5 MySQL报错: You can't specify target table 'document_basic' for update in FROM clause 原因:MySQL不支持对同表同时更新+查询 解决方案:查询结果使用中间表接收,或......

Hzhodor
25分钟前
0
0
最长不重复字符子串

给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。 这个有点像最长前缀匹配,简单的想到的就是暴力搜索一下,得到最大的子串,这样就是时间复杂度比较大,可以看到里面有两个f...

woshixin
29分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部