专栏首页陶士涵的菜地[Go] Golang练习项目-GO语言实现快速排序-第一个数作为基准更容易理解

[Go] Golang练习项目-GO语言实现快速排序-第一个数作为基准更容易理解

快速排序思路:

1. 第一个数作为基准数,找到所有比基准数小的放在左边 ,找所有比基准数大的放右边

2.两个指针 ,一个从前往后 i,一个从后往前 j,i找到比基准数大的停下 , j找到比基准数小的停下 , 两个数调换位置,直到两数相遇

3.调换基准数与i/j位置

4.递归 , 从0到基准数位置 ,从基准数位置到最后

//快速排序2
func QuickSort2(arr *[]int,left int,right int){
    if left>= right{
        return
    }
    privot:=(*arr)[left]
    i:=left
    j:=right
    for i<j{
        for i<j && (*arr)[j]>privot{
            j--
        }
        for i<j && (*arr)[i]<=privot{
            i++
        }
        temp:=(*arr)[i]
        (*arr)[i]=(*arr)[j]
        (*arr)[j]=temp
    }
    (*arr)[left]=(*arr)[i]
    (*arr)[i]=privot

    QuickSort(arr,left,i-1)
    QuickSort(arr,i+1,right)
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [PHP] 算法-把数组排成最小的数的PHP实现

    陶士涵
  • [Go] Golang练习项目-GO实现冒泡排序以及优化算法

    变量lastSwapIndex ,记录最后一次发生交换的位置,后续元素不再进行比较

    陶士涵
  • [Go] Golang练习项目-快速排序的GO语言实现

    快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有...

    陶士涵
  • 快速排序(quick sort)C++实现

    每次选一个轴pivot(我选数组的第一个元素arr[p]),遍历其余数组元素使得比arr[p]大的数都在arr[p]的右边,比arr[p]小的数都在arr[p]...

    kalifa_lau
  • JavaScript常用排序算法

    3、对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

    FinGet
  • 数组中重复的数

    先给数组排序,然后再遍历一遍有序数组,依次比较相邻元素,就很容易能找出数组中重复的值。使用快排排序的话时间复杂度为 O(nlogn) 。

    谭小谭
  • php疑难杂症代码收集(不断增长中)

    使用PHP开发已经很久了,但是最近看过一些代码,却发现自己竟然不知道为什么运行结果会是那个样子,特收集记录之,代码运行结果大家请自行尝试,我会不断更新此文,弄明...

    luxixing
  • BubbleSort冒泡排序

    冒泡排序是一种简单的排序算法。它适合小规模数据的排序,并且其效率比较低。冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没...

    羊羽shine
  • 作为一个前端,排序算法你有了解过吗?

    前天看到知乎上有一篇文章在吐槽阮一峰老师的快速排序算法,这里插一句题外话,我觉得人非圣贤孰能无过,尽信书不如无书,学习的过程也就是不断发现错误改正错误的过程,有...

    前端博客 : alili.tech
  • 算法菜鸟的烂笔头

    cnguu

扫码关注云+社区

领取腾讯云代金券