思路1：快速排序
while 1-while结构
注意不要对nums[:]这种进行浅复制
注意边界判断、哨兵归位、分成3段哨兵不动
思路2：归并排序
while-if结构
不断二分数组，直到只剩单元素数组。
不断合并两个有序的数组成为一个有序的数组。
思路3：堆排序
核心操作是对节点进行下沉操作
思路4：计数排序 counting sort
对每个数值进行hash映射，使用count统计每个数值出现次数，
count.size() = m = max - min + 1
时间复杂度：O(n+m)
额外空间复杂度：O(m)
思路5：基数排序 radix sort
额外空间复杂度：O(n+k)，k是桶的数量
1、负数处理
[1]int转unsigned int，使用unsigned int处理负数
[2]使用额外的桶处理负数
2、小数处理
IEEE 754标准的小数，除去符号位，可以直接排序。
符号位处理参考负数，使用bit_cast将float转化为unsigned int或者使用额外的桶。
3、进制选择
10进制、256进制、65536进制。

思路6：桶排序 bucket sort

###快速排序###
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quickSort(nums, 0, len(nums))
        return nums

    def quickSort(self, nums, l, r): #对nums[l:r]排序，左闭右开
        if l >= r - 1: return
        sent = nums[l] #哨兵，一部分小于哨兵，另一部分大于等于哨兵
        i, j= l + 1, r - 1 # l是哨兵位置，不参与排序, r是越界位置，不能排序
        while 1:
            while i < r and nums[i] < sent: i += 1
            while j > l and nums[j] >= sent: j -= 1
            if l < i < j < r: nums[i], nums[j] = nums[j], nums[i]
            else: break
        nums[l], nums[j] = nums[j], nums[l] # nums[j]原来小于nums[s]，把哨兵放回目标位置
        # 把nums分成3段，小于哨兵，哨兵，大于等于哨兵
        self.quickSort(nums, l, j)
        self.quickSort(nums, j+1, r) #哨兵最终位置确定了，哨兵不参与下一次排序

###归并排序###
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.mergeSort(nums)
    def mergeSort(self, nums):
        if not nums: return []
        n = len(nums)
        mid = n >> 1
        if n == 1: return [nums[0]]
        numA = self.mergeSort(nums[0:mid]) #长度是mid
        numB = self.mergeSort(nums[mid:n]) #长度是n - mid
        res = [] #注意mergeSort需要O(n)空间，不是原地排序
        a, b = 0, 0
        while a < mid or b < n - mid:
            if b >= n - mid or (a < mid and numA[a] < numB[b]): #从两个数中选择小的那个加入
                res.append(numA[a])
                a += 1
            else:
                res.append(numB[b])
                b += 1
        return res

###堆排序###   
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.heapSort(nums)

    def heapDown(self, nums, n, i): #对nums[:n][i]节点下沉操作（最大堆）
        largest = i #largest存储最大数下标
        l, r = 2 * i + 1, 2 * i + 2 #左右子节点
        if l < n and nums[l] > nums[largest]:
            largest = l
        if r < n and nums[r] > nums[largest]:
            largest = r
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i] #交换节点位置
            self.heapDown(nums, n, largest) #对原nums[i]继续下沉
    def createHeap(self, nums): #将nums[:n] 变为最大堆
        n = len(nums)
        if n <= 0: return []
        for i in range(n-1,-1,-1): #从最后叶节点开始，逐个下沉
            self.heapDown(nums, n, i)
        return nums #原地更改
    def heapSort(self, nums): #最大堆变成递增序列
        if not nums: return []
        n = len(nums)
        nums = self.createHeap(nums) #建立最大堆
        for i in range(n-1, -1, -1): #不断取出根节点
            nums[0], nums[i] = nums[i], nums[0] #交换根节点和最后一个叶节点
            self.heapDown(nums, i, 0)
        return nums

