codetop排序篇

力扣912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

快速排序和归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // qsort(nums, 0, nums.size()- 1);
        // merge_sort(nums, 0, nums.size()- 1);
        return nums;
    }

    void qsort(vector<int>& q, int l, int r)
    {
        if (l >= r) return ;

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

    void merge_sort(vector<int>& q, int l, int r)
    {
        if (l >= r) return;

        int mid = (l + r) / 2;

        merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

        vector<int> tmp(r - l + 1);
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
            else tmp[k ++ ] = q[j ++ ];
        while(i <= mid) tmp[k ++ ] = q[i ++ ];
        while (j <= r) tmp[k ++ ] = q[j ++ ];
       // 每次递归，tmp都是从0开始的
        for (int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
    }
};

堆排序(大根堆和小根堆)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void heap(vector<int>& nums)
{
    // 为了方便使用 1-based 索引，在前面插入一个无用的数
    nums.insert(nums.begin(), -1);
    int n = nums.size() - 1;

    // 建堆（小根堆）
    for (int i = n / 2; i; i--) down(nums, i, n);
    for (int i = n; i > 1; i--)
    {
        swap(nums[1], nums[i]);
        down(nums, 1, i - 1);
    }
    // 去掉哨兵元素（还原为 0-based 数组）
    nums.erase(nums.begin());
    reverse(nums.begin(), nums.end());
}


void down(vector<int>& nums, int u, int size)
{
    int t = u;
    if (u * 2 <= size && nums[u * 2] < nums[t]) 
        t = u * 2;
    if (u * 2 + 1 <= size  && nums[u * 2 + 1] < nums[t]) 
        t = u * 2 + 1;
    if (u != t)
    {
        swap(nums[t], nums[u]);
        down(nums,t,size);
    }
}

🧠需要注意一点就是，算法模板是从小到大输出最小的数，但整个的堆并不是有序的，所以需要加上下面的这段代码

1
2
3
4
5
for (int i = n; i > 1; i--)
{
    swap(nums[1], nums[i]);
    down(nums, 1, i - 1);
}

✅最好的方法还是使用大根堆来实现升序排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void heap(vector<int>& nums)
{
    nums.insert(nums.begin(), -1);   // 下标从1开始
    int n = nums.size() - 1;
    
    // 建立大根堆
    for (int i = n / 2; i; i -- ) down(nums, i, n);
    
    for (int i = n; i > 1; i -- )
    {
        swap(nums[1], nums[i]);
        up(nums, 1, i - 1);
	}
    num.erase(nums.begin());
}

void down(vector<int>& nums, int u, int size)
{
    int t = u;
    if (u * 2 <= size && nums[u * 2] > nums[t]) t = u * 2;    
    if (u * 2 + 1 <= size && nums[u * 2 + 1] > nums[t]) t = u * 2 + 1;
    
    if (u != t)
    {
        swap(nums[u], nums[t]);
        down(nums, t, size);
    }
}

这里忒一些容器的知识

1
2
3
4
5
std::vector<数据类型> 变量名;
std::vector<int> s;
std::vector<int> s{1,2,3};
std::vector<int> s(5);  // 设置了5个大小的容器
std::vector<int> s(5,100);  // 这个容器拥有五个元素，每个元素的初始值为100

容器的几个新用法：

1
2
3
4
5
6
7
8
std::vector<int> s;
s.push_back(值);  //将值添加到容器末尾
s.pop_back();  //将末尾的值删除掉
s.insert(s.begin()+2, 2); // 在指定位置插入元素
s.assign(10,100); //将s重新初始化为拥有10个元素  每个元素位100的容器
s.erase(s.begin() + 2);   // 删除指定位置的元素
s.clear(); // 将容器清空
s.empty(); //看看是不是空的

容器比数组更灵活，排序的时候可以当做数组来操作！！！