Golang排序算法-快速排序

2018-05-08 16:18:29 george518 ...

什么是快速排序

快速排序简单的说就是选择一个基准,将比起大的数放在一边,小的数放到另一边。对这个数的两边再递归上述方法

时间复杂度

时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 复杂性
O(nlog2n) O(n^2 ) O(nlog2n) O(nlog2n) 不稳定 较复杂

基本思想

  • 1、先从数列中取出一个数作为基准数
  • 2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
  • 3、再对左右区间重复第二步,直到各区间只有一个数
/************************************************************
** @Description: quickSort
** @Author: george hao
** @Date:   2018-05-08 09:08
** @Last Modified by:  george hao
** @Last Modified time: 2018-05-08 09:08
*************************************************************/
package main

import "fmt"

func quickSort(arr []int, start, end int) {

    if start >= end {
        return
    }

    i, j := start, end

    //选择中间作为基准值
    mid := (start + end) / 2
    key := arr[mid]

    //fmt.Println("基准值:", mid, key)

    for i <= j {
        for arr[i] < key {
            i++
        }

        for arr[j] > key {
            j--
        }

        if i <= j {
            arr[i], arr[j] = arr[j], arr[i]
            i++
            j--
        }
    }
    //fmt.Println(arr)
    if start < j {
        quickSort(arr, start, j)
    }

    if end > i {
        quickSort(arr, i, end)
    }

}

func main() {
    arr := []int{3, 7, 9, 8, 38, 93, 12, 222, 45, 93, 23, 84, 65, 2}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)

}

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。