快速排序

快速排序是一种高效的排序算法，它基于将数据列划分为更小的数组。比如将一个数组分割成两个更小的数据。然后重复对两个以上元素的数组进行排序，直到元素不可分割为止。

动画演示

image

逻辑描述

1. 以数组最后一个元素作为分割基准（pivot）。

2. 声明两个变量(lo ,hi)，指向最左、右元素，但是不包括基准位置。

3. 移动 lo 位置找到大于，pivot 的元素。

4. 移动 hi 位置找到小于，pivot 的元素。

5. 交换 lo和hi 元素位置，并重复操作。

6. 当 lo>=hi ,退出本次操作，从新寻找基准值。

代码实现

GO

package mainimport (    "fmt")func main() {    //声明数组
    numbers := []int{35, 33, 42, 10, 14, 19, 27, 44, 26, 31}    //numbers := utils.GetRandSlices(10)
    fmt.Printf("%v \n", numbers)    //开始排序： 第一遍 左、右
    QuickSort(0, len(numbers)-1, &numbers)
    fmt.Printf("%v \n", numbers)
}func QuickSort(left, right int, numbers *[]int) {    if right-left <= 0 { //数据已经不能再被分割。
        return
    } else {
        pivot := (*numbers)[right] //找到基准元素
        partIndex := Partition(left, right, pivot, numbers) //执行定位迁移操作。获取到基准原始交叉点。
        //-----------------------------------------------------
        //此时的数据已经由交叉点分割成左右两份。分别对左右的元素执行如此操作。
        QuickSort(left, partIndex-1, numbers)  //小于基准（左边）的元素，执行快速排序
        QuickSort(partIndex+1, right, numbers) //大于基准（右边）的元素，执行快速排序
    }
}func Partition(left, right, pivot int, numbers *[]int) int {
    lo := left
    hi := right - 1 //不包含基准元素位置
    for {        // 移动 `lo` 位置找到大于，`pivot` 的元素。
        for (*numbers)[lo] < pivot {
            lo++
        }        // 移动 `hi` 位置找到小于，`pivot` 的元素。
        for hi > 0 && (*numbers)[hi] > pivot {
            hi--
        }        //当移动的点交叉，本次迁移完成。退出
        if lo >= hi {            break
        } else {            //交换两个元素位置。
            fmt.Printf(" 交换 :%d,%d\n", (*numbers)[lo], (*numbers)[hi])
            (*numbers)[lo], (*numbers)[hi] = (*numbers)[hi], (*numbers)[lo]
        }
    }    //当 `hi` 和 `lo` 交叉以后，数据已经通过 `pivot` 分割成左右两段。那么 `pivot` 就需要移动到交叉点的位置。
    if lo != right {
        fmt.Printf(" 交换 :%d,%d\n", (*numbers)[lo], (*numbers)[right])
        (*numbers)[lo], (*numbers)[right] = (*numbers)[right], (*numbers)[lo]
    }    //返回交叉点。
    return lo
}

Python

# -*- coding: UTF-8 -*-numbers = [35, 33, 42, 10, 14, 19, 27, 44, 26, 31]
length = len(numbers)def quick_sort(left, right, nums):
    if left >= right:        return
    else:
        pivot = nums[right]
        pivot_index = partition(left, right, pivot, nums)
        quick_sort(left, pivot_index - 1, nums)
        quick_sort(pivot_index + 1, right, nums)def partition(left, right, pivot, nums):
    lo = left
    hi = right - 1  # 不包含基准元素位置

    while True:        # 移动 `lo` 位置找到大于，`pivot` 的元素。
        for i in range(lo, hi + 1):
            lo = i            if nums[i] > pivot:                break
        # 移动 `hi` 位置找到小于，`pivot` 的元素。
        for j in range(hi, lo - 1, -1):
            hi = j            if nums[j] < pivot:                break

        # 当移动的点交叉，本次迁移完成。退出
        if lo >= hi:            break
        else:            # 交换两个元素位置。
            print("交换:", nums[lo], nums[hi], "\n")
            nums[lo], nums[hi] = nums[hi], nums[lo]    # 当 `hi` 和 `lo` 交叉以后，数据已经通过 `pivot` 分割成左右两段。那么 `pivot` 就需要移动到交叉点的位置。
    if lo != right:
        print("交换:", nums[lo], nums[right], "\n")
        nums[lo], nums[right] = nums[right], nums[lo]    return lo


print("排序前:")
print(numbers)
quick_sort(0, length - 1, numbers)
print("排序后:", numbers)

作者：小码侠
链接：https://www.jianshu.com/p/7b7fe9eb671e