38ccc67ddac6796ccee896b5a5b0f331
Go 语言算法实战-各种排序算法

冒泡排序

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

作为最简单的排序算法之一,冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1、算法步骤
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
动图演示

动图演示

Runtime(时间复杂度):

  • Average平均: O(N^2)
  • Worst最差: O(N^2)
  • 稳定性:稳定

空间复杂度 O(1)

package main
import "fmt"
func bsort(a []int) {
    for i := 0; i < len(a); i++ {
        for j := 1; j < len(a)-i; j++ {
            if a[j] < a[j-1] {
                a[j], a[j-1] = a[j-1], a[j]
            }
        }
    }
}
func main() {
    b := [...]int{8, 7, 5, 4, 3, 10, 15}
    bsort(b[:])
    fmt.Println(b)
}

快速排序

快速排序有几种实现方式,不过核心操作是选出一个基点比较值,通过一次遍历得出比它小的A和比它大的B无序数组,
然后通过递归方式分别操作A与B,并将低值A结果放到基点左边,高值B结果放到基点右边。
全过程都是为了基准点pivot归位。
Runtime(时间复杂度):

  • Worst:O(n ^ 2)
  • Best:O(n lg n)
  • Average:O(n lg n) 或者O(n*log2n)

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

1、 算法步骤
从数列中挑出一个元素,称为 “基准”(pivot);

2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
```
package main
import "fmt"
func qsort(a []int, left, right int) {
if left >= right {
return
}
val := a[left]
k := left
//确定val所在的位置
for i := left + 1; i <= right; i++ {
if a[i] < val {
a[k] = a[i]

top Created with Sketch.