快速排序

樹澤 · · 234 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

排序简介(采用了分治+递归)

  • 从数列中挑出一个元素,称为 “基准”(pivot)
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

复杂度

  • 平均时间复杂度:T(n) = O(nlogN)
  • 最佳情况:T(n) = O(nlogN)
  • 最坏情况:T(n) = O(n2)
  • 空间复杂度:O(logN)
  • 稳定性:不稳定
    排序方式:In-place

golang实现

package main

import "fmt"

// 快速排序
func partion(arr []int, start, end int) int {
    pivot, i, j := arr[start], start, end
    // 将第一个元素作为pivot
    for i < j {
        for i < j && pivot < arr[j] { // 从右边开始找出小于pivot
            j--
        }
        if i < j {
            arr[i] = arr[j]
            i++
        }

        for i < j && arr[i] < pivot { // 找出大于pivot
            i++
        }
        if i < j {
            arr[j] = arr[i]
            j--
        }
    }
    arr[i] = pivot //这时i是pivot最终位置
    return i
}

func QuickSort(arr []int, start, end int)  {
    if start < end {
        d := partion(arr, start, end)
        QuickSort(arr, start, d-1)
        QuickSort(arr, d+1, end)
    }
}

func main()  {
    arr := []int{33,11,55,7,44,1}
    QuickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:樹澤

查看原文:快速排序

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

234 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传