Go语言实现：常见排序算法

冒泡排序：

时间复杂度：O(n^2)
稳定性：稳定

//冒泡排序
//相邻两位交换，12交换，23交换，34交换，把最大的数放到最右边
//利用flag标记可以避免无效循环
func BubbleSort(arr []int) {
	length := len(arr)
	//length是最后一位，i < length-1，查询到倒数第二位
	for i := 0; i < length-1; i++ {
		//true表示此次循环没有发生交换
		flag := true
		//每次循环j都从0开始，然后j++
		//每次循环最大的数都会被放到最右边，j的查询范围在逐渐减小，所以j < length-1-i
		for j := 0; j < length-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				//false表示此次循环发生了交换
				flag = false
			}
		}
		//true表示序列已经有序，直接退出，不用继续循环
		//false表示本次循环发生了交换，需要继续判断下个循环
		if flag {
			break
		}
	}
}

简单选择排序：

时间复杂度：O(n^2)
稳定性：不稳定

//简单选择排序
//循环一遍，把最小的放最左边；循环剩下的序列
//循环时只取值比较，一遍循环完发生交换
func selectSort(arr []int) {
   length := len(arr)
   for i := 0; i < length; i++ {
      //从首位i开始，最小指向i，依次与后面比较
      min := i
      for j := i + 1; j < length; j++ {
         //j比首位小，把最小指向j
         if arr[min] > arr[j] {
            min = j
         }
      }
      //循环完一遍，最小值发生过变化
      if min != i {
         //交换i和min
         arr[i], arr[min] = arr[min], arr[i]
      }
   }
}

直接插入排序：

时间复杂度：O(n^2)
稳定性：稳定

//直接插入排序
//取首元素作为有序队列，把第二位插入到有序队列中，把第三位插入到前两位组成的有序队列中
//新的一位插入有序队列时，跟他的前一位比较，即有序队列的最右边，依次向前遍历
func insertSort(arr []int) {
   length := len(arr)
   //从第二位开始处理，所以i从1开始
   for i := 1; i < length; i++ {
      //if满足，则新的一位需要插入处理；else表示新的一位依旧有序，不处理
      if arr[i] < arr[i-1] {
         //arr[i]插入时，前面的元素需要后移，i位置元素被顶掉，所以需要临时存值
         temp := arr[i]
         //j取有序队列的最右位i-1，依次向左j--
         j := i - 1
         //temp < arr[j]，把j向后移位，依次循环，直到temp >= arr[j]
         for ; j >= 0 && temp < arr[j]; j-- {
            //把j向后移位
            arr[j+1] = arr[j]
         }
         //因为发生了j--
         arr[j+1] = temp
      }
   }
}

希尔排序：

时间复杂度：O(n^1.5)
稳定性：不稳定

//希尔排序
//按间隔分组，每组进行插入排序
//长度为10，间隔为10/2=5，按(0,5)(1,6)(2,7)(3,8)(4,9)分组
//间隔减小为5/2=2，按(0,2,4,6,8)(1,3,5,7,9)分组
//组内插入排序时，各组之间交替比较，以间隔为2举例：先比较0和2，再比较1和3，再比较4，再比较5，依次遍历
//直到间隔为1，按(0,1...9)分组
func shellSsort(arr []int) {
   length := len(arr)
   //按间隔分组
   for gap := length / 2; gap > 0; gap /= 2 {
      //当前各个分组进行插入排序
      for i := gap; i < length; i++ {
         if arr[i] < arr[i-gap] {
            temp := arr[i]
            j := i - gap
            for ; j >= 0 && temp < arr[j]; j -= gap {
               arr[j+gap] = arr[j]
            }
            arr[j+gap] = temp
         }
      }
   }
}

归并排序：

时间复杂度：O(nlogn)
稳定性：稳定

//归并排序
//将两个有序序列合并成一个有序序列
//取中间值分左右递归处理
func mergeSort(r []int) []int {
   length := len(r)
   if length <= 1 {
      return r
   }
   //左右分别处理
   num := length / 2
   left := mergeSort(r[:num])
   right := mergeSort(r[num:])
   //左右两边都为有序，进行合并
   return merge(left, right)
}

func merge(left, right []int) (result []int) {
   l, r := 0, 0
   //left或right有一方遍历完则退出循环
   for l < len(left) && r < len(right) {
      if left[l] < right[r] {
         result = append(result, left[l])
         l++
      } else {
         result = append(result, right[r])
         r++
      }
   }
   //left和right均为有序，直接将剩余部分加进序列
   //如果上面是left遍历完，left[l:]为[]，right还有剩余值
   //如果上面是right遍历完，right[r:]为[], left还有剩余值
   result = append(result, left[l:]...)
   result = append(result, right[r:]...)
   return
}

快速排序：

时间复杂度：O(nlogn)
稳定性：不稳定

//快速排序
//取首位元素为临界值，一遍循环，临界值左边为小数，右边为大数
//递归临界值左边和右边
func quickSort(arr []int) {
   length := len(arr)
   if length <= 1 {
      return
   }
   quick(arr, 0, length-1)
}

