算法（十）快速排序

2019-07-11

本文简单介绍一下快速排序算法，以及最后用python和go语言的实现

1. 原理

选择基准元素，将小于基于元素的数放到数组左边，将大于等于基准元素的数放到数组的右边。这样的话，基准元素左边的数都小于自己，基准元素右边的数都大于自己。递归左边的数组和右边的数组，从而实现对整个数组的排序

2. Python实现

2.1 方案一

浅显易懂，患处就是消耗大量内存。


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less_than_pivot, more_than_pivot = [], []
    for i in range(1, len(arr)):
        if arr[i] >= pivot:
            more_than_pivot.append(arr[i])
        else:
            less_than_pivot.append(arr[i])
    # 也可以用下面的方式，注意的是要过滤掉arr[0]元素
    #more_than_pivot = [x for x in arr[1:] if x >= pivot]
    #less_than_pivot = [x for x in arr[1:] if x < pivot]
    return quick_sort(less_than_pivot) + [pivot] + quick_sort(more_than_pivot)

data=[97, 38, 27, 50, 76, 65, 49, 13]
print quick_sort(data)

2.2 方案二

类似于C的实现方式

#寻找分割点
def partition(arr, left, right):
    # 枢纽
    pivot = arr[left] #初始化一个待比较数据
    while left < right:
        while left < right and arr[right] >= pivot: #从后往前查找，直到找到一个比pivot更小的数
            right -= 1
        arr[left] = arr[right]#将更小的数放入左边
        # 必须是<=,不然进入不了循环，因为基准是arr[left]
        while left < right and arr[left] <= pivot:
            left += 1
        arr[right] = arr[left]#将更大的数放入右边
    arr[left] = pivot#待比较数据放入最终位置 
    return left
def quick_sort(arr, left, right):
    if left < right:
        pivot = partition(arr, left, right)
        quick_sort(arr, left, pivot-1)
        quick_sort(arr, pivot+1, right)
data=[97, 38, 27, 50, 76, 65, 49, 13]
quick_sort(data, 0, len(data) - 1)
print data

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left, right = 0, len(arr) -1
    while left < right:
        while left < right and arr[right] >= pivot:
            right -= 1
        arr[left] = arr[right]
        # 必须是<=,不然进入不了循环，因为基准是arr[left]
        while left < right and arr[left] <= pivot:
            left += 1
        arr[right] = arr[left]
    arr[left] = pivot
    # 此处也会比较占内存
    return quick_sort(arr[:left]) + [arr[left]] + quick_sort(arr[left+1:])

data=[97, 38, 27, 50, 76, 65, 49, 13]
print quick_sort(data)

3. Golang实现

3.1 方案一

package main

import (
    "fmt"
)
func partition(arr []int, left, right int) int {
    pivot := arr[left]
    for left < right {
        for left < right && arr[right] >= pivot {
            right--
        }
        arr[left] = arr[right]
        // 必须是<=,不然进入不了循环，因为基准是arr[left]
        for left < right && arr[left] <= pivot {
            left ++
        }
        arr[right] = arr[left]
    }
    arr[left] = pivot
    return left
}

func quickSort(arr []int, left, right int) {
    if left < right {
        pivot := partition(arr, left, right)
        quickSort(arr, left, pivot -1)
        quickSort(arr, pivot+1, right)
    }
}

func main() {
    arr := []int{97, 38, 27, 50, 76, 65, 49, 13}
    quickSort(arr, 0, len(arr) - 1)
    fmt.Println(arr)
}