快速排序算法

原理

快速排序算法基于这样一个理念：随机从中选一个值作为参考值，将它与全序列比较，比它小的放左边，大的放右边。这样完成一次排序，就会把整个序列分成两部分，再分别对这两部分排序即可。
复杂度 nLog(n)
但涉及到机器机械地执行，这里每一步的描述里都有限制。用程序的描述方法，则有以下限制：

• 对于这个值，要用下标标识其所在位置，那要用一个额外的存储空间来存储这个下标；
• 特殊情况的考虑；
• 递归结束的标志。
  下面开始按思路来写

编程思路

1. 先考虑终止条件（特殊情况）

也许你习惯于最后考虑终止条件，但这样不利于自己调试代码。

• 一是因为可能会发生死循环，不利于调试；
• 二是因为意外的现象可能会引起自己的误解。

    if len(arr) < 2 {
        return
    }
    if len(arr) == 2 && arr[0] > arr[1] {
        arr[0], arr[1] = arr[1], arr[0]
        return
    }

2. 先完成一次排序

这里是主要逻辑，所以要用机器的思维拆解快速排序原理的每一步：

• 要有一个额外的空间来记标记选用的参考值（存下标）；(需要把直接用下标的思想拆出来)
• 用下标标记“始”与“终”；
  考虑的这些量先做为参数传入函数，之后再做精化处理。
  由于我们用 Go 语言对于数组只要不超出容量，可以认为是引用传递，且支持多重赋值，那么写下来如下：

func quickSort(arr []int, tempIndex, startIndex, endIndex int) {
    if len(arr) < 2 {
        return
    }
    if len(arr) == 2 && arr[0] > arr[1] {
        arr[0], arr[1] = arr[1], arr[0]
        return
    }

    for startIndex <= endIndex { // attention: <=, not <
        if arr[startIndex] > arr[tempIndex] {
            arr[startIndex], arr[tempIndex] = arr[tempIndex], arr[startIndex]
        }
        startIndex++
    }
}

加入递归

加入递归时，最重要的是考虑下一次调用的参数的传递，但结合 Go 的切片的概念和特性我们发现会很方便，只需要传入子切片，只对子切片操作排序就可以了。参考值可以始终选用数组第一个元素。所以改为代码如下：

func quickSort(arr []int) {
    if len(arr) < 2 {
        return
    }

    if len(arr) == 2 && arr[0] > arr[1] {
        arr[0], arr[1] = arr[1], arr[0]
    }

    tempIndex := 0
    startIndex := 0
    endIndex := len(arr) - 1

    for startIndex <= endIndex {
        if arr[startIndex] < arr[tempIndex] {
            arr[startIndex], arr[tempIndex] = arr[tempIndex], arr[startIndex]
        }
        startIndex++
    }

    if tempIndex > 0 {
        quickSort(arr[0 : tempIndex-1])
    }
    if tempIndex < len(arr)-1 {
        quickSort(arr[tempIndex+1:])
    }
}

其中还有细节要把握，比如 < 与 <= 不能出错 等。
以下是所有代码清单：

package main

import (
    "fmt"
    "os"
    "strconv"
)

func main() {
    inputs := os.Args[1:]
    nums := covertToInt(inputs)
    n := len(nums)
    fmt.Printf("Your input has %d integers\n", n)

    quickSort(nums)

    fmt.Println(nums)
}

func quickSort(arr []int) {
    if len(arr) < 2 {
        return
    }

    if len(arr) == 2 && arr[0] > arr[1] {
        arr[0], arr[1] = arr[1], arr[0]
    }

    tempIndex := 0
    startIndex := 0
    endIndex := len(arr) - 1

    for startIndex <= endIndex {
        if arr[startIndex] < arr[tempIndex] {
            arr[startIndex], arr[tempIndex] = arr[tempIndex], arr[startIndex]
        }
        startIndex++
    }

    if tempIndex > 0 {
        quickSort(arr[0 : tempIndex-1])
    }
    if tempIndex < len(arr)-1 {
        quickSort(arr[tempIndex+1:])
    }
}

func covertToInt(strs []string) []int {
    ints := []int{}
    for _, v := range strs {
        i, _ := strconv.Atoi(v)
        ints = append(ints, i)
    }
    return ints
}