rust 解法, 执行用时: 60 ms, 内存消耗: 2.7 MB, 提交时间: 2023-09-15 15:41:52

impl Solution {
    // 堆排序（超时）
    pub fn sort_array1(mut nums: Vec<i32>) -> Vec<i32> {
        if nums.len() <= 1 { return nums; }
        Solution::modify_by_left(&mut nums[..]);
        nums
    }

    fn modify_by_left(s: &mut [i32]) {
        let (mut i, mut j) = (0, s.len()-1);
        loop {
            while i != j {
                if s[j] <= s[0] { break; }
                j -= 1;
            }
            while i != j {
                if s[i] > s[0] { break; }
                i += 1;
            }
            if i == j { break; }
            s.swap(i, j);
        }
        s.swap(0, i);
        if i > 1 { Solution::modify_by_left(&mut s[0..i]); }
        if s.len() - i > 2 { Solution::modify_by_left(&mut s[i+1..]); }        
    }
    
    
    // 快速排序（超内存）
    pub fn sort_array2(nums: Vec<i32>) -> Vec<i32> {
        let mut vec_result = nums.to_owned();
        //vec_result.sort();
        vec_result = Self::quick_sort(nums);
        vec_result
    }
    pub fn quick_sort(nums: Vec<i32>) -> Vec<i32> {
        if nums.len() <= 1 {
            return nums;
        }
        let mut vec1: Vec<i32> = Vec::new();
        let mut vec2: Vec<i32> = Vec::new();
        for  i in 1..nums.len() {
            if nums[i] >= nums[0] {
                vec2.push(nums[i]);
            } else {
                vec1.push(nums[i]);
            }
        }
        let mut result = Self::quick_sort(vec1);
        result.push(nums[0]);
        result.append(&mut Self::quick_sort(vec2));
        
        //println!("{:?}",result);
        result
    }
    
    // 归并排序
    pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
        fn merge_sort(nums:&mut Vec<i32>, p:usize, q:usize){
            if p >= q-1 {return;}
            let r = p + ((q-p) >> 1);
            merge_sort(nums,p,r);
            merge_sort(nums,r,q);
            merge(nums,p,r,q);
        }
        
        fn merge(nums:&mut Vec<i32>, p:usize, q:usize, r:usize){
            let mut cpa = nums.get(p..q).unwrap().to_vec();
            let mut cpb = nums.get(q..r).unwrap().to_vec();
            let n = r - p;
            let mut i = 0;
            let mut j = 0;
            for k in p..p+n{
                if i == q-p {
                    nums[k] = cpb[j];
                    j+=1;
                }else if j == r-q{
                    nums[k] = cpa[i];
                    i+=1; 
                }else if cpa[i] < cpb[j]{
                    nums[k] = cpa[i];
                    i+=1; 
                }else{
                    nums[k] = cpb[j];
                    j+=1;
                }
            }
        }
        let n = nums.len();
        merge_sort(&mut nums,0,n);
        nums
    }
}

golang 解法, 执行用时: 148 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-15 15:38:01

func sortArray(nums []int) []int {
    heapSort(nums)
    return nums
}

// 堆排序
func heapSort(nums []int) []int {
    end := len(nums) - 1
    for i := end / 2; i >= 0; i-- {
        sink(nums, i, end)
    }
    for i := end; i >= 0; i-- {
        nums[0], nums[i] = nums[i], nums[0]
        end--
        sink(nums, 0, end)
    }
    return nums
}

func sink(heap []int, root, end int) {
    for {
        child := root * 2 + 1
        if child > end {
            return
        }
        if child < end && heap[child] <= heap[child + 1] {
            child++
        }
        if heap[root] > heap[child] {
            return
        }
        heap[root], heap[child] = heap[child], heap[root]
        root = child
    }
}

// 快速排序
func quickSort(nums []int, left, right int) {
    if left > right {
        return
    }
    i, j, base := left, right, nums[left]
    for i < j {
        for nums[j] >= base && i < j {
            j--
        }
        for nums[i] <= base && i < j {
            i++
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    nums[i], nums[left] = nums[left], nums[i]
    quickSort(nums, left, i - 1)
    quickSort(nums, i + 1, right)
}

// 归并排序
func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    mid := len(nums) / 2
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, len(left) + len(right))
    l, r, i := 0, 0, 0
    for l < len(left) && r < len(right) {
        if left[l] < right[r] {
            result[i] = left[l]
            l++
        } else {
            result[i] = right[r]
            r++
        }
        i++
    }
    copy(result[i:], left[l:])
    copy(result[i+len(left)-l:], right[r:])
    return result
}

