《算法导论》读书笔记 PART 2

发布于 2020-02-25  133 次阅读


由于文章长度过长导致数据库崩溃,现在将笔记分段

第二部分:排序和顺序统计量

第6章:堆排序

6.1 堆

堆是树形数据结构的一种,可以用数组模拟实现,并且能再logn的时间内找出所有元素中的最大值(最小也行),可以将其视为一棵完全二叉树。

对于单个父节点K,其左子节点的下标为K*2(如果存在的话),右子节点为K*2+1。

与此同时,可以用位运算来优化计算节点坐标的过程

同样的,查找父节点也可以写成这样

6.4堆排序算法 传送门

堆排序算法的思想就在于,不断地取出堆顶的元素,也就是堆中元素的最大值,然后依次将取出的元素排列,便可以实现排序操作。

时间复杂度(nlogn)

空间复杂度(n)

int heap[110000];
int heap_size;
int n;
void max_heapify(int i)
{
    int largest = i;
    if (i * 2 <= heap_size && heap[i * 2] > heap[i])
    {
        largest = i * 2;
    }
    if (i * 2 + 1 <= heap_size && heap[i * 2 + 1] > heap[largest])
    {
        largest = i * 2 + 1;
    }
    if (largest != i)
    {
        swap(heap[i], heap[largest]);
        max_heapify(largest);
    }
}
void build_max_heap()
{
    heap_size = n;
    for (int i = heap_size / 2; i >= 1; i--)
    {
        max_heapify(i);
    }
}
void heap_sort()
{
    build_max_heap();
    for (int i = n; i > 1; i--)
    {
        swap(heap[1], heap[i]);
        heap_size--;
        max_heapify(1);
    }
}

测试题目 :luogu 【模板】快速排序

此图像的alt属性为空;文件名为TY81C8P7TC9@VOE4-1024x507.png

第7章:快速排序

7.1快速排序的描述

快速排序和归并排序一样,也使用了分治思想。由于在分解子问题时,快速排序采取了取中间值,将比中间值小和比中间值大的数划分成两个数组,从而递归求解,由于合并时,两个数组已经排好序,所以并不需要归并操作,也自然不需要多出来的O(n)数组来临时处理这个变量,是实际情况下排序的最好选择。

时间复杂度 O(n^2)最坏 ,O(nlogn)平均(常数比前面提到的几种排序小)

空间复杂度O(nlogn)无需额外线性空间

vector<int> date;
int partition(int left, int right)
{
    int x = date[right];
    int i = left - 1;
    for (int j = left; j <= right - 1; j++)
    {
        if (date[j] <= x)
        {
            i++;
            swap(date[i], date[j]);
        }
    }
    swap(date[i + 1], date[right]);
    return i + 1;
}
void quicksort(int left, int right)
{
    if (left < right)
    {
        int mid = partition(left, right);
        quicksort(left, mid - 1);
        quicksort(mid + 1, right);
    }
}

测试题目 :luogu 【模板】快速排序

此图像的alt属性为空;文件名为LAHP52TH6ZF6V3S-1024x460.png

因为题目特地设计数据卡了普通写法快速排序,所以导致大范围超时,但这可以通过随机化来弥补,同时这也体现出了普通快排不够稳定。

7.3随机化的快速排序

随机化的核心就在划分之前,对要划分的中位数M进行随机化,加上下面这段代码

int random_partition(int left, int right)
{
    int i = rand() % (right - left) + left;
    swap(date[i], date[right]);
    return partition(left, right);
}

从而达到对某些设计好的数据进行规避(实际效果看脸)

时间复杂度和空间复杂度同普通快速排序

测试题目 :luogu 【模板】快速排序

此图像的alt属性为空;文件名为1OQE@5A_MS3YURT_QCZAS-1024x461.png
此图像的alt属性为空;文件名为FFIB2JOK9333VI@6YW-1024x441.png

一共测试了两次,看来还是有两个点的数据过大(最后一个点是100000个0)。