/*计数排序*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();

        int minNum = nums[0], maxNum = nums[0];
        for(int num:nums){
            minNum = min(minNum, num);
            maxNum = max(maxNum, num);
        }
        int range = maxNum - minNum + 1;
        vector<int> cnt(range, 0);
        for(int num: nums) cnt[num-minNum] ++; // 统计每个数值出现次数
        for(int i = 1; i < range; i ++) cnt[i] += cnt[i-1]; // 前缀和，数量->下标

        vector<int> ans(n); // 不使用二维数组代表桶
        for(int i = n-1; i >= 0; i --) { // 分桶，反向填充保证稳定性
            int idx = nums[i] - minNum;
            ans[--cnt[idx]] = nums[i]; 
        }

        return ans;
    }
};
/*基数排序1*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        int max = abs(nums[0]);
        for(int i = 1; i < n; i ++) // 统计最大的绝对值，方便计算最大位数
            if(max < abs(nums[i])) max = abs(nums[i]);

        int epoch = 0; // 最大值对应的十进制位数
        while(max > 0) {
            max /= 10;
            epoch ++;
        }
        int flag = 1;
        vector<int> ans(n); // 不使用二维数组代表桶
        for(int i = 0; i < epoch; i ++) {
            vector<int> cnt(19, 0); // 十进制基数排序对应19个桶，-9 ~ 9，桶中存的是对应元素排序后的下标
            for(int j=0; j<n; j ++) { // 统计每个桶存多少个元素
                int idx = nums[j] / flag % 10 + 9;
                cnt[idx] ++;
            }
            for(int j = 1; j < 19; j ++) cnt[j] += cnt[j-1]; // 前缀和，数量->下标
            for(int j = n-1; j >= 0; j --) { // 分桶，反向填充保证稳定性
                int idx = nums[j] / flag % 10 + 9;
                ans[--cnt[idx]] = nums[j];
            }
            nums = ans;
            flag *= 10;
        }
        return nums;
    }
};
/*基数排序2*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        using uint = unsigned int;
        int n = nums.size();
        vector<uint> cpy(n), ans(n); // 不使用二维数组代表桶
        for (int i = 0; i < n; i ++) // 处理负数，int转换为uint，使用cpy代替nums
            cpy[i] = nums[i] ^ 0x80000000;

        // 不计算最大值，对所有32位进行排序；base代表进制，epoch = ceil(32/base)
        // int base = 256, epoch = 4, mask = 0xff, bit_num = 8; // 256进制
        int base = 65536, epoch = 2, mask = 0xffff, bit_num = 16; // 65535进制
        for(int i = 0; i < epoch; i ++) {
            vector<int> cnt(base, 0); // base进制基数排序对应base个桶，0 ~ base-1，桶中存的是对应元素排序后的下标
            for(int j = 0; j < n; j ++) { // 统计每个桶存多少个元素
                int idx = cpy[j] >> (bit_num * i) & mask;
                cnt[idx] ++;
            }
            for(int j = 1; j < base; j ++) cnt[j] += cnt[j-1]; // 前缀和，数量->下标
            for(int j = n-1; j >= 0; j --) { // 分桶，反向填充保证稳定性
                int idx = cpy[j] >> (bit_num * i) & mask;
                ans[--cnt[idx]] = cpy[j];
            }
            cpy = ans;
        }
        for (int i = 0; i < n; i ++) // uint转换为int
            nums[i] = cpy[i] ^ 0x80000000;
        return nums;
    }
};
/*桶排序*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return nums;
        vector<int> cnt(11, 0), bucket(11, 0); // 10个桶，m=10
        int maxn = nums[0], minn = nums[0];
        for (auto &x:nums) {
            maxn = max(x, maxn);
            minn = min(x, minn);
        }
        int range = maxn - minn + 1; // 总宽度
        int len = (range + 9) / 10; // 每个桶的宽度，len = ceil(range/m) = (range+m-1) / m

        for (auto &x: nums) {
            int idx = (x - minn) / len; // 0 ~ m-1号桶
            cnt[idx+1] ++; // 0 ~ m-1转为1~m号桶
        }

        for(int i = 1; i < 11; i ++) { // 前缀和，数量->下标
            // cnt和bucket一致，cnt用于分桶，bucket用于桶内排序
            cnt[i] += cnt[i-1]; 
            bucket[i] = cnt[i];
        }

        vector<int> ans(n, 0);
        for(int i = n-1; i >= 0; i --) { // 分桶，每个桶代表ans的一段，反向填充保证稳定性
            int idx = (nums[i] - minn) / len;
            ans[--cnt[idx+1]] = nums[i]; 
        }
        nums = ans;
        for (int i = 1; i < 11; i ++) // 桶内排序
            sort(nums.begin()+bucket[i-1], nums.begin()+bucket[i]);

        return nums;
    }
};