cpp 解法, 执行用时: 112 ms, 内存消耗: 57.7 MB, 提交时间: 2022-12-09 15:55:34

// 基数排序
class Solution {
    vector<int> counts;
    void radixSort(vector<int>& nums, vector<int>& tmp, int divisor) {
        int n = nums.size();
        counts = vector<int>(10, 0);
        // 统计个、十、百、千、万上对应 0 ~ 9 的出现次数
        for (int i = 0; i < n; ++i) {
            int x = (nums[i] / divisor) % 10;
            if (x != 9) ++counts[x + 1];
        }
        // 前缀和
        for (int i = 1; i <= 9; ++i) {
            counts[i] += counts[i - 1];
        }
        // 从前向后赋值
        for (int i = 0; i < n; ++i) {
            int x = (nums[i] / divisor) % 10;
            tmp[counts[x]++] = nums[i];  
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        // RadixSort 基数排序
        int n = nums.size();
        // 预处理，让所有的数都大于等于0
        for (int i = 0; i < n; ++i) {
            nums[i] += 50000; // 50000为最小可能的数组大小
        }
        // 找出最大的数字，并获得其最大位数
        int maxNum = nums[0];
        for (int i = 0; i < n; ++i) {
            if (nums[i] > maxNum) {
                maxNum = nums[i];
            }
        }
        int num = maxNum, maxLen = 0;
        while (num) {
            ++maxLen;
            num /= 10;
        }
        // 基数排序，低位优先
        int divisor = 1;
        vector<int> tmp(n, 0);
        for (int i = 0; i < maxLen; ++i) {
            radixSort(nums, tmp, divisor);
            swap(tmp, nums);
            divisor *= 10;
        }
        // 减去预处理量
        for (int i = 0; i < n; ++i) {
            nums[i] -= 50000;
        }
        return nums;
    }
};

cpp 解法, 执行用时: 104 ms, 内存消耗: 60.9 MB, 提交时间: 2022-12-09 15:55:08

// 桶排序
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // BucketSort 桶排序
        int n = nums.size();
        // 获取数组的最小值和最大值
        int maxNum = nums[0], minNum = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > maxNum) maxNum = nums[i];
            if (nums[i] < minNum) minNum = nums[i];
        }
        // 初始化桶
        int bucketNum = 5, bucketSize = (maxNum - minNum) / bucketNum + 1;
        vector<vector<int>> buckets(bucketNum, vector<int>(0));
        // 小至大分桶
        for (int num : nums) {
            int bucketIndex = (num - minNum) / bucketSize;
            buckets[bucketIndex].emplace_back(num);
        }
        // 桶内排序
        for (int i = 0; i < buckets.size(); ++i) {
            sort(buckets[i].begin(), buckets[i].end());
        }
        // 从桶中依次取数
        int index = 0;
        for (auto& bucket : buckets) {
            for (int num : bucket) {
                nums[index++] = num;
            }
        }

        return nums;
    }
};

cpp 解法, 执行用时: 68 ms, 内存消耗: 57.4 MB, 提交时间: 2022-12-09 15:54:44

// 计数排序
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // CountSort 计数排序
        int n = nums.size();
        int minNum = INT_MAX, maxNum = INT_MIN;
        // 找到数组中的最小和最大元素
        for (int i = 0; i < n; ++i) {
            if (nums[i] < minNum) minNum = nums[i];
            if (nums[i] > maxNum) maxNum = nums[i];
        }
        // 构造计数数组
        vector<int> counts(maxNum - minNum + 1, 0);
        for (int i = 0; i < n; ++i) {
            ++counts[nums[i] - minNum];
        }
        // 计数排序
        int index = 0;
        for (int i = 0; i < counts.size(); ++i) {
            while (counts[i] != 0) {
                nums[index++] = i + minNum;
                counts[i]--;
            }
        }
        return nums;
    }
};

cpp 解法, 执行用时: 176 ms, 内存消耗: 55.8 MB, 提交时间: 2022-12-09 15:53:56

