912. 排序数组

冒泡排序

C++

void bubble_sort(vector<int>& nums) {
    bool sorted = false;
    int N = nums.size();
    while (!sorted) {
        sorted = true;
        for (int i = 1; i < N; i++) {
            if (nums[i - 1] > nums[i]) {
                swap(nums[i - 1], nums[i]);
                sorted = false;
            }
        }
        N--;
    }
}

Python

def bubble_sort(nums):
    N = len(nums)
    sorted = False
    while not sorted:
        sorted = True
        for i in range(1, N):
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i -1]
                sorted = False
        N -= 1

Golang

func bubbleSort(nums []int) {
    N := len(nums)
    sorted := false
    for !sorted {
        sorted = true
        for i := 1; i < N; i++ {
            if nums[i - 1] > nums[i] {
                sorted = false
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
            }
        }
        N--
    }
}

Rust

fn bubble_sort(nums: &mut Vec<i32>) {
    let mut sorted = false;
    let mut N = nums.len();
    while !sorted {
        sorted = true;
        for i in 1..N {
            if nums[i - 1] > nums[i] {
                nums.swap(i - 1, i);
                sorted = false;
            }
        }
        N -= 1;
    }
}

插入排序

C++

void insertion_sort(vector<int>& nums) {
    int t = 0, i = 1, j = 0;
    for (i = 1; i < nums.size(); i++) {
        t = nums[i];
        for (j = i; j > 0 && nums[j - 1] > t; j--) {
            nums[j] = nums[j - 1];
        }
        nums[j] = t;
    }
}

Python

def insertion_sort(nums):
    for i in range(1, len(nums)):
        t = nums[i]
        j = i
        while j > 0 and nums[j - 1] > t:
            nums[j] = nums[j - 1]
            j -= 1
        nums[j] = t

Golang

func insertionSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        t := nums[i]
        j := i
        for j > 0 && nums[j - 1] > t {
            nums[j] = nums[j - 1]
            j--
        }
        nums[j] = t
    }
}

Rust

fn insertion_sort(nums: &mut Vec<i32>) {
    for i in 1..nums.len() {
        let t = nums[i];
        let mut j = i;
        while j > 0 && nums[j - 1] > t {
            nums[j] = nums[j - 1];
            j -= 1;
        }
        nums[j] = t;
    }
}

希尔排序

希尔排序作为插入排序的一种改进，又被称为缩小增量排序，其每次进行增量为 d 的插入排序，d /= 2 向下递减到 1

C++

void shell_sort(vector<int>& nums) {
    int N = nums.size(), d = N >> 1, i = 0, j = 0, t = 0;
    for (; d > 0; d >>= 1) {
        for (i = d; i < N; i++) {
            t = nums[i];
            for (j = i; j >= d && nums[j - d] > t; j -= d) {
                nums[j] = nums[j - d];
            }
            nums[j] = t;
        }
    }
}

Python

def shell_sort(nums):
    N = len(nums)
    d = N >> 1
    while d > 0:
        for i in range(d, N):
            t = nums[i]
            j = i
            while j >= d and nums[j - d] > t:
                nums[j] = nums[j - d]
                j -= d
            nums[j] = t
        d >>= 1

Golang

func shellSort(nums []int) {
    N := len(nums)
    d := N >> 1
    for ; d > 0; d >>= 1 {
        for i := d; i < N; i++ {
            t := nums[i]
            j := i
            for ; j >= d && nums[j - d] > t; j -= d {
                nums[j] = nums[j - d]
            }
            nums[j] = t
        }
    }
}

Rust

fn shell_sort(nums: &mut Vec<i32>) {
    let N = nums.len();
    let mut d = N >> 1;
    while d > 0 {
        for i in d..N {
            let t = nums[i];
            let mut j = i;
            while j >= d && nums[j - d] > t {
                nums[j] = nums[j - d];
                j -= d;
            }
            nums[j] = t;
        }
        d >>= 1;
    }
}

选择排序

C++

