排序

归并排序

• 分解
• 排序
• 合并

void merge(int[] arr, int l, int mid, int r){
    int n1 = l;
    int n2 = mid + 1;
    
    int help[r - l + 1];
    int i = 0;
    while (n1 <= mid && n2 <= r){
        help[i++] = arr[n1] < arr[n2] ? arr[n1++] : arr[n2++];
    }
    while (n1 <= mid){
        help[i++] = arr[n1++];
    }
    while (n2 <= r){
        help[i++] = arr[n1++];
    }
    for (int i = 0; i < r; i++){
        arr[l+i] = help[i];
    }
}

void mergeSort(int[] arr, int l, int r){
    if (l == r){
        return ;
    }
    int mid = l + ((r - l) >> 1);	//防止溢出、速度快
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1; r);
    merge(arr, l, mid, r);
    return ;
}

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$

快速排序

随机选一个数放到最后并且用来分区，其中$\lt$的放最左边，$\gt$的放右边，$=$的放中间，然后递归左右两侧

时间复杂度：$O(nlogn)$

空间复杂度：$O(logn)$

pair<int, int> partition3(int arr[], int left, int right) {
    // 随机选 pivot 并放到最右边
    int pivotIndex = left + rand() % (right - left + 1);
    swap(arr[right], arr[pivotIndex]);
    int pivot = arr[right];

    int lt = left;      // < pivot 区间的最后一个位置
    int gt = right;     // > pivot 区间的第一个位置
    int i = left + 1;   // 当前扫描元素

    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[i], arr[lt]);
            lt++;
            i++;
        }
        else if (arr[i] > pivot) {
            swap(arr[i], arr[gt]);
            gt--;
        } 
        else {
            i++;
        }
    }
    // 返回等于 pivot 的区间
    return {lt, gt};
}

// 三路快速排序
void quickSort3Way(int arr[], int left, int right) {
    if (left >= right) return;

    pair<int, int> mid = partition3(arr, left, right);
    int lt = mid.first, gt = mid.second;

    quickSort3Way(arr, left, lt - 1);  // < pivot
    quickSort3Way(arr, gt + 1, right); // > pivot
}

堆排序

堆结构

• 完全二叉树
• 左子结点：2 * i + 1
• 右子节点：2 * i + 2
• 父节点：(i - 1) / 2

将数组作为大根堆并插入（向上调整）

void heapInsert(int[] arr, int index){
    while (arr[index] > arr[(index - 1) / 2]){
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

将数组调整成堆（向下调整）

void heapify(int[] arr, int index, int heapSize){
    int left = index * 2 + 1;
    while (left < heapSize){
        //比较左子结点和右子节点（判断存在）
        int largest = left + 1 < heapSize && arr[left +1] > arr[left] ? left + 1 : left;
    	
        //比较父节点和大子节点
        largest = arr[largest] > arr[index] ? largest : index;
        
        if (largest == index){
            break;
        }
        swap(arr, index, largest);
        index = largest;
        left = index * 2 + 1;
    }
}

排序

1. 通过index从0到size进行heapInsert来构建大根堆
2. 将根节点与末尾进行交换，并且heapSize–
3. 从根节点开始heapify
4. 循环2、3步

void heapSort(int[] arr){
    if (arr == null || arr.length < 2){
        return;
    }
    for (int i = 0; i < arr.length; i++){	//O(n)
        heapInsert(arr, i);		//O(logn)
    }
    //如果给定全部数组而不是一个一个元素，则上面for循环可以优化成O(n)，但排序复杂度仍为O(nlogn)
    //for (int i = arr.length - 1; i >= 0; i--){
    //    heapify(arr, i, arr.length);
    //}
    int heapSise = arr.length;
    swap(arr, 0, --heapSize);	
    while (heapSize > 0){	//O(n)
        heapify(arr, 0, heapsize);		//O(logn)
        swap(arr, 0, --heapSize);		//O(1)
    }
}

• 时间复杂度：$O(nlogn)$
• 空间复杂度： $O(1)$

优先级队列就是堆

基数排序

1. 将待排序的数字按“位数”拆分（从低位到高位，或从高位到低位）。
2. 按某一位的数值，把元素分配到 0–9 的桶（对十进制）中。
3. 收集所有桶内的元素，按顺序合并。
4. 继续处理下一位，直到最高位。

void radixSort(int[] arr, int L, int R, int digit){
    const int radix = 10;
    int i = 0;
    int j = 0;
    int[] bucket = new int[R - L + 1];
    for (int d = 1; d <= digit; d++){	//出桶入桶次数
        int[] count = new int[radix];	//count[0..9]
        for (i = L; i <= R; i++){	//对应计数
            j = getDigit(arr[i], d);
            count[j]++;
        }
        for (i = 1; i < radix; i++){	//将当前位计数改为小于等于的所有计数
            count[i] = count[i] + count[i - 1];
        }
        for (i = R; i >= L; i--){	//逆序分区放bucket临时数组
            j = bucket[count[j] - 1] = arr[i];
            count[j]--;
        }	
        for (i = L, j = 0; i <= R; i++, j++){	//bucket中放回原数组
            arr[i] = bucket[j];
        }
    }
}

排序算法稳定性

在值相同的情况下，保证排序后相对顺序不变

• 有稳定性：冒泡排序、插入排序、归并排序、计数排序、基数排序
• 无稳定性：选择排序、快速排序、堆排序

没有时间复杂度是$O(nlogn)$、空间复杂度是$O(1)$且稳定的排序