本片文章主要描述一些奇特的排序算法和常用的排序算法。 因为排序算法在网上基本都可以找见， 而且随便一找都很全面， 也都可以在维基百科上找见算法图解， 因此， 这篇文章不会对算法的细节做详细介绍， 主要是讲下算法步骤， 并且用go语言实现。
排序算法是非常重要的， 虽然每个语言基本都会自带排序函数， 大多数人都是直接使用的。 但是， 也不知道为了啥， 每次面试的时候会有人问排序算法， 有的时候你可能知道这个怎么排， 但是你又忘了它叫什么排序， 因此， 整理了一下几种常用的排序方法是非常有必要的， 由于go语言天生的并发性， 所以本篇语言都是使用go完成的。
1.睡眠排序(Sleep Sort)
对于一个在数组里面的x值
1. 睡眠x秒
2. 打印出x
让全部元素在同一时间开始计时， 计时越快值越小， 当全部计时完成时， 排序好的数组就出来了。
func Sleep(arr ...int) (orders []int) {
var wg sync.WaitGroup
ch := make(chan int, len(arr))
for _, item := range arr {
wg.Add(1)
go func(sleepTime int) {
defer wg.Done()
time.Sleep(time.Duration(int64(sleepTime) * time.Hour.Milliseconds()))
ch <- sleepTime
}(item)
}
wg.Wait()
close(ch)
for item := range ch {
orders = append(orders, item)
}
return
}仔细看里面实际有个小坑的， 如果排序的数值足够小， 可能导致线调度器切换不及时而出现错误的排序结果， 因此不建议取很小的值（如10的负6次方）。
2.量子Bogo排序(Quantum Bogosort)
- 通过多元宇宙，随机打乱数组里面的元素
- 如果数组的顺序不是有序的， 消灭这个宇宙
- 剩余的宇宙则是排序结果正确的
这个排序主要将我们小学学的量子力学结合到一起， 排序的速度是非常快的。 达到了O(n)复杂度。
func QuantumBogo(arr ...int) []int {
ch := make(chan []int, 0)
rand.Seed(time.Now().UnixNano())
//开启10000个宇宙
for i := 0; i < 10000; i++ {
arrInner := make([]int, len(arr))
copy(arrInner, arr)
go func(arrInner ...int) {
shuffle(arrInner...)
if checkSorted(arrInner...) {
select {
case ch <- arrInner:
default:
}
}
}(arrInner...)
}
arr = <-ch
return arr
}这个也有一点坑， 第一个就是golang的切片赋值问题， 如果不用copy的话， 很容易出现多个宇宙维度相互影响问题。导致排序失败。第二个是如果有一个宇宙得到了正确的排序结果， 怎样让这个排序结果给到现在， 并且其他宇宙自行销毁。这里面， 用golang的chan跟select结合， 轻松解决了这个问题， 再由于go的具有的并发特性， 轻松并发10000个不是梦。
3.Bogo排序(Bogo Sort. Random Sort, Monkey Sort)
- 创建一个随机程序
- 将数组随机打乱输出
- 如果输出是正确， 则获取排序后的结果
- 否则重复输出
这个排序有好多名字， 而且跟第二个排序有点像， 只是把多个宇宙换成的一个宇宙， 在一个宇宙里循环
func Random(arr ...int) []int {
for {
shuffle(arr...)
if checkSorted(arr...) {
break
}
}
return arr
}4.太阳比特翻转排序(Solar Bitflip Sort)
- 检测数组是否排序正确
- 如果正确， 返回数组
- 否则等待十秒钟， 并且祈祷通过太阳光的照射使你的内存bit位发生翻转， 进而改变你得数组， 从1开始重复
这个排序个人不建议在项目里面直接使用， 如果非要使用， 在测试的时候一定要把电脑放在太阳光底下， 这样可以让内存翻转的快一点， 要不然测试都可能通过不。
func SolarBitflip(arr ...int) (orders []int) {
for {
if checkSorted(arr...) {
return
}
time.Sleep(time.Second * 10)
}
}5.面条排序(Spaghetti Sort)
- 将数值转化为同比例的面条， 面条尽量选硬的。 最好还没下锅的挂面， 筷子也可以。
- 将面条全部用手拿起来， 一端对着平面怼一下。
- 从上往下进行肉眼扫描， 将扫到的值依次记下， 第一个扫到的是最大的， 依次类推
- 直到扫描完成
这个算法目前没有实现， 觉得跟睡眠算法道理差不多， 如果有好的实现方式， 也可以给我说下
6.斯大林排序(Stalin Sort)
- 召集同志并且把数组给他们看
- 问他们队列是否有序， 有序就举手
- 如果没有举手， 枪决他们
- 重复2,3 直到全部认为有序
func Stalin(arr ...int) (isOrders bool) {
//定义一百个同志, 并且给这些士兵随机分配信仰，区间是0-1
rand.Seed(time.Now().UnixNano())
var comrades []*Comrade
for i := 0; i < 100; i++ {
comrades = append(comrades, &Comrade{
Index: i, Belief: rand.Float64(), IsOrders: false, IsKilled: false})
}
//开始信仰表决
for i := 0; i < 1000; i++ {
// fmt.Printf("开始第%d轮表决n", i)
//isPass：全部同志认为队列是有序的
var isPass = true
for _, comrade := range comrades {
if comrade.IsKilled == true {
continue
}
if comrade.Belief > 0.5 {
comrade.IsOrders = true
//再次制造信仰， 让信仰更加充实
// fmt.Printf("信仰为%f第%d个士兵认为数组的顺序:%tn", comrade.Belief, comrade.Index, comrade.IsOrders)
comrade.Belief = comrade.Belief * (0.5 + rand.Float64())
} else {
comrade.IsOrders = false
// fmt.Printf("---信仰为%f第%d个士兵认为数组的顺序:%tn", comrade.Belief, comrade.Index, comrade.IsOrders)
isPass = false
}
if comrade.IsOrders == false {
// fmt.Println("枪决该同志")
comrade.IsKilled = true
}
}
if isPass {
return true
}
}
return
}这个排序如果选择的都是自己的心腹， 第一次排序就会获取全票通过， 那么排序效率是非常高的。
常用的排序
除了上面用到的排序外， 还有几个排序是非常重要的， 这四个面试之前一定要会
1.插入排序(Insert Sort)
插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌
func Insert(arr ...int) []int {
length := len(arr)
for i := 0; i < length; i++ {
for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
return arr
}2.冒泡排序(Bubble Sort)
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
func Bubble(arr ...int) []int {
for i := len(arr); i > 0; i-- {
for j := 0; j < i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}3.快速排序(Quick Sort)
- 首先设定一个分界值，通过该分界值将数组分成左右两部分。
- 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
- 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
- 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了
func Quick(arr ...int) []int {
if len(arr) <= 1 {
return arr
}
quick(arr, 0, len(arr)-1)
return arr
}
func quick(arr []int, left, right int) {
temp := arr[left]
pointer := left
i, j := left, right
for i < j {
for j >= pointer && arr[j] >= temp {
j--
}
if j >= pointer {
arr[pointer] = arr[j]
pointer = j
}
for i <= pointer && arr[i] <= temp {
i++
}
if i <= pointer {
arr[pointer] = arr[i]
pointer = i
}
}
arr[pointer] = temp
if pointer-left > 1 {
quick(arr, left, pointer-1)
}
if right-pointer > 1 {
quick(arr, pointer+1, right)
}
}4. 归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
func Merge(arr ...int) []int {
divide(arr, 0, len(arr)-1)
return arr
}
func conquer(arr []int, left, mid, right int) {
var tempArr []int
pl := left
pr := mid + 1
for pl <= mid && pr <= right {
var item int
if arr[pl] < arr[pr] {
item = arr[pl]
pl++
} else {
item = arr[pr]
pr++
}
tempArr = append(tempArr, item)
}
for pl <= mid {
tempArr = append(tempArr, arr[pl])
pl++
}
for pr <= right {
tempArr = append(tempArr, arr[pr])
pr++
}
for i := range tempArr {
arr[left+i] = tempArr[i]
}
}
func divide(arr []int, left, right int) {
if left < right {
mid := left + (right-left)/2
divide(arr, left, mid)
divide(arr, mid+1, right)
conquer(arr, left, mid, right)
}
}