func quick(arr []int, start, end int) {
   if start >= end {
      return
   }
   i, j := start, end
   //取首位元素为分界值
   temp := arr[i]
   for i < j {
      //从右往左找，大的不处理，j--
      for i < j && arr[j] >= temp {
         j--
      }
      //直到遇见第一个小的，跳出上面循环
      if i < j {
         //把小的给i，temp的值没发生变化
         arr[i] = arr[j]
         i++
      }

      //从左往右找，小的不处理，i++
      for i < j && arr[i] <= temp {
         i++
      }
      //直到遇见第一个大的，跳出上面循环
      if i < j {
         //把大的给j，temp的值没发生变化
         arr[j] = arr[i]
         j--
      }
   }
   //把temp给到i位置
   arr[i] = temp
   //递归i的左边，0到i-1
   quick(arr, start, i-1)
   //递归i的右边，i+1到right
   quick(arr, i+1, end)
}

堆排序：

时间复杂度：O(nlogn)
稳定性：不稳定

//堆排序
//升序使用大顶堆，降序使用小顶堆，以大顶堆为例
//顶堆是上下比较大小，父结点与其孩子比较，同一父结点的左右大小无限制，二叉搜索树是左右比较大小，不要搞混
//先调整序列为大顶堆(序列默认是一棵二叉树，把该二叉树调整为大顶堆)
//处理大顶堆：首尾交换，末位最大，去掉末位，调整剩下序列为大顶堆，循环处理
func heapSort(arr []int) []int {
   length := len(arr)
   //调整序列为大顶堆
   for i := length/2 - 1; i >= 0; i-- {
      //从最后一个非叶子结点开始，从右往左，从下往上，length/2-1为最后一个非叶子结点
      adjustHeap(arr, i, length)
   }
   //处理大顶堆
   //大顶堆左右无序，上下有序
   for i := length - 1; i > 0; i-- {
      //首位最大，首尾交换，把最大放在队尾
      arr[0], arr[i] = arr[i], arr[0]
      //去掉队尾最大元素，所以队列长度length-1，即为i，把剩余i个元素调整为大顶堆
      //此时只有刚交换的首位不符合大顶堆条件，没必要像上面循环所有非叶子结点，只需从首位开始调整，所以i=0
      adjustHeap(arr, 0, i)
   }
   return arr
}

//调整二叉树为大顶堆
func adjustHeap(arr []int, i, length int) {
   //非叶子结点i的左右孩子
   left := 2*i + 1
   right := 2*i + 2
   //默认i为最大
   max := i
   //存在左孩子且左孩子大，最大指向left，因为右孩子可能更大，所以暂不交换
   if left < length && arr[left] > arr[max] {
      max = left
   }
   //存在右孩子且右孩子更大，最大指向right
   if right < length && arr[right] > arr[max] {
      max = right
   }
   //最大发生过改变，交换
   if max != i {
      arr[i], arr[max] = arr[max], arr[i]
      //最后一层非叶子结点，递归时不发生交换操作；
      //假如二叉树深度为4，最后一层非叶子结点为第三层，处理第二层发生交换时，需要递归处理第三层是否被影响了
      adjustHeap(arr, max, length)
   }
}

基数排序：

时间复杂度：O(d(n+r))
稳定性：稳定

//基数排序
//分配式排序，桶子法，非负数，共0-9，10个桶子
//首次循环根据元素个位数，将元素分配至对应桶子里，0进0号桶，9进9号桶
//按桶子排序，再次循环，根据元素十位数再次分配
func radixSort(arr []int) {
   length := len(arr)
   if length <= 1 {
      return
   }
   //元素的最大位数
   d := maxBit(arr)
   //用mod和dev求对应位数上的数值
   mod, dev := 10, 1
   //循环位数
   for i := 0; i < d; i++ {
      //10个桶子
      temp := [10][]int{}
      //遍历序列
      for j := 0; j < length; j++ {
         //先求余，再求商
         //个位数值：x%10/1；十位数值：x%100/10
         bucket := arr[j] % mod / dev
         //按位存值
         temp[bucket] = append(temp[bucket], arr[j])
      }
      //为arr排序时的下标
      k := 0
      //排序arr
      for m := 0; m < 10; m++ {
         for n := 0; n < len(temp[m]); n++ {
            arr[k] = temp[m][n]
            k++
         }
      }
      //为下一位做准备
      mod *= 10
      dev *= 10
   }
}

//基数排序
//分配式排序，桶子法，存在负数，共0-19，20个桶子
//首次循环根据元素个位数，将元素分配至对应桶子里，-9进1号桶，-1进9号桶，0进10号桶，1进11号桶，19进19号桶
//按桶子排序，再次循环，根据元素十位数再次分配
func radixSort(arr []int) {
   length := len(arr)
   if length <= 1 {
      return
   }
   //元素的最大位数
   d := maxBit(arr)
   //用mod和dev求对应位数上的数值
   mod, dev := 10, 1
   //循环位数
   for i := 0; i < d; i++ {
      //10个桶子
      temp := [20][]int{}
      //遍历序列
      for j := 0; j < length; j++ {
         //先求余，再求商，下标不为负，+10保证为非负数
         //个位数值：x%10/1+10；十位数值：x%100/10+10
         bucket := (arr[j] % mod / dev)+10
         //按位存值
         temp[bucket] = append(temp[bucket], arr[j])
      }
      //为arr排序时的下标
      k := 0
      //排序arr
      for m := 0; m < 20; m++ {
         for n := 0; n < len(temp[m]); n++ {
            arr[k] = temp[m][n]
            k++
         }
      }
      //为下一位做准备
      mod *= 10
      dev *= 10
   }
}

//元素的最大位数
func maxBit(arr []int) int {
   length := len(arr)
   d := 1
   p := 10
   for i := 0; i < length; i++ {
      for arr[i] >= p {
         d++
         p *= 10
      }
   }
   return d
}