排序——快速排序/QuickSort

概述

快速排序的核心思想就是分治。把复杂的问题分割成若干个同样的简单的问题，化繁为简。
对于长度为 1 或者为 0 的数组的排序是最简单的。因为，它们根本不再需要排序。所以，快速排序就要想尽办法，利用分治，分割成长度为1或者0 的排序。

算法步骤

1. 设置基准值从数列中挑出一个元素，称为 “基准”（pivot）;
2. 分区（partition）操作,重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）操作递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

时间复杂度

快速排序的时间复杂度是
快速排序最糟糕的情况是算法复杂度是
快速排序会进行多趟，每一趟的时间复杂度是 O(n)，递归调用的次数相当于递归树的层数,所以总共的复杂度就是。

以数组int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 }为例：

以第一个数字6作为基数，使用双指针i,j进行双向遍历：

• 1、i从左往右寻找第一位大于基数（6）的数字，j从右往左寻找第一位小于基数（6）的数字；
  
• 2、找到后将两个数字进行交换。继续循环交换直到i>=j结束循环；
  
• 3、最终指针i=j,此时交换基数和i(j)指向的数字即可将数组划分为小于基数（6）/基数（6）/大于基数（6）的三部分，即完成一趟快排；
  

Java

public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        return quickSort(arr, 0, arr.length - 1);
    }
    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }
    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

Python

def quick_sort(arr):
    """快速排序"""
    if len(arr) < 2:
        return arr
    # 选取基准，随便选哪个都可以，选中间的便于理解
    mid = arr[len(arr) // 2]
    # 定义基准值左右两个数列
    left, right = [], []
    # 从原始数组中移除基准值
    arr.remove(mid)
    for item in arr:
        # 大于基准值放右边
        if item >= mid:
            right.append(item)
        else:
            # 小于基准值放左边
            left.append(item)
    # 使用迭代进行比较
    return quick_sort(left) + [mid] + quick_sort(right)

func quickSort(arr []int)[]int{
    if len(arr) <2{// 一个元素不需要排序 直接返回
        return arr
    }
    pivot :=arr[0]
    var left []int //小于基准值
    var mid []int // 等于基准值
    var right []int // 大于基准值
    for _,v :=range arr{
        if v<pivot {
            left = append(left,v)
        }else if v>pivot{
            right = append(right,v)
        }else {
            mid = append(mid,v)
        }
    }
     l :=quickSort(left)
     l = append(l,mid...)
     r :=quickSort(right)
    return append(l,r...)
}

package main

import (
    "fmt"
    "sort"
)
func getLeastNumbers0(arr []int, k int) []int {
    sort.Sort(Array(arr))
    return arr[:k]
}

type Array []int

func (a Array) Len() int           { return len(a) }
func (a Array) Less(i, j int) bool { return a[i] < a[j] }
func (a Array) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }


func getLeastNumbers(arr []int, k int) []int {
    sort.Ints(arr)
    return arr[:k]
}
func getLeastNumbers1(arr []int, k int) []int {
    //sort.Ints(arr)
    arr = quickSort(arr)
    return arr[:k]
}

func quickSort(arr []int)[]int{
    if len(arr) <2{// 一个元素不需要排序 直接返回
        return arr
    }
    pivot :=arr[0]
    var left []int //小于基准值
    var mid []int // 等于基准值
    var right []int // 大于基准值
    for _,v :=range arr{
        if v<pivot {
            left = append(left,v)
        }else if v>pivot{
            right = append(right,v)
        }else {
            mid = append(mid,v)
        }
    }
    return append(append(quickSort(left),mid...),quickSort(right)...)
}

//面试题40. 最小的k个数 https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
func main() {
    fmt.Println(getLeastNumbers([]int{3,2,1},2))
}

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func RandArray(num int) []int {
    arr := make([]int, num)
    //以当前时间为随机数种子
    rand.Seed(time.Now().Unix())

    for i := 0; i < num; i++ {
        arr[i] = rand.Intn(100)

    }
    return arr

}

//来源于WIKI 网站
func quic_wiki(data []int) []int {
    if len(data) <= 1 {
        return data
    }
    mid := data[0]
    head, tail := 0, len(data)-1
    for i := 1; i <= tail; {
        if data[i] > mid {
            data[i], data[tail] = data[tail], data[i]
            tail--
        } else {
            data[i], data[head] = data[head], data[i]
            head++
            i++
        }
    }
    data[head] = mid
    quic_wiki(data[:head])
    quic_wiki(data[head+1:])
    return data

}

func quick_sort(arr []int) []int {

    if len(arr) <= 1 {
        return arr
    }

    median := arr[rand.Intn(len(arr))]
    //fmt.Printf("par: %v\n", median)

    low_part := make([]int, 0, len(arr))
    high_part := make([]int, 0, len(arr))
    middle_part := make([]int, 0, len(arr))

    for _, item := range arr {
        switch {
        case item < median:
            low_part = append(low_part, item)
        case item == median:
            middle_part = append(middle_part, item)
        case item > median:
            high_part = append(high_part, item)
        }
    }

    low_part = quick_sort(low_part)
    high_part = quick_sort(high_part)

    low_part = append(low_part, middle_part...)
    low_part = append(low_part, high_part...)

    return low_part
}
func main() {
    fmt.Println("Quick sort algorithm \n")
    arr := RandArray(13)
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    fmt.Println(" wiki  Sorted  array is: ", quic_wiki(arr))

    fmt.Println("")
    fmt.Println(" others Sorted array is: ", quick_sort(arr))

}

参考

https://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html