快速入门 排序算法
排序算法
原文:https://github.com/googege/AMAC/tree/master/basic/7
原文处有实现代码，如果有bug欢迎pull request。
有一些排序算法例如快排我写的非常容易，估计不是很容易看懂，你们可以在github上找到代码，我认为一个好的程序员，看代码比看字更快。
经典排序算法的分类（按照时间复杂度）
-
O(n^2) : 冒泡 插入 选择 这三个最好的就是 插入排序，速度最快。
-
O(nlogn) : 希尔排序 快排 并归 堆排序（堆排序放到了堆那里来说明，这里就不谈了）
-
O(n) : 桶 计数 基数
重要指标
-
稳定性 ： 相同的数字 排序前后时候发生变化 ，非常重要，通常我们需要相同的排序的时候不动他们，还是按照以前的顺序。
-
时间复杂度： 平均的 最好的 最坏的 对于比较小量的也要注意它的常数低次项式 以及所有的参数，因为数量级小，所以要注意这些
-
样本的排序度 也会对最后的结果产生很大的影响
-
是否使用了空间O(1) 是否开辟了额外的空间
-
交换的次数 比较的次数（只对于比较合交换的算法）
冒泡
for i := 0 ; i < n ; i++ {
for j := 0; j < n-i-1;j++ {
if a[j] > a[j+1] {
a[j],a[j+1] = a[j+1],a[j] 每次都是跟相邻的数据进行交换
}
}
}
//改进
L:
for i := 0 ; i < n ; i++ {
b := false
for j := 0; j < n-i-1;j++ {
if a[j] > a[j+1] {
a[j],a[j+1] = a[j+1],a[j] 每次都是跟相邻的数据进行交换
b = true
}
if !b {
break L // 这样就可以确保如果已经排序完成了继续排序的尴尬
}
}
优化的一点就是 判断 这次冒泡的过程中是否有过换位，如果这一次整个过程中都没有换位，可以证明已经结束了，直接break出来即可。
选择排序
for i := 0;i < len(x) -1;i++ {
min := i
for j := i+1;j < len(x);j++{
if x[min] > x[j]{
min = j // 找到最小值的索引
}
}
x[min],x[i] = x[i],x[min] //然后 让 此时的 i这个值跟 min调换位置，这样就成功的把 min加到了队尾
}
因为选择排序，在前面拍好的序列后加上后面最小的那个数字，所以 每次找到的最小，如果是一样的话 这些最小就会跟之前 按照相反的方向排列
故 并不稳定。 当然时间复杂度也是 n ^2 空间复杂度依然是1 因为没有其它的空间占用
插入排序
for i := 1;i < len(x);i++ {
value := x[i]
for j := i-1;j >=0;j-- {
if x[j] > value {
x[j+1] = x[j] // 这是为了 往后转移
}else{
break //这是为了确保j刚好是在 插入的那个位置
}
}
x[j+1] = value //在这个空位置 插入即可。
}
因为 插入排序是比值，如果是一样大的值，那么就不会插到这个位置，只会不动，所以说是 稳定的。 当然 空间复杂度也是1
为什么 插入排序和冒泡法时间复杂度都是 n^2 时间为什么不一样
答案： 因为 冒泡法需要 x[i],x[i+1] = x[j+1],x[j] 虽然go可以这么写 但是 这其实是3个步骤 ，但是插入排序只需要 x[j+1] = x[j]这是一个步骤
所以理论上 插入排序要比冒泡法 快3倍以上。或者是更快。
希尔排序
希尔排序是另一种 插入排序 它的平均时间复杂度是nlogn 这个log 取决于把每一份分成了多少。
并归排序
中心思想就是 分治，它是将所有的数据一点一点的分为一半一半，然后直到分成了一个一个，再合并 合并的时候就是分开的反向，然后就
一步一步的向上合并就ok了。
举个例子：
1，543，33，55，3，55，23，55，3
1 543 33 55 和 3 55 23 55 3
1 543和 33 55 和 3 55 和 23 55 3
1和543 和 33和55 和 3 和55 和 23 和55 3
1和543 和 33和55 和 3 和55 和 23 和55和3
现在开始合并了
1 543 和 33 55 和 3 55 和 3 23 55
1 33 55 543 和 3 3 23 55 55
结局是： 1 3 3 23 33 55 55 55 543
这就是整个的过程，先分治然后分别的合并然后最后全部排列后再合并。
它的空间复杂度是 N 时间复杂度就是 分治的时候的 logn 乘以 merge的时候的比较的n所以结果就是 nlogn
快速排序
举个例子
1 8 43 4 1221
使用最左边的作为标记值
比1 小的放在左边，比1大的放在右边
1 8 43 4 1221
1 4 8 43 1221
1 4 8 43 1221
这样就排好了。
基数
其实基数排序的基本算法是:按照数字的数位进行分解，先比较最高位，然后比较次高位，依次类推
桶
桶排序的特点是，将所有的数据按照区间分到每个桶里，这其实是计数排序的一种通解，所以在每个桶内再通过某个排序即可例如快排
桶排序用在的地方比如说 超大量的数据，然后没办法同时给导入到内存中，我们可以按照区间一部分一部分的导入，这样就可以排序
在go中我们还可以分为不同的桶然后使用多协程然后进行同时排序提高速度。
计数
计数排序，是已经知道排序数据的左右，以及数据的跨度不是很大，举个例子 全校的成绩（在没有0.5的前提下），那么也就分为100数字即可
所以 0 1 2 3 ... 99 100 按照这些数据将数据填进去，然后就可以算出每个数据一共拥有多少人数
emm 这种排序算法有很大的局限性啦...
func CountingSort(arr []int,maxValue int)[]int{
bucket := make([]int,maxValue+1)
for i := 0;i < len(arr);i++ {
bucket[arr[i]]++
}
sortedIndex := 0
for j := 0; j < len(bucket); j++ {
for bucket[j] > 0 {
arr[sortedIndex] = j
sortedIndex ++
bucket[j] --
}
}
return arr
}
排序算法的优化
- 快排中如果分区点选的不好，很容易形成n^2 这种非常差的表现，所以选择分区点就很重要常见的我们可以这么几点的优化
-
随机 随机的在区间中选择
-
选择 开头 中间 结尾，三个数的中位数或者 更多数的中位数
-
递归的深度限制
-
使用手动模拟栈的调用来规避掉递归带来的栈的调用过多的现象。
-
