排序

验证排序算法

快速排序

基于辅助数组实现的快速排序

1. 从数组中随机选择一个基准值t

2. 将小于基准值的元素放到low中，将等于基准值的元素放到mid中，将大于基准值的元素放到high中

3. 递归排序low数组，递归排序high数组

4. 合并数组 low+mid+high

from random import randint


# 借助额外数组，容易理解
def quick_sort_with_help(nums: list) -> list:
    if len(nums) <= 1:
        return nums

    rd = randint(0, len(nums) - 1)

    low = list()
    mid = list()
    high = list()

    for a in nums:
        if a < nums[rd]:
            low.append(a)
        elif a > nums[rd]:
            high.append(a)
        else:
            mid.append(a)

    low = quick_sort_with_help(low)
    high = quick_sort_with_help(high)
    low.extend(mid)
    low.extend(high)
    return low

基于双指针实现的快速排序

1. 判断排序区间是否合法

2. 初始化左右指针

3. 选取目标值（此处选择的是中点，也可以随机选择，但在此代码中请注意选择随机值的范围应该是[left+1, right)）

4. 使left指针指向第一个不小于目标值的元素

5. 使right指针指向第一个不大于目标值的元素

6. 如果left < right则交换两个指针指向的元素

python实现

def quick_sort(nums: list, start: int, end: int):
    if start >= end:
        return

    # 双指针
    left, right = start - 1, end + 1    # 这样初始化是为了减少边界判断

    t = nums[left + ((right - left) >> 1)]

    while left < right:
        left += 1
        while nums[left] < t:
            left += 1

        right -= 1
        while nums[right] > t:
            right -= 1

        if left < right:
            nums[left], nums[right] = nums[right], nums[left]

    quick_sort(nums, start, right)
    quick_sort(nums, right + 1, end)

go实现

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    readInt(reader)
    var x = readArray(reader)
    QuickSort(x, 0, len(x)-1)
    fmt.Println(nums2string(x, " "))
}

func QuickSort(nums []int, start, end int) {
    if start >= end {
        return
    }
    var (
        // 这样初始化是为了减少边界判断
        left  = start - 1
        right = end + 1

        midValue = nums[left+((right-left)>>1)]
    )
    for left < right {
        left++
        // 寻找左边不小于midValue的元素，往右移动
        for nums[left] < midValue {
            left++
        }

        right--
        // 寻找右边不大于midValue的元素，往左移动
        for nums[right] > midValue {
            right--
        }

        if left < right {
            nums[left], nums[right] = nums[right], nums[left]
        }
    }
    QuickSort(nums, start, right)
    QuickSort(nums, right+1, end)
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var num, _ = strconv.Atoi(readLine(reader))
    return num
}

func readArray(reader *bufio.Reader) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, " ")
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

func nums2string(x []int, sep string) string {
    var b strings.Builder
    for i := 0; i < len(x); i++ {
        b.WriteString(strconv.Itoa(x[i]))
        b.WriteString(sep)
    }
    return b.String()
}

归并排序

基于分治实现的归并排序

1. 折半拆分数组，排序左半边数组，排序右半边数组

2. 外排合并左半边数组和右半边数组

python实现

def merge_sort(nums: list) -> list:
    if len(nums) <= 1:
        return nums
    mid = len(nums) >> 1
    return merge(merge_sort(nums[:mid]), merge_sort(nums[mid:]))


def merge(a: list, b: list) -> list:
    ans = list()
    ai = bi = 0
    while ai < len(a) and bi < len(b):
        if a[ai] <= b[bi]:
            ans.append(a[ai])
            ai += 1
        else:
            ans.append(b[bi])
            bi += 1

    if ai < len(a):
        ans.extend(a[ai:])

    if bi < len(b):
        ans.extend(b[bi:])

    return ans

go实现

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    readInt(reader)
    var x = readArray(reader)
    fmt.Println(nums2string(MergeSort(x), " "))
}

func MergeSort(x []int) []int {
    if len(x) <= 1 {
        return x
    }
    return merge(MergeSort(x[0:len(x)>>1]), MergeSort(x[len(x)>>1:]))
}

func merge(a, b []int) []int {
    var (
        i   int
        j   int
        ans []int
    )

    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            ans = append(ans, a[i])
            i++
        } else {
            ans = append(ans, b[j])
            j++
        }
    }

    if i < len(a) {
        ans = append(ans, a[i:]...)
    }

    if j < len(b) {
        ans = append(ans, b[j:]...)
    }
    return ans
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var num, _ = strconv.Atoi(readLine(reader))
    return num
}

func readArray(reader *bufio.Reader) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, " ")
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

func nums2string(x []int, sep string) string {
    var b strings.Builder
    for i := 0; i < len(x); i++ {
        b.WriteString(strconv.Itoa(x[i]))
        b.WriteString(sep)
    }
    return b.String()
}

逆序对的数量

python3实现

cnt = 0

def merge_sort(nums: list) -> list:
    if len(nums) <= 1:
        return nums
    mid = len(nums) >> 1
    return merge(merge_sort(nums[:mid]), merge_sort(nums[mid:]))


def merge(a: list, b: list) -> list:
    ans = list()
    ai = bi = 0
    while ai < len(a) and bi < len(b):
        if a[ai] <= b[bi]:
            ans.append(a[ai])
            ai += 1
        else:
            ans.append(b[bi])
            global cnt
            cnt += len(a) - ai
            bi += 1

    if ai < len(a):
        ans.extend(a[ai:])

    if bi < len(b):
        ans.extend(b[bi:])

    return ans

input()
nums = [int(x) for x in input().split(" ")]
merge_sort(nums)
print(cnt)

go实现

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var c int

func main() {
    var reader = bufio.NewReader(os.Stdin)
    readInt(reader)
    var x = readArray(reader)
    MergeSort(x)
    fmt.Println(c)
    c = 0
}

func MergeSort(x []int) []int {
    if len(x) <= 1 {
        return x
    }
    return merge(MergeSort(x[0:len(x)>>1]), MergeSort(x[len(x)>>1:]))
}

func merge(a, b []int) []int {
    var (
        i   int
        j   int
        ans []int
    )

    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            ans = append(ans, a[i])
            i++
        } else {
            // a[i:]列表中的元素与b[j]都构成逆序对
            ans = append(ans, b[j])
            c += len(a[i:])
            j++
        }
    }

    if i < len(a) {
        ans = append(ans, a[i:]...)
    }

    if j < len(b) {
        ans = append(ans, b[j:]...)
    }
    return ans
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var num, _ = strconv.Atoi(readLine(reader))
    return num
}

func readArray(reader *bufio.Reader) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, " ")
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

func nums2string(x []int, sep string) string {
    var b strings.Builder
    for i := 0; i < len(x); i++ {
        b.WriteString(strconv.Itoa(x[i]))
        b.WriteString(sep)
    }
    return b.String()
}