int findMin(vector<int>& nums, int l, int r) {
    int min = nums[l], min_pos = l;
    for (int i = l; i <= r; i++ ) {
        if (nums[i] < min) {
            min = nums[i];
            min_pos = i;
        }
    }
    return min_pos;
}

void selectSort(vector<int>& nums) {
    int N = nums.size();
    for (int i = 0; i < N; i++) {
        int min_pos = findMin(nums, i, N - 1);
        swap(nums[i], nums[min_pos]);
    }
}

Python

def findMin(nums, l, r):
    m = nums[l]
    m_pos = l
    for i in range(l, r + 1):
        if nums[i] < m:
            m = nums[i]
            m_pos = i
    return m_pos


def selectSort(nums):
    N = len(nums)
    for i in range(0, N):
        min_pos = findMin(nums, i, N - 1)
        nums[i], nums[min_pos] = nums[min_pos], nums[i]

Golang

func findMin(nums []int, l int, r int) int {
    m := nums[l]
    mp := l
    for i := l; i <= r; i++ {
        if nums[i] < m {
            m = nums[i]
            mp = i
        }
    }
    return mp
}

func selectSort(nums []int) {
    N := len(nums)
    for i := 0; i < N; i++ {
        mp := findMin(nums, i, N - 1)
        nums[i], nums[mp] = nums[mp], nums[i]
    }
}

Rust

fn find_min(nums: &Vec<i32>, l: usize, r: usize) -> usize {
    let mut m = nums[l];
    let mut mp = l;     // min position
    for i in l..(r + 1) {
        if nums[i] < m {
            m = nums[i];
            mp = i;
        }
    }
    mp
}

fn select_sort(nums: &mut Vec<i32>) {
    let N = nums.len();
    for i in 0..N {
        let mp = find_min(nums, i, N - 1);
        nums.swap(i, mp);
    }
}

堆排序

C++

void percolate(vector<int>& nums, int i, int N) {
    int p = i;
    int top = nums[i];
    int c = 0;
    while (p * 2 + 1 < N) {
        c = p * 2 + 1;
        if (c < N - 1 && nums[c + 1] > nums[c]) {
            c++;
        }
        if (nums[c] <= top) {
            break;
        } else {
            nums[p] = nums[c];
        }
        p = c;
    }
    nums[p] = top;
}

void heap_sort(vector<int>& nums) {
    int N = nums.size();
    int i = 0;
    for (i = N / 2; i >= 0; i--) {
        percolate(nums, i, N);
    }

    for (i = N - 1; i > 0; i--) {
        swap(nums[i], nums[0]);
        percolate(nums, 0, i);
    }
}

Python

def percolate(nums, i, N):
    p = i
    top = nums[i]
    c = 0
    while p * 2 + 1 < N:
        c = p * 2 + 1
        if c + 1 < N and nums[c + 1] > nums[c]:
            c += 1
        if nums[c] <= top:
            break
        else:
            nums[p] = nums[c]
        p = c
    nums[p] = top


