快速排序算法

算法描述:是对插入算法的一种优化,利用对问题的二分化,实现递归完成快速排序
,在所有算法中二分化是最常用的方式,将问题尽量的分成两种情况加以分析,
最终以形成类似树的方式加以利用,因为在比较模型中的算法中,最快的排序时间
负载度为 O(nlgn).

算法步骤

  • 将数据根据一个值按照大小分成左右两边,左边小于此值,右边大于
  • 将两边数据进行递归调用步骤1
  • 将所有数据合并

优化

标准的快速排序只是取,数组的第一个元素进行分组,对于随机的数据会产生
如果数据已经排好序,算法的时间会上升到O(n^2),所以一般为了优化,避免
产生最坏情况,会采取随机数来避免这种情况产生

优化步骤

  • 随机选取一个数,当分割值
  • 递归1方法
  • 将所有数据进行合并
package sort

import "fmt"

func QuickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    splitdata := arr[0]          //第一个数据
    low := make([]int, 0, 0)     //比我小的数据
    hight := make([]int, 0, 0)   //比我大的数据
    mid := make([]int, 0, 0)     //与我一样大的数据
    mid = append(mid, splitdata) //加入一个
    for i := 1; i < len(arr); i++ {
        if arr[i] < splitdata {
            low = append(low, arr[i])
        } else if arr[i] > splitdata {
            hight = append(hight, arr[i])
        } else {
            mid = append(mid, arr[i])
        }
    }
    low, hight = QuickSort(low), QuickSort(hight)
    myarr := append(append(low, mid...), hight...)
    return myarr
}

//快读排序算法
func main() {
    arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
    fmt.Println(QuickSort(arr))
}
文档更新时间: 2020-07-22 17:11   作者:kuteng