【Go】一段快速排序代码看不懂，能请大佬们解释一下吗

thepoy

我知道什么是快速排序，也知道快速排序怎么实现

只是看不懂下面这段实现快速排序的代码。

这是我看见过的用Go实现快速排序最简洁的代码，但也正是因此，我才看不懂，道行太浅了。

for循环体内的代码，主要是else里的代码，看不太明白是什么意思

代码如下：

func QuickSort(s []int) {
        if len(s) < 2 {
                return
        }
        base, baseIndex := s[0], 1
        left, right := 0, len(s)-1
        for left < right {
                if s[baseIndex] > base {   // 如果基础索引对应的值 s[baseIndex] 大于基数 base，那么就将这 s[baseIndex] 与右边界值互换，并将右边界索引减1向左移动1位
                        s[baseIndex], s[right] = s[right], s[baseIndex] 
                        right--                                         
                } else {  // 如果基础索引对应的值 s[baseIndex] 小于或基数 base，那么就将这 s[baseIndex] 与左边界值互换，并将左边界索引加1向右移动1位
                        s[baseIndex], s[left] = s[left], s[baseIndex]
                        left++      
                        baseIndex++   //  不明白的是这行基础索引  ++  的原因和意义是什么，是因为左边界右移了，所以baseIndex也必须右移，还是有其他原因呢？
                }
        }
        s[left] = base
        QuickSort(s[:left])
        QuickSort(s[left+1:])
}

雨中楼

这个东西还真无能为力。

我是蒲公英

就是两个数互换

庸人误我

没学过Go，但是能看出来这是一段快速排序的代码。
我就讲一下大概的思路，更多你可以看一下这个：https://www.runoob.com/w3cnote/quick-sort-2.html
其实挺简单的。
首先一个数组，假设为[5,12,8,7,6,2,4],找到一个数作为基数，以基数为标准，将数组的数划分为两半，比基数大的和比基数小的

如:
基数：5
[2, 4]   5   [12, 8, 7, 6]
然后对小于基数的数组和大于基数的数组，重复上面的过程
小于基数的数组:[2, 4]
重新选择基数：2
2 [4]

大于基数的数组： [12, 8, 7, 6]
重新选择基数：12
[8, 7, 6] 12(从此处看出，选择的基数如果较差，为当前数组的最大值和最小值，就只会确定一个数的位置)
重新选择基数：8
[7, 6] 8
重新选择基数：7
[6] 7

将上面的所有列出来就是完整的排序数组;[2, 4, 5, 6, 7, 8, 12]

仅限个人理解，不喜勿喷

kabengqi

https://www.cnblogs.com/guoyaohua/p/8600214.html他的这篇不错，有图文解释，十大排序算法。

thepoy

kabengqi 发表于 2020-6-17 13:18
https://www.cnblogs.com/guoyaohua/p/8600214.html他的这篇不错，有图文解释，十大排序算法。

排序算法好理解，代码也好实现，但是我发的这段代码是我在Go语言里看见的最简洁的快速排序代码，自己写的和网上找的其他的代码都要比这复杂。可是我就是看不懂这简洁的代码啊，复杂的还能看得懂。

thepoy

庸人误我 发表于 2020-6-17 12:47
没学过Go，但是能看出来这是一段快速排序的代码。
我就讲一下大概的思路，更多你可以看一下这个：https:// ...

快速排序原理是这个，实现原理也差不多是你说的这样。如果是Python或其他能够直接对数组进行加减运算的话就好实现了，直接几个排好序的数组加到一起成为一个完整的有序数组。但Go里无法这样做，数组不能直接sort(left)+base+sort(right)这样合并，所以需要另僻蹊径。这段代码里可以看出来，除了有一个base作为基数外，还有一个baseIndex作为基础索引，通过比较基础索引对应的值和base的大小，来交换边界值与baseIndex的位置。我不明白的点是else块里baseIndex++的目的和意义是什么。

庸人误我

thepoy 发表于 2020-6-17 17:52
快速排序原理是这个，实现原理也差不多是你说的这样。如果是Python或其他能够直接对数组进行加减运算的话 ...

感觉你这函数有点问题，每次递归都是[0,left]和[left+1,max],效率有点低吧！好吧，我直接解释这个baseIndex为啥会++吧！
当前函数(本次调用中)
[5,                        12,        8,       7,       6,         2,          4]
|                             |                                                      |
base(left)         baseIndex                                         right

s[baseIndex] > base,交换s[baseIndex], s[right] = s[right], s[baseIndex],right--
[5,                         4        8,       7,       6,         2,         12]
|                             |                                         |
base(left)         baseIndex                              right


s[baseIndex] < base
s[baseIndex], s[left] = s[left], s[baseIndex]                        left++                              baseIndex++
[4,                            5                           8,       7,       6,                    2,         12]
  |                             |                             |                                         |
base                      (left)                 baseIndex                              right
在 此处可见，baseIndex必须加1，如果不加一，又会执行将一个比基数大的数在本来就比基数大的区域内，进行一些多余的操作
baseIndex完全不用自己维护，直接去left+1即可

thepoy

庸人误我 发表于 2020-6-17 20:53
感觉你这函数有点问题，每次递归都是[0,left]和[left+1,max],效率有点低吧！好吧，我直接解释这个baseInd ...

测试了一下排序8000000的数组，这段代码的效率不低，还稍高于下面的代码实现：

func QuickSort2(left, right int, s []int) {
    l := left
    r := right
    base := s[(left+right)/2]

    for l < r {
        for s[l] < base {
            l++
        }
        for s[r] > base {
            r--
        }

        if l >= r {
            break
        }

        s[l], s[r] = s[r], s[l]

        if s[l] == base {
            r--
        }
        if s[r] == base {
            l++
        }
    }
    if l == r {
        l++
        r--
    }
    if left < r {
        QuickSort2(left, r, s)
    }
    if right > l {
        QuickSort2(l, right, s)
    }
}

二者用时基本没什么差别：

QuickSort(s)  //   748227362纳秒
QuickSort2(s)  //  776221765纳秒