排序.md

排序

题目	来源	链接	分类	备注
快速排序	acwing.com	快速排序	排序
堆排序	acwing.com	堆排序
数组中的第K个最大元素	leetcode	数组中的第K个最大元素	快排

快速排序

AC代码

Cpp

#include <iostream>


using namespace std;
const int N = 100010;
int q[N];
int n;

void quick_sort(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(l, j);
    quick_sort(j + 1, r);
    
}

int main(){
    scanf("%d", &n);
    
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
    
    quick_sort(0, n - 1);
    
    for(int i =  0; i < n; i ++){
        printf("%d ", q[i]);
    }
    
    return 0;
}

堆排序

分析

• 时间复杂度 O(nlog(n))

每次恢复堆的时间复杂度是logn，供n - 1此重新恢复堆操作 时间复杂度是nlogn

建立堆n / 2 次向下调整，时间复杂度(n/2)*logn

所以总时间复杂度是nlogn

AC代码

Cpp

#include <iostream>


using namespace std;
const int N = 100010;
int h[N], length;
int n, m;

// 将最小的结点换到最上结点
void down(int u){
    int t = u;
    if(u * 2 <= length && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= length && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

int main(){
    scanf("%d %d", &n, &m);
    
    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    length = n;
    
    for(int i = n / 2; i ; i --) down(i);
    
    while(m --){
        // 
        printf("%d ", h[1]);
        // 将尾部结点换到头
        h[1] = h[length];
        length --;
        down(1);
    }
    
    
    return 0;
}

冒泡排序

分析

• 时间复杂度

O(n2)

• 是否稳定

稳定

AC代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            for(int j = 1; j < nums.size(); j++){
                if(nums[j] < nums[j-1]) {
                    swap(nums[j], nums[j-1]);
                }
            }
        }
        return nums;
    }
};

选择排序

分析

• 时间复杂度

O(n2)

• 是否稳定

不稳定

AC代码

#include <iostream>


using namespace std;
const int N = 100010;
int q[N];
int n;

void select_sort(){
    for(int i = 0; i < n - 1; i ++){
        int minInt = i;
        for(int j = i; j < n; j ++){
            if(q[j] < q[minInt]) minInt = j;
        }
        if(minInt != i){
            swap(q[i], q[minInt]);
        }
    }
}

int main(){
    scanf("%d", &n);
    
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
    
    select_sort();
    
    for(int i =  0; i < n; i ++){
        printf("%d ", q[i]);
    }
    
    return 0;
}

📅 6.29

数组中的第K个最大元素

题意

在未排序的数组中找到第 k 个最大的元素，其实就是找出排序后的第k个元素

思路分析

1. 找到分界点x
2. 划分区间 左边区间个数为sl
3. 如果 k <= sl 则答案一定在左半边, 如果k > sl 则答案一定在右边

AC代码

class Solution {

    public int quick_select(int[] q, int k, int l, int r){
        if(l == r) return q[l];
        int i = l - 1;
        int j = r + 1;
        int x = q[(l + r) >> 1];
        while(i < j){
            do i ++; while(q[i] > x);
            do j --; while(q[j] < x);
            if(i < j){
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }
        int sl = j - l + 1;
        if(k <= sl){
            return quick_select(q, k, l, j);
        } else {
            return quick_select(q, k - sl, j + 1, r);
        }
    }

    public int findKthLargest(int[] nums, int k) {
        return quick_select(nums, k, 0, nums.length - 1);
    }
}