// shell排序
class Solution {
    void shellSort(vector<int>&nums, int gap, int i) {
        int j, tmp = nums[i];
        for (j = i - gap; j >= 0 && tmp < nums[j]; j -= gap) {
            // 依次后移
            nums[j + gap] = nums[j];
        }
        nums[j + gap] = tmp;
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        // 分组，最开始时，间隔 gap 为数组的一半
        for (int gap = n / 2; gap >= 1 ; gap /= 2) {
            // 对各个分组进行插入分组
            for (int i = gap; i < n; ++i) {
                shellSort(nums, gap, i);
            }
        }
        return nums;
    }
};

python3 解法, 执行用时: 1400 ms, 内存消耗: 21.6 MB, 提交时间: 2022-12-09 15:50:47

'''
堆排序
'''
class Solution:
    def max_heapify(self, heap, root, heap_len):
        p = root
        while p * 2 + 1 < heap_len:
            l, r = p * 2 + 1, p * 2 + 2
            if heap_len <= r or heap[r] < heap[l]:
                nex = l
            else:
                nex = r
            if heap[p] < heap[nex]:
                heap[p], heap[nex] = heap[nex], heap[p]
                p = nex
            else:
                break
        
    def build_heap(self, heap):
        for i in range(len(heap) - 1, -1, -1):
            self.max_heapify(heap, i, len(heap))

    def heap_sort(self, nums):
        self.build_heap(nums)
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            self.max_heapify(nums, 0, i)
            
    def sortArray(self, nums: List[int]) -> List[int]:
        self.heap_sort(nums)
        return nums

python3 解法, 执行用时: 1016 ms, 内存消耗: 21.6 MB, 提交时间: 2022-12-09 15:50:30

'''
归并排序
'''
class Solution:
    def merge_sort(self, nums, l, r):
        if l == r:
            return
        mid = (l + r) // 2
        self.merge_sort(nums, l, mid)
        self.merge_sort(nums, mid + 1, r)
        tmp = []
        i, j = l, mid + 1
        while i <= mid or j <= r:
            if i > mid or (j <= r and nums[j] < nums[i]):
                tmp.append(nums[j])
                j += 1
            else:
                tmp.append(nums[i])
                i += 1
        nums[l: r + 1] = tmp

    def sortArray(self, nums: List[int]) -> List[int]:
        self.merge_sort(nums, 0, len(nums) - 1)
        return nums

java 解法, 执行用时: 23 ms, 内存消耗: 50.7 MB, 提交时间: 2022-12-09 15:50:03

class Solution {
    int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int i = l, j = mid + 1;
        int cnt = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[cnt++] = nums[i++];
            } else {
                tmp[cnt++] = nums[j++];
            }
        }
        while (i <= mid) {
            tmp[cnt++] = nums[i++];
        }
        while (j <= r) {
            tmp[cnt++] = nums[j++];
        }
        for (int k = 0; k < r - l + 1; ++k) {
            nums[k + l] = tmp[k];
        }
    }
}

java 解法, 执行用时: 34 ms, 内存消耗: 51.4 MB, 提交时间: 2022-12-09 15:49:49

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    public void heapSort(int[] nums) {
        int len = nums.length - 1;
        buildMaxHeap(nums, len);
        for (int i = len; i >= 1; --i) {
            swap(nums, i, 0);
            len -= 1;
            maxHeapify(nums, 0, len);
        }
    }

    public void buildMaxHeap(int[] nums, int len) {
        for (int i = len / 2; i >= 0; --i) {
            maxHeapify(nums, i, len);
        }
    }

    public void maxHeapify(int[] nums, int i, int len) {
        for (; (i << 1) + 1 <= len;) {
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;
            int large;
            if (lson <= len && nums[lson] > nums[i]) {
                large = lson;
            } else {
                large = i;
            }
            if (rson <= len && nums[rson] > nums[large]) {
                large = rson;
            }
            if (large != i) {
                swap(nums, i, large);
                i = large;
            } else {
                break;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

java 解法, 执行用时: 1248 ms, 内存消耗: 56.1 MB, 提交时间: 2022-12-09 15:49:31

class Solution {
    public int[] sortArray(int[] nums) {
        randomizedQuicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void randomizedQuicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuicksort(nums, l, pos - 1);
            randomizedQuicksort(nums, pos + 1, r);
        }
    }

    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

python3 解法, 执行用时: 72 ms, 内存消耗: 21.4 MB, 提交时间: 2022-12-09 15:48:54

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        return nums