快速排序

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

动画演示

image

逻辑描述

1. 以数组最后一个元素作为分割基准（pivot）。
2. 声明两个变量(lo ,hi)，指向最左、右元素，但是不包括基准位置。
3. 移动 lo 位置找到大于，pivot 的元素。
4. 移动 hi 位置找到小于，pivot 的元素。
5. 交换 lo和hi 元素位置，并重复操作。
6. 当 lo>=hi ,退出本次操作，从新寻找基准值。

代码实现

GO

package main

import (
    "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)

微信搜索：小码侠

长按二维码关注我们