专栏首页JAVAandPython君【Basic algorithm学习笔记】 排序

【Basic algorithm学习笔记】 排序

语言版本:C语言 运行平台:Windows IDE: Dev-C++

一、桶排序(最简单最快)

原理: 其实原理很简单 大白话来讲 就是 先定义很多 容器 即这里形象的表达 为桶,之后每次输入的数字则为选择哪个桶,将对应的 桶中扔一个标志物表示有这个 桶数对应的数字,如果有相同的 就 继续扔一个标志物,最后 如果降序输出则 从大到小 输出有标志物桶的数字,升序类似。

废话不说先上 代码 这里 不会c语言的朋友 可以先去 补习一下c语言知识 估计 认真看 个 一周 足以,也可以用不同语言去 编写 效果一样的

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4int main(int argc, char *argv[])
 5{
 6  int  a[11]; // 数组
 7  int i,j,t; 
 8  for(i=0; i<=10; i++)///M
 9  {
10      a[i] = 0;  // 11个桶的定义  0-10        
11  } 
12  for(i=1; i<=5; i++)////N
13  {
14      scanf("%d",&t); // 输入 5个数字
15      a[t]++;   //对应的 数字的桶进行扔标志物
16  } 
17
18  for(i=0; i<=10; i++)
19  {
20     for(j=1; j<=a[i]; j++)
21     {
22          printf("%d",i);   //从0-10输出 有几个标志物输出几次这个桶代表的数字
23     }
24  }
25  system("PAUSE");    
26  return 0;
27}

输入 5 3 5 2 8

输出 23558 此处 5有两个即a[5] = 2 所以最后标志物为2个最后输出了两个5对应。

说下自由度问题 自由度为O(M+N) M为桶的定义的个数 N为需要排序数的个数 看代码即可得出O(M+N+M+N) = O(M+N)

二、冒泡排序

我相信很多学过c语言的朋友都已经学过这个 排序这里不再赘述 简单说明 贴上代码即可,有不解者可查看c语言的书籍

首先注意冒泡二字,即从他所在位置往一边一直相当于 吐泡泡 ,这里记住泡泡的特性是 一个连着一个 所以这个算法的核心就是如果是n个数则需要用n-1个数即第一层循环为 n-1次 之后从前到尾相邻的比较之后这里假设这里是降幂的话, 如果小的话则 交换 ,一直交换到最后面则为n-i次循环 都是最后一个数 一个个定下来

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4int main(int argc, char *argv[])
 5{
 6  int a[100];
 7  int i,j,t,n;
 8  scanf("%d",&n); //输入数的个数 
 9  for(i=1; i<=n; i++)
10  {
11      scanf("%d",&a[i]);//输入数字 
12  } 
13  //冒泡排序
14  for(i=1; i<n-1; i++)
15  {
16      for(j=1; j<n-i; j++)
17      {
18          if(a[j]<a[j+1])
19          {
20             t = a[j];
21             a[j] = a[j+1];
22             a[j+1] = t;
23          }
24      }
25  } 
26
27  for(i=1; i<=n; i++)
28  {
29     printf("%d ",a[i]);
30  }
31  system("PAUSE");    
32  return 0;
33}

复杂度为 O(N²) 这个复杂度取决于嵌套的循环 并且这个 复杂度已经很高了

三、快速排序

为什么说 叫快速排序,顾名思义, 排序的速度很快。 它的核心思想就是将 最左的数字 记为 基准值 举个例子 假如 6 1 2 7 9 3 4 5 10 8 首先 定下 6为基准值接下来 想达到的目的是 6放在中间 左边都是小于6的右边都是大于6的 从左到右找到 比6大的有 第一个为7 同样从右到左 找到 比6小的 第一个数为 5 两个交换 得到 6 1 2 5 9 3 4 7 10 8 同理 得到 6 1 2 5 4 3 9 7 10 8 将6送到中间去 3 1 2 5 4 6 9 7 10 8 得到之前的目的了把 之后 6的左边 3 1 2 5 4 重复上述的方法 进行 排序(相当于把这五个数看做 一个新的排序将 3 设为基准) 右边 的9 7 10 8 同样 变化过程如下: 3 1 2 5 4 2 1 3 5 4

9 7 10 8 9 7 8 10 8 7 9 10

之后 基准值进入中间区域之后 依次进行以上操作 (其实就是个 递归操作)