def heap_sort(nums):
    N = len(nums)
    for i in range(N >> 1, -1, -1):
        percolate(nums, i, N)
    for i in range(N - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        percolate(nums, 0, i)

Golang

func percolate(nums []int, i int, N int) {
    p := i
    top := nums[i]
    c := 0
    for p * 2 + 1 < N {
        c = p * 2 + 1
        if c + 1 < N && nums[c + 1]  > nums[c] {
            c++
        }
        if top >= nums[c] {
            break
        } else {
            nums[p] = nums[c]
        }
        p = c
    }
    nums[p] = top
}

func heapSort(nums []int) {
    N := len(nums)
    for i := N >> 1; i >= 0; i-- {
        percolate(nums, i, N)
    }
    for i := N - 1; i > 0; i-- {
        nums[0], nums[i] = nums[i], nums[0]
        percolate(nums, 0, i)
    }
}

Rust

fn percolate(nums: &mut Vec<i32>, i: usize, N: usize) {
    let mut p = i;
    let top = nums[i];
    let mut c = 0;
    while p * 2 + 1 < N {
        c = p * 2 + 1;
        if c + 1 < N && nums[c + 1] > nums[c] {
            c += 1;
        }
        if top >= nums[c] {
            break;
        } else {
            nums[p] = nums[c];
        }
        p = c
    }
    nums[p] = top;
}

fn heap_sort(nums: &mut Vec<i32>) {
    let N = nums.len();
    for i in (0 as usize..(N >> 1) + 1).rev() {
        percolate(nums, i, N);
    }
    for i in (0..N).rev() {
        nums.swap(0, i);
        percolate(nums, 0, i);
    }
}

归并排序

C++

void merge(vector<int>& nums, int low, int mid, int high) {
    auto it = nums.begin();
    vector<int> L(it + low, it + mid + 1);
    vector<int> R(it + mid + 1, it + high + 1);
    int i = 0, j = 0, k = low;
    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) {
            nums[k++] = L[i++];
        } else {
            nums[k++] = R[j++];
        }
    }
    while (i < L.size()) nums[k++] = L[i++];
    while (j < R.size()) nums[k++] = R[j++];
}

void mergesort(vector<int>& nums, int low, int high) {
    if (low < high) {
        int mid = (low + high) >> 1;
        mergesort(nums, low, mid);
        mergesort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }
}

Python

def merge(nums, l, mid, r):
    left = nums[l: mid + 1]
    right = nums[mid + 1: r + 1]
    i, j, k = 0, 0, l
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            nums[k] = left[i]
            i += 1
        else:
            nums[k] = right[j]
            j += 1
        k += 1
    while i < len(left):
        nums[k] = left[i]
        k += 1
        i += 1
    while j < len(right):
        nums[k] = right[j]
        k += 1
        j += 1

def merge_sort(nums, l, r):
    if l < r:
        mid = (l + r) >> 1
        merge_sort(nums, l, mid)
        merge_sort(nums, mid + 1, r)
        merge(nums, l, mid, r)

Golang

func merge(nums []int, low int, mid int, high int) {
    L := make([]int, mid - low + 1)
    R := make([]int, high - mid)
    copy(L, nums[low: mid + 1])
    copy(R, nums[mid + 1: high + 1])
    i, j, k := 0, 0, low
    for i < len(L) && j < len(R) {
        if L[i] <= R[j] {
            nums[k] = L[i]
            i++
        } else {
            nums[k] = R[j]
            j++
        }
        k++
    }
    for i < len(L) {
        nums[k] = L[i]
        k++
        i++
    }
    for j < len(R) {
        nums[k] = R[j]
        k++
        j++
    }
}

func mergesort(nums []int, low int, high int) {
    if low < high {
        mid := (low + high) >> 1
        mergesort(nums, low, mid)
        mergesort(nums, mid + 1, high)
        merge(nums, low, mid, high)
    }
}

Rust

fn merge(nums: &mut Vec<i32>, l: usize, mid: usize, r: usize) {
    let it = nums.iter();
    let L: Vec<i32> = it.clone().skip(l).take(mid - l + 1).map(|&x| x).collect();
    let R: Vec<i32> = it.clone().skip(mid + 1).take(r - mid).map(|&x| x).collect();

    let mut i = 0;
    let mut j = 0;
    let mut k = l;
    while i < L.len() && j < R.len() {
        if L[i] <= R[j] {
            nums[k] = L[i];
            i += 1;
        } else {
            nums[k] = R[j];
            j += 1;
        }
        k += 1;
    }
    while i < L.len() {
        nums[k] = L[i];
        i += 1;
        k += 1;
    }
    while j < R.len() {
        nums[k] =R[j];
        j += 1;
        k += 1;
    }
}

fn merge_sort(nums: &mut Vec<i32>, l: usize, r: usize) {
    if l < r {
        let mid = (l + r) >> 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }
}

快速排序

naive 实现1（消耗额外空间）

消耗额外的空间，但思路最简单

