【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 结构体（相当于一个类）就可以搞定 可以 自己 去尝试一下
腾讯云开发者
