深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分，快速排序按照元素的值对它们进行划分。具体来说，它对给定数组中的元素进行重新排列，以得到一个快速排序的分区。在一个分区中，所有在s下标之前的元素都小于等于a[s]，所有在s下标之后的元素都大于等于a[s]。

显然，建立了一个分区以后，a[s]已经位于它在有序数组中的最终位置，接下来我们可以继续对a[s]前和a[s]后的子数组分别进行排序（使用同样的方法）。
为了排序一个数组a的全部元素，初始调用的是quicksort(a,1，a.length)。

下面的算法对a[p..r]进行分区（先伪代码一下、领会意思）。

partition(a,p,r)
 
 x = a[r]
 
 i = p - 1
 
 for j = p to r - 1
 
  if a[j] ≤ x
 
   i = i + 1
 
   exchange a[i] with a[j]
 
 exchange a[i+1] with a[r]
 
 return i+1

快速排序算法的效率：

在最优情况下，键值比较的次数cbest(n)满足下面的递推式：

当n>1时，cbest(n)=2cbest(n/2)+n，cbest(1)=0

根据主定理，cbest(n)∈θ(nlogn)；对于n=2k的情况求得cbest(n) = nlog(n)。

在最差的情况下，所有的分裂点都趋于极端：两个子数组有一个为空，而另一个子数组仅仅比被分区的数组少一个元素。具体来说，这种令人遗憾的情况会发生在升序的数组上，也就是说输入的数组已经被排过序了。所以，在进行了n+1次比较之后建立了分区，并且将a[0]和它本身进行了交换以后，快速排序算法还会对严格递增的数组a[1..n-1]进行排序。对规模减小了的严格递增数组的排序会一直继续到最后一个子数组a[n-2..n-1]。这种情况下，键值比较的总次数应该等于：

cworst(n)=(n+1)+n+...+3=(n+1)(n+2)/2-3∈θ(n2)

现在，轮到讨论快速排序在平均情况下的效率了。对于大小为n的随机排列的数组，快速排序的平均键值比较次数记为cavg(n)。假设分区的分裂点s（0≤s≤n-1)位于每个位置的概率都是1/n，我们得到下面的递推关系式：

cavg(0)=0，cavg(1)=0

cavg(n)≈2nlnn≈1.38nlogn
因此，快速排序在平均情况下，仅比最优情况多执行38%的比较操作。此外，它的最内层循环效率非常高，使得在处理随机排列的数组时，速度要比归并排序快。

以下是快速排序的go代码：

func quicksort(slice_arg []int, ileft int, iright int) {
    if ileft < iright {
        var itmpval = slice_arg[ileft]
        var i, j = ileft, iright
        for i < j {
            fmt.println("i,j = ", i, j)
            for i < j && slice_arg[j] > itmpval {
                j--
            }
            if i < j {
                slice_arg[i] = slice_arg[j]
                i++
            }

            for i < j && slice_arg[i] < itmpval {
                i++
            }
            if i < j {
                slice_arg[j] = slice_arg[i]
                j--
            }
        }
        slice_arg[i] = itmpval

        quicksort(slice_arg, ileft, i-1)
        quicksort(slice_arg, j+1, iright)
    }
}