Golang

func quicksort(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	pivot := nums[0]
	var left, right []int
	for _, e := range nums[1:] {
		if e <= pivot {
			left = append(left, e)
		} else {
			right = append(right, e)
		}
	}
	return append(quicksort(left), append([]int{pivot}, quicksort(right)...)...)
}

Python

def quicksort(nums):
    l = len(nums)
    if l < 2:
        return nums

    p = nums[0]
    left, right = [], []
    for n in nums[1:]:
        if n <= p:
            left.append(n)
        else:
            right.append(n)
    return quicksort(left) + [p] + quicksort(right)

js

function quicksort(nums) {
    let l = nums.length;
    if (l < 2) return nums;
    let pivot = nums[0];
    let left = [], right = [];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] <= pivot) {
            left.push(nums[i]);
        } else {
            right.push(nums[i]);
        }
    }
    return [...quicksort(left), pivot, ...quicksort(right)];
}

naive 实现2（借助 partition）

Python

def partition(nums, l, r):
    pivot = nums[l]
    while l < r:
        while l < r and pivot <= nums[r]:
            r -= 1
        nums[l] = nums[r]
        while l < r and pivot >= nums[l]:
            l += 1
        nums[r] = nums[l]
    nums[l] = pivot
    return l

def quicksort(nums, l, r):
    if (l < r):
        p = partition(nums, l, r)
        quicksort(nums, l, p - 1)
        quicksort(nums, p + 1, r)

C++

int partition(vector<int>& nums, int l, int r) {
    int pivot = nums[l];
    while (l < r) {
        while (l < r && nums[r] >= pivot) r--;
        nums[l] = nums[r];
        while (l < r && nums[l] <= pivot) l++;
        nums[r] = nums[l];
    }
    nums[l] = pivot;
    return l;
}

void quicksort(vector<int>& nums, int l, int r) {
    if (l < r) {
        int p = partition(nums, l, r);
        quicksort(nums, l, p - 1);
        quicksort(nums, p + 1, r);
    }
}

naive 实现3（额外消耗空间+随机选主元）

rand.Seed(time.Now().UnixNano())

func quicksort(nums []int) []int {
    l := len(nums)
	if l < 2 {
		return nums
	}
	p := rand.Intn(l)
	pivot := nums[p]

	var left, right []int
	for i, e := range nums {
        if i == p {
            continue
        }
		if e <= pivot {
			left = append(left, e)
		} else {
			right = append(right, e)
		}
	}
	return append(quicksort(left), append([]int{pivot}, quicksort(right)...)...)
}

标准模板（简洁可AC）

C++

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

Rust

pub fn quicksort(nums: &mut Vec<i32>, l: usize, r: usize) {
    if l >= r {
        return;
    }
    let mut i = l as isize - 1;
    let mut j = r as isize + 1;
    let x = nums[(l + r) >> 1];
    
    while i < j {
        loop {
            i += 1;
            if nums[i as usize] >= x {
                break;
            }
        }
        loop {
            j -= 1;
            if nums[j as usize] <= x {
                break;
            }
        }
        if i < j {
            nums.swap(i as usize, j as usize);
        }
    }
    Self::quicksort(nums, l, j as usize);
    Self::quicksort(nums, j as usize + 1, r);
}

Python

def quicksort(nums, l, r):
    if l >= r:
        return
    i, j = l - 1, r + 1
    x = nums[(l + r) >> 1]
    while i < j:
        i += 1
        while nums[i] < x:
            i += 1
        j -= 1
        while nums[j] > x:
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    quicksort(nums, l, j)
    quicksort(nums, j + 1, r)

Golang

func quicksort(nums []int, l int, r int) {
    if l >= r {
        return
    }
    i := l - 1
    j := r + 1
    x := nums[(l + r) >> 1]
    for i < j {
        for i++; nums[i] < x; i++ {}
        for j--; nums[j] > x; j-- {}
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    quicksort(nums, l, j)
    quicksort(nums, j + 1, r)
}