go 实现快速排序

清疚 2021-07-24 13:46 526阅读 0赞

# 一 点睛 #

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

# 二 图解 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 三 代码 #

package main
    
    import (
       "fmt"
    )
    
    // 快速排序
    // 说明
    // 1 left 表示数组左边的下标
    // 2 right 表示数组右边的下标
    // 3 array 表示要排序的数组
    func QuickSort(left int, right int, array *[9]int) {
       l := left
       r := right
       // pivot 是中轴， 支点
       pivot := array[(left+right)/2]
       temp := 0
       // for 循环的目标是将比 pivot 小的数放到左边，比 pivot 大的数放到右边
       for l < r {
          // 从 pivot 的左边找到大于等于pivot的值
          for array[l] < pivot {
             l++
          }
          // 从 pivot 的右边边找到小于等于pivot的值
          for array[r] > pivot {
             r--
          }
          // 1 >= r 表明本次分解任务完成, break
          if l >= r {
             break
          }
          // 交换
          temp = array[l]
          array[l] = array[r]
          array[r] = temp
          // 优化
          if array[l] == pivot {
             r--
          }
          if array[r] == pivot {
             l++
          }
       }
       // 如果  1== r, 再移动下
       if l == r {
          l++
          r--
       }
       // 向左递归
       if left < r {
          QuickSort(left, r, array)
       }
       // 向右递归
       if right > l {
          QuickSort(l, right, array)
       }
    }
    
    
    func main() {
       arr := [9]int{-9, 78, 0, 23, -567, 70, 123, 90, -23}
       / /调用快速排序
       QuickSort(0, len(arr)-1, &arr)
       fmt.Println(arr)
    }

# 四 测试 #

> \[-567 -23 -9 0 23 70 78 90 123\]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/22f8e114c9f048f891470cfc3a9984c6.png