最后得到1 2 3 4 5 6 7 8 9 10 上代码

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4int number[101];
 5int n;
 6/*
 7  Name: quickSort(int left, int right)
 8  Author: Che_Hongshu
 9  Date: 06/09/17 13:52
10  Description:  quick sort 
11*/
12
13void quickSort(int left, int right)
14{
15     int baseNumber;// 基准值初始化 
16     int i;
17     int j;
18     int t;
19     if (left > right) // 向右找数 和向左找数 碰到 则结束 找数 
20     {
21         return;
22     }
23     baseNumber = number[left];  // 记住基准值 
24     i = left;
25     j = right;
26     while(i != j)
27     {
28          //  顺序很重要要先从右向左找 
29          while((number[j] >= baseNumber)&&(i<j))
30          {
31               j--;
32          }
33          //   从左向右找 
34          while((number[i] <= baseNumber)&&(i<j))
35          {
36               i++; 
37          } 
38          //  左右 找数没有碰到 
39          if(i<j)
40          {
41              //  比基准值大的数和基准值小的数  交换 
42              t = number[i];
43              number[i] = number[j];
44              number[j] = t;       
45          }
46
47     }
48     // while结束 则  i = j  则 到 中间 所以此时的i为中间的索引  
49     // 中间数字  和  基准值交换  
50      number[left] = number[i];
51      number[i] = baseNumber;
52
53      //递归   左面的 继续 sort   右边的同理 
54      quickSort(left, i-1);
55      quickSort(i+1, right); 
56      return ;
57}
58
59int main(int argc, char *argv[])
60{
61    int  i, j;
62    scanf("%d",&n);
63    for(i=1 ;i<=n; i++)
64    {
65        scanf("%d",&number[i]);
66    }
67    quickSort(1,n);
68    for(i =1; i<=n; i++)
69    {
70        printf("%d   ",number[i]);         
71    }
72     system("PAUSE");    
73}

输入 10 6 1 2 7 9 3 4 5 10 8 输出 1 2 3 4 5 6 7 8 9 10 它的平均时间复杂度O(NlogN)

四、总结

1.快速排序应该是最快的 排序(以上三种) 2.冒泡排序 复杂度太高 浪费时间太多一般不用 但是思想可取 3.时间复杂度 一般用来估计一个算法的 速度,速度对于算法来说 是非常之重要的。 4.如果要是 排序 学生的成绩需要最后输出 学生的名字的话 来个struct 结构体(相当于一个类)就可以搞定 可以 自己 去尝试一下

本文分享自微信公众号 - JAVAandPython君(JAVAandPythonJun)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 23种设计模式之单例模式进阶

    前一篇推文里面我们初步介绍了一下23种设计模式,并且讲解了其中的单例模式的两种情况,今天我们再来讲一讲另外几种单例模式的情况,因为我们都知道懒汉式和饿...

    Python进击者
  • 重建二叉树

    博客地址:https://blog.csdn.net/sunandstarws/article/details/86578080

    Python进击者
  • 详解JAVA包装类、自动拆箱和装箱

    终于有时间给大家来写篇技术推文啦!今天给大家来说说JAVA中的包装类以及自动拆箱和装箱的相关知识!这部分的内容其实也是很重要的,在一些面试题中这部分知识还是会...

    Python进击者
  • LeetCode 119 Pascal's Triangle II

    Given a non-negative index k where k ≤ 33, return the kth index row of the Pasca...

    ShenduCC
  • 洛谷P4719 【模板】动态dp(ddp LCT)

    attack
  • Spring 复盘 | AOP

    Spring AOP 基础 Java 动态代理实现,阅读文章之前,你最好有以下基础:

    一个优秀的废人
  • POJ 2112 Optimal Milking(Floyd+二分+二分图多重匹配)

           题意是有k台挤奶机,c头奶牛,每台挤奶机最多可以给m奶头牛挤奶,1--k是挤奶机的编号,k+1--k+c是奶牛的编号,然后输入一个邻接矩阵,表示它...

    Ch_Zaqdt
  • 1009 产生数 2002年NOIP全国联赛普及组

    009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...

    attack
  • [C语言] 数据结构-预备知识动态内存分配

    int *parr=(int *)malloc(sizeof(int) * len);

    陶士涵
  • Golang leetcode 464. Can I Win.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89175214

    anakinsun

扫码关注云+社区

领取腾讯云代金券