第三篇：排序
目录
一、选择排序
选择排序是一种排序算法
浏览一遍所有数据，从里面挑出最大的，再浏览一遍，挑出第二大的，如果有n个元素，那么要浏览N变，每次都要浏览N个元素 因此是O(n^2)
如下图：
显然这属于比较笨的那一种算法，有人问，每次都可以少浏览一个元素啊。为什么不是n，n-1，n-2，…，1
这样运行时间不就少了吗？如果是这样，平均来看，每次浏览n/2，那么就是O(n^2/2)，考虑之前提及一般会省略常数。
二、快速排序
刚才的排序方法笨笨的，这里介绍一个快一些的算法
用简单查询 vs 二分查询一样。一个一个来总是最笨的，可以选择分批处理，快速排序也是大致思路。
步骤
-
首先选择一个基准值
-
接下来对两边的子数组进行排序，同样是拆分
具体从笔记本上再整理。
想法很简单，如何实现呢？
整个是一个重复过程，可以通过递归，见递归那一章
那么快速排序速度有多快呢？
如果每次基准值都是第一个，那要把所有元素都过一遍 ==> O(n) ==> O(nn)，如果从中间选，则一半一半，==> O(logn) ==> O(nlogn)
最常用的排序。
桶排序浪费空间，冒泡排序太慢。
冒泡排序是顺次两两排序，有没有更聪明的方法呢？
可以找一个标杆（基准值）
快速排序每一轮就是将这一轮的基准数归位，直到所有数都归位。之所以快，因为交换是跳跃式的。
因为快，所以叫快速排序。
三、合并排序
四、插入排序（insert sort）
举个例子了解插入排序：
写成代码如下：
for i in range(1,n):
key = A[i] # 按顺序依次指定key，从第二个开始
j = i - 1 # 先和前面一个比较
while j >= 0 and A[j] > key: # 中止条件，不断和前一个比较，直到前一个比key更小。
A[j+1]=A[j] # 如果key比前一个小，就让大的往后挪一位，小的往前挪一位。
j = j -1
A[j+1] = key
while 循环里是key找位置的过程
这样的过程是不断的将key插入序列中，当key插完了，序列也排序完成，因此叫做插入排序。
存在一个常量，每次循环这个常量不变，常量就是数组已经被排序过的这部分，
每次循环的目的是完成增量，使已排序的部分长度增加1
实现方法是提取当前循环中位置为j的数字键。这样一步步把前面的值抄到下一位上，知道找到此键合适的位置，然后将此键插入。
在数组中移动元素的位置，持续复制这些元素直到我们找到它们的适当位置，并将它们放置到这些位置中去。
四、桶排序
基本思想是：
举个例子了解桶排序：
对序列：5,3,5,2,8，从大到小排序
~~ 1，生成长度为11的数组，a[0] ~ a[10]
2，将a[0] ~ a[10]的值初始化为0，a[0]=0，就代表没人得0分，a[i]=0，就代表没人得i分。
3，处理并统计每个人的得分
4，将此数组输出，数值为n的输出n次，则得：2,3,5,5,8
对N个数进行排序就至少需要N个同。每个桶的作用其实就是“标记”每个数出现的次数
那时间复杂度是多少呢？
假设有M个数，N个桶，首先需要遍历每个桶(N)，判断要不要插旗子，然后把要插旗子的M个桶输出，所以总共是M+N，即O(M+N)。（重新梳理这部分）
到这一步已经可以看出，速度还不错，但是假设数字范围0-1000，但就5个数，那要是生成长度为1001的数组，只用了5个位置，余下的996个空间都浪费了
其次，只能处理整数
而且只到这一步，也只能输出排了序的分数，无法输出排了序的人，还需要把人和分数对应起来
五、冒泡排序
基本思想：每次比较两个相邻的元素，如果顺序错误，就把它们交换过来
像气泡一样，一步一步往后“翻滚”，所以叫冒泡排序
冒泡排序最糟糕的情形：每一趟只能确定将一位数归位
1,如果有n个数进行排序，只需将n-1个数归位，也就是要进行n-1趟操作
2,每一趟都需要从第1位开始进行相邻两个数的比较，直到最后一个尚未归位的数
时间复杂度为O(n^2)
六、选择排序
七、计数排序
八、基数排序
九、归并排序
十、堆排序
二叉树
[1] 算法图解 Aditya Bhargava (作者) 袁国忠 (译者)