试试STL的sort?

此图像的alt属性为空;文件名为@R5WED@84U4HWJ1T37RO-1024x508.png
这逆天的效率。

第8章:线性时间排序

8.2:计数排序

计数排序的原理是利用数组下标来排序,先用下标来统计每个数的出现次数,再用递推维护计数数组的前缀和,此时计数数组里面的每个元素的值,就代表了其下标在排序后数组里面的位置。之后只要一个个把原来数组的元素带入计数数组,便可以实现排序操作。

时间复杂度:O(n+k)) (k为数组中最大元素和最小元素和最小元素的差)

空间复杂度: O(n+k) (k为数组中最大元素和最小元素和最小元素的差)

vector<int> date;
vector<int> out;
vector<int> C;
void count_sort()
{
    for (int i = 0; i < C.size(); i++)
    {
        C[i] = 0;
    }
    for (int i = 0; i < date.size(); i++)
    {
        C[date[i]]++;
    }
    for (int i = 1; i < C.size(); i++)
    {
        C[i] += C[i - 1];
    }
    out.resize(date.size() + 1);
    for (int i = date.size() - 1; i >= 0; i--)
    {
        out[C[date[i]]] = date[i];
        C[date[i]]--;
    }
    return;
}

测试题目 :luogu 【模板】快速排序

此图像的alt属性为空;文件名为Q6_EAGCE9EZO22N2W3-1024x451.png

虽然计数排序有着其他nlogn时间排序所没有的速度(k比较小时),其在k很大时是不可取的。

8.3基数排序

以前一直以为,桶排序就是拿下标扫一下,今天见识到了。。。。。。。

其思想就是不断地按照各位数进行下标排序,排序后保留原来的顺序,从而实现对加入每个“桶”来说,其中的所有元素的前k位数字(k位当前处理到的位数)都是有序的,不断地处理每个位置,就可以实现,对数组中的树进行排序

此图像的alt属性为空;文件名为440px-基数排序.gif
图片来自维基百科

时间复杂度:O(n*r)(r为最大数的位数)

空间复杂度O (n)

vector<int> date;
int get_max()
{
    int ma = date[0];
    for (int i = 1; i < date.size(); i++)
    {
        ma = max(date[i], ma);
    }
    int t = 1;
    while (ma > 0)
    {
        t++;
        ma /= 10;
    }
    return t;
}
void radix_sort()
{
    int d = get_max();
    // cout << d << endl;
    vector<int> tmp[10];
    int chu = 1;
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < date.size(); j++)
        {
            tmp[date[j] / chu % 10].push_back(date[j]);
        }
        date.clear();
        for (int j = 0; j < 10; j++)
        {
            for (int k = 0; k < tmp[j].size(); k++)
            {
                date.push_back(tmp[j][k]);
            }
        }
        for (int j = 0; j < 10; j++)
        {
            tmp[j].clear();
        }
        chu *= 10;
    }
    return;
}

测试题目 :luogu 【模板】快速排序

此图像的alt属性为空;文件名为MPHPNHJPNKVHML_EWW-1024x443.png

8.4桶排序

桶排序的具体思想就是先把问题进行划分,比如说把区间[0,20]的数划分为[0,10][11,20]然后再对每个区间进行排序或者递归处理,个人认为这只是一种对其他排序算法的预处理,可以在具体问题起到一定的效果(一种优化?)。

第9章:中位数与顺序统计量

9.1最大值最小值

如何查找一个数组中的最大最小值?

只需要(也只能)遍历数组里的每一个元素才能得出结果。

9.2期望为线性的选择排序算法

如何查找一个无序数组里面的某个特定值?

先拍序再二分会消耗掉nlogn复杂度的时间(显然没必要)

直接遍历又会被设计好的数据好,这时可以采用随机化+二分,先随机取值,再将取的值两边的区间递归求解,不过时间复杂度也是O(n)

第三部分:传说门


💭💭💭💭💭💭