【go】剑指offer：常见排序算法
作者 | 陌无崖
转载请联系授权
冒泡排序
冒泡排序是比较简单的排序算法，它的关键思想是移动指针不断的进行两两比较，将最大的数字不断的进行更换位置，直至到最后，即完成一趟比较，都会寻找到最大的数字，且最大的数字会跑到末尾。
理解了上面的基本思想接着我们来想一想我们的代码思路，首先我们需要进行刚开始两个位置的比较，然后且需要比较到原始数据的最后一个位置。然后我们需要仍然从初始位置进行两两比较，然后应该比较到原始数据的倒数第2个位置。
现在我们模拟一下代码思路
//定义i来控制我们的比较一趟(冒出最大)的次数
//数据长度为len(data)，需要比较len(data)-1次
i < len(data)-1
//定义一个j代表我们的比较位置
//比较结束位置用len(data)-1-i
代码如下
func bubbleSort(data []int) {
// 外循环控制次数
for i := 0; i < len(data)-1; i++ {
//内循环进行比较
for j := 0; j < len(data)-1-i; j++ {
// fmt.Println(data[j], "与", data[j+1], "作比较")
if data[j] > data[j+1] {
data[j], data[j+1] = data[j+1], data[j]
}
}
}
fmt.Println(data)
}时间复杂度：
外循环为n次，内循环总共为(1+2+3+4+..n)次，由此可知时间复杂度为O(n^2)
选择排序
对于选择排序，比较符合思考的逻辑，它的思想为每次从原始序列中找到最小放到初始位置，然后从剩余的未排序的中序列中找到最小的数字，排列到已排序的末尾。
这个思想相对简单，我们直接来看代码思路
//首先我们需要从初始位置开始寻找最小的数字，
// 然后移动初始位置，因此定义i来表示第一次比较的位置
for i :=0 ;i < len(data);i++{}
//在循环中我们需要将data[i]不断的与其之后的数字进行比较，
// 因此定义j来表示后面的数组的位置
for j := i + 1; j < len(data); j++{}
//开始比较data[i] 与 data[j]代码如下：
func Select_Sort(data []int) {
for i := 0; i < len(data); i++ {
for j := i + 1; j < len(data); j++ {
if data[i] > data[j] {
data[i], data[j] = data[j], data[i]
}
}
}
fmt.Println(data)
}时间复杂度：
由于外循环n次内循环总共为(1+2+3+4+ ...n),因此时间复杂度仍然为O(n^2)
插入排序
插入排序是一个不断插入数字来保证顺序不变的算法，即将一个数字插入到一个已经排好的序列。这一点可以类比扑克牌抓牌，每次抓牌都是从桌面上的牌抓起插入到自己手中的牌中，自己的手中的牌一直都将是有序的序列.
那么我们如何来保证我们的有序呢？我们不防也默认不知序列中的数字的排序情况，我们拿出一个数字，然后将下一数字拿出插入到第一个数字的之前或之后，保证有序，然后我们拿第三个数字，通过第三个数字和第二数字、第一个数字比较，一旦发现该数字比比较的数字小，以此来确定位置。然后将较大的数字整体往后移动。因此我们在移动数字之前我们的原始序列应该扩充一个位置。
看一下代码思路
//因为第一个数字就是有序，因此我们拿数字可以从第二个位置，令 i = 1
for i := 1; i < len(data); i++ {}
//我们需要将拿起的数字从后往前的进行比较，因此，我们令j = i
for j := i; j > 0; j-- {}
//前面的思想说我们需要一个扩展我们的数组，
// 为了更加简单，我们可以在原始数组上进行修改，只需要比较的时候，
// 不断更替位置，一直到比较结束的终止条件
if data[j] > data[j-1] {
data[j], data[j-1] = data[j-1], data[j]
}代码如下
// 直接插入排序简单写法
func Insert_Sort(data []int) {
// 外循环控制待插入的数字
for i := 1; i < len(data); i++ {
for j := i; j > 0; j-- {
if data[j] > data[j-1] {
data[j], data[j-1] = data[j-1], data[j]
}
}
}
}那么我们如何使用扩展数组的方式进行插入排序呢？也很简单，首先我们需要不断的从我们的原始序列中取出数字，然后通过一个插入排序的函数即可，在插入排序中，我么的原始数组是有序的，我们需要对数组的长度增1，我们可以将待插入的数字先暂时放到尾，然后开始比较寻找位置。代码如下
func direct_insert(data []int, key int) {
// 获取已经排好序列的数组的长度
length := len(data)
data = append(data, key)
// 定义尾指针
tail := length - 1
// 定义result的末尾
right := length
for tail >= 0 && data[tail] > key {
data[tail], data[right] = data[right], data[tail]
tail--
right--
}
}传入原始数组的待插入的方式如下：
for i := 0; i < len(data); i++ {
Birary_Serect_Sort(data[:i], data[i])
}时间复杂度
对于坏的比较次数就是原始数组是逆序的，对于第n个数，我们需要比较n-1次，因此时间复杂度仍然为O(n^2)，但是不固定，适用于较少的数据，性能稳定。
快速排序
快速排序从名称上就很明显这是一个快速的排序方法，它采用了折半的思想，在一个序列中，随机选出其中的一个数字，将这个数字和整个序列进行比较，将比这个数字大的放右边，比数字小的放左边，因此原始的序列分成了两个序列，然后再在各自的序列按照同样的方法，分成两个序列。以此递归。
接着我们来看代码思路
1、从数列中挑出一个元素，称为 "基准"（pivot）;
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
代码如下：
func Quick_Sort(data []int,left,right int){
// 定义基准数的位置
p := left
i,j :=left,right
for i<=j{
if data[p] <=data[j] && p <=j{
j--
}
if p <= j{
data[p],data[j] = data[j],data[p]
p = j
}
if data[p]>=data[i] && j <=p{
i++
}
if p >=i{
data[p],data[i] = data[i],data[p]
p = i
}
}
if (p-left)>1{
Quick_Sort(data,left,p-1)
}
if (right-p)>1{
Quick_Sort(data,p+1,right)
}
}