快速排序(Quick Sort)

快速排序(QuickSort)是对冒泡排序的一种改进；

• 基本思想是：

  • 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，

  • 然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据编程有序序列。

快速排序法应用实例：

• 要求： 对[-9,78,0,23,-567,70]进行从小到大的排序，要求使用快速排序法。

• 说明：

  • 如果取消左右递归，结果是 -9 -567 0 23 78 70
  • 如果取消右递归，结果是 -567 -9 0 23 78 70
  • 如果取消左递归，结果是 -9 -567 0 23 70 78

• 代码实现：

package main

import "fmt"

//QucckSort，快速排序函数
//说明：
//1.left 表示数组左边的下标；
//2.right 表示数组右边的下标；
//3.array表示要排序的数组；
func QuickSort(left int, right int, array *[9]int) {
    l := left
    r := right
    // pivot 是中轴，支点
    pivot := array[(left+right)/2]
    temp := 0

    //for循环的目标是：
    //将比pivot小的数放到左边，
    //将比pivot大的数放到右边；
    for l < r {

        //从 pivot的左边找到大于等于pivot的值；
        for array[l] < pivot {
            l++
        }
        //从 pivot的右边找到小于等于pivot的值；
        for array[r] > pivot {
            r--
        }

        // l >= r 表明本次分解任务完成，break
        if l >= r {
            break
        }

        //交换：
        temp = array[l]
        array[l] = array[r]
        array[r] = temp

        //优化
        if array[l] == pivot {
            r--
        }
        if array[r] == pivot {
            l++
        }
    }

    // 如果 l == r,再移动一下； 如果没有本判断，程序会卡在r==l的情况下；
    if l == r {
        l++
        r--
    }

    //向左递归
    if left < r {
        QuickSort(left, r, array)
    }
    //向右递归
    if right > l {
        QuickSort(l, right, array)
    }
}
func main() {
    arr := [9]int{-9, 78, 0, 23, -567, 70, 123, 99, -80}
    fmt.Println("main...", arr)
    QuickSort(0, len(arr)-1, &arr)
    fmt.Println("main...", arr)
}