GO语言实现 一 快速排序(一)

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

快速排序被誉为20世纪科学和工程领域的十大算法之一。听名字就能了解,快速排序的特点,就是快

快速排序

快速排序采用了二分递归的思想,通过一趟排序将整个数组划分为两个部分,低位部分的值全部小于高位部分的值,然后对低位和高位部分分别排序

快速排序算法的具体步骤如下:

  1. 对数组 arr 进行随机洗牌

  2. 划分数组,我们通过交换操作,找到合适的 j,保证

    • j 左边的元素全部小于 arr[j]
    • j 右边的元素全部大于 arr[j]
  3. 对每一块被划分的切片进行排序

qs1.png

我们可以通过双指针在O(n)的时间复杂度内获取合适的 j

我们设立两个指针 i 和 j,同时设置一个标志值 arr[low],一般来说,标志值取数组第一个元素

  • 当 arr[i] < arr[low]时,指针 i 从左至右一直扫描
  • 当 arr[j] > arr[low]时,指针 j 从右至左一直扫描
  • 交换 arr[i]和 a[j]的元素
  • 当 i < j 时重复以上步骤

上述算法结束之后,j 所在的位置即为我们寻找的 j

golang代码实现如下:

func partition(arr []int, low int, high int) int {
    i, j := low+1, high
    for true {
        for arr[i] < arr[low] {
            i++
            if i == high {
                break
            }
        }
        for arr[low] < arr[j] {
            j--
            if j == low {
                break
            }
        }
        if i >= j {
            break
        }
        exch(arr, i, j)
    }
    exch(arr, low, j)
    return j
}

对于整个快排算法,我们的 golang实现如下:

func quickSort(arr []int) []int {
    arr = shuffling(arr)
    sort(arr, 0, len(arr)-1)
    return arr
}

func sort(arr []int, low int, high int) {
    if high <= low {
        return
    }
    j := partition(arr, low, high)
    sort(arr, low, j-1)
    sort(arr, j+1, high)
}
func partition(arr []int, low int, high int) int {
    i, j := low+1, high
    for true {
        for arr[i] < arr[low] {
            i++
            if i == high {
                break
            }
        }
        for arr[low] < arr[j] {
            j--
            if j == low {
                break
            }
        }
        if i >= j {
            break
        }
        exch(arr, i, j)
    }
    exch(arr, low, j)
    return j
}
func exch(arr []int, a int, b int) {
    temp := arr[a]
    arr[a] = arr[b]
    arr[b] = temp
}

时间复杂度:

最好情况 O(nlogn)
最坏情况 O(n^2)

由于我们添加了洗牌方法(见基本排序实现),所以整个数组趋向于无序,快速排序往往能取得比其他排序好的多的性能


参考文献:
Dynamic Connectivity - 普林斯顿大学 | Coursera


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

本文来自:简书

感谢作者:YXCoder

查看原文:GO语言实现 一 快速排序(一)

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

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