C++数据结构算法(二)排序算法集合(二)

简介: C++数据结构算法(二)排序算法集合(二)

插入排序:

详细算法描述


整理插入排序算法描述如下:

枚举序列中第2~n个元素。

当枚举元素i时,前i-1个元素已经有序。将第i个元素插入到前i-1个元素的有序序列中,形成长度为i的有序序列。

枚举过程结束后,整个序列有序。

所以,我们总结一下插入操作的算法描述:


假设序列1~(i-1)已经有序, 从i到1枚举分界线的下标j;


如果分界线前面的元素a[j-1]大于x,说明a[j-1]应该在分界线后面。所以将a[j-1]移动到a[j],分界线前移变成j-1。


如果分界线前面没有元素(j=1),就将x放在数组第1位。否则如果碰到一个j-1号元素小于等于x,说明分界线位置正确,就将x插到j位。


完整代码:

#include <bits/stdc++.h>
#define N 1550
using namespace std;
int a[N], n;
int main() {
    // 输入
    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    // 插入排序
    for (int i = 2; i <= n; ++i) {    // 按照第2个到第n个的顺序依次插入
        int j, x = a[i];    // 先将i号元素用临时变量保存防止被修改。
        // 插入过程,目的是空出分界线位置j,使得所有<j的部分<=x,所有>j的部分>x。
        // 循环维持条件,j>1,并且j前面的元素>x。
        for (j = i; j > 1 && a[j - 1] > x; --j) {   
            // 满足循环条件,相当于分界线应向前移,
            // 分界线向前移,就等于将分界线前面>x的元素向后移
            a[j] = a[j - 1];              
        }
        // 找到分界线位置,插入待插入元素x
        a[j] = x;                         
    }
    // 输出
    for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
    cout << endl;
    return 0;
}


快速排序:

image.png


快速排序的基本思想:

image.png

当需要将1到n的n个数排序时,我们通过分解,将该问题分解为两个将n/2个数排序的子问题;


在每个子问题中,我们继续分解,直到最后子问题长度为1;


此时,整个序列就完成排序了。


所以该算法的总复杂度变成了n^2/4 + 2nn2/4+2n。可以发现,在该算法中,多分解了一层,而复杂度也进一步减少了。


由此我们可以产生一个感觉,分解得越复杂度越小。所以,我们完全可以进一步分解,直到最后每个单位排序的长度为1。


image.png


任意长度为n的序列排序


当然快速排序也可用来给任意n个数的序列排序。但是与和1~n排序不同的是,对于任意n个数的序列,我们在划分子段的时候并不能很容易找到整个序列的“中位数”。所以只能在序列中任意取一个数。比如


取整个序列中最左边的数。

取整个序列中最右边的数。

在整个序列中随机一个位置并取该位置上的数。

都是常见的取数策略。


但由于不能保证每次取的数字都刚好是中位数,所以每次划分时也不能保证左边子段长度和右边子段长度非常平均。如果“不幸”选到不合适的数(比如整个子段中最小的数或最大的数),整个算法的效率会降低很多。


在此,我们详细描述一下给任意n个数排序的快速排序算法:


假设我们要对数组a[1..n]排序。初始化区间[1..n]。


令l和r分别为当前区间的左右端点。下面假设我们对l到r子段内的数字进行划分。取pivot = a[l]为分界线,将<pivot的数字移到左边,>pivot的数字移到右边,然后将pivot放在中间。假设pivot的位置是k。


如果左边区间[l..k-1]长度大于1,则对于新的区间[l..k-1],重复调用上面的过程。


如果右边区间[k+1..r]长度大于1,则设置新的区间[k+1, r],重复调用上面的过程。


当整个过程结束以后,整个序列排序完毕。


递归函数实现快速排序:

// 该代码参考 https://www.geeksforgeeks.org/quick-sort/
#include <bits/stdc++.h>
#define N 100010 
using namespace std; 
int n; 
int a[N]; 
void quick_sort(int l, int r) {  
    // l和r分别代表当前排序子段在原序列中左右端点的位置
    // 设置最右边的数为分界线
    int pivot = a[r];
    int k;
    /* 此处省略了元素移动和确定分界线新位置k的过程 */
    if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1,排序
    if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1,排序
    // 上面的过程结束后,到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动操作
    // 保证了左子段中的元素都小于等于分界线,右子段中的元素都大于分界线。所以整个序列也是有序的。
} 
int main() { 
    // 输入
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); 
    // 快速排序
    quick_sort(1, n); 
    // 输出
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);  
    return 0; 
}


快速排序完整代码:

// 该代码参考 https://www.geeksforgeeks.org/quick-sort/
#include <bits/stdc++.h>
#define N 100010 
using namespace std; 
int n; 
int a[N]; 
void quick_sort(int l, int r) { 
    // 设置最右边的数为分界线
    int pivot = a[r];
    // 元素移动
    int k = l - 1;
    for (int j = l; j < r; ++j)
        if (a[j] < pivot) swap(a[j], a[++k]); 
    swap(a[r], a[++k]); 
    if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1,排序
    if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1,排序
    // 上面的过程结束后,到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动操作
    // 保证了左子段中的元素都小于等于分界线,右子段中的元素都大于分界线。所以整个序列也是有序的。
} 
int main() { 
    // 输入
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); 
    // 快速排序
    quick_sort(1, n); 
    // 输出
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);  
    return 0; 
}

复杂度分析


空间复杂度


首先该算法的空间复杂度是O(n)O(n),具体来说,在整个排序过程中,元素的移动都在原始数组中进行。所以快速排序是一种原地排序算法。


时间复杂度


可以看出,在「详细算法描述」中,我们的算法分为若干层。每一层中都是分治法的三个步骤:我们首先进行问题拆分,然后进入下一层,下一层的问题解决后,我们返回这一层进行子问题解的合并。


image.png


我们首先分析对1~n的n个数字进行快速排序的情况。


在每一层中,问题拆分的复杂度是O(n)O(n),因为我们移动数组元素的时候,需要将每个子段扫一遍。那么把所有层的子段一起看,就相当于在每一层都把整个序列完整扫了一遍。对于子段解的合并,其复杂度是O(1)O(1),因为有分界线的存在,当我们把左边和右边都排好序后,它们和分界线元素一起天然形成了原序列的完整排序。


那么一共有多少层呢?因为每次我们都知道当前子段的中位数,所以可以保证每次划分,两个字段长度比较平衡,所以下一层子段的长度都比上一层减少了一半,直到长度为1算法停止。所以整个算法有\log nlogn层。


那么我们分析出在这种情况下,算法的复杂度是O(n\log n)O(nlogn)。这样,在1秒之内,计算机能非常轻松地排序10^6106及以上的数据。


但对于任意n个数的排序,每次划分情况取决于选取的分界线情况。如果每次分界线刚好取到最小值或者最大值,会导致划分时所有数字都会移动到同一边,整个算法的复杂度也会下降为O(n^2)O(n2)。如下图:



我们很容易想到两种尽量避免出现这种情况的方法:


在排序之前,先把整个数组随机打乱顺序。

在选取分界线时,与之前固定选取某个位置的方法相比,我们换成随机选择分界线的位置。

这两种方法都能极大概率避免上面提到的极端情况的发生。


分治思想:


快速排序用到的一个很重要的思想就是分治思想,也是分治法运用在排序中的很重要的实例。


分治思想是一种“分而治之”的思想,反应在解决问题当中,就是将一个复杂问题不断分解为规模更小、更容易解决的问题,从而提升解决问题的效率。而分治法就是基于分治思想得到的解决问题的方法,它分为下面三个步骤:


问题的拆分。例如在快速排序中,我们以某个元素为分界线,将待排序的数字分为两部分。

解决子问题。例如在快速排序中,如果子问题的规模为1,我们就直接解决它,否则,我们就使用和划分主问题同样的办法继续划分子问题直到子问题规模达到很容易直接解决为止。

合并子问题的解。例如在快速排序中,我们将左边右边分别排序后,将前后排好序的部分与中间的分界线连接,形成主问题的解。

分治思想在算法领域有非常广泛的应用,在很多分解和合并都非常容易的问题上,分治法都能够提升其算法效率。


总结


快速排序是一种基于分治法的排序。其基本思想在于固定一个分界线,将整个序列按照小于分界线和大于分界线划分,然后再分别对划分好的子段进行排序。


快速排序的时间复杂度在理想情况下是O(n \log n)O(nlogn),但如果选取分界线每次都是子段中的最大值或最小值的话,时间复杂度可能会退化到O(n^2)O(n2)。在内存使用上,因为整个移动过程都在原数组中进行的,所以属于原地排序。


sort函数是C++标准模板库(STL)中一种对快速排序的优化实现,可以通过传入头指针、尾指针和比较函数来对数组中的对象进行排序。


快速排序示例:


将数组{2, 3, 1, 5, 4}从小到大排列。


不使用sort函数


将「整体框架」和「移动元素」进行合并,我们得到快速排序完整代码:

// 该代码参考 https://www.geeksforgeeks.org/quick-sort/
#include <bits/stdc++.h>
#define N 100010 
using namespace std; 
int n; 
int a[N]; 
void quick_sort(int l, int r) { 
    // 设置最右边的数为分界线
    int pivot = a[r];
    // 元素移动
    int k = l - 1;
    for (int j = l; j < r; ++j)
        if (a[j] < pivot) swap(a[j], a[++k]); 
    swap(a[r], a[++k]); 
    if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1,排序
    if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1,排序
    // 上面的过程结束后,到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动操作
    // 保证了左子段中的元素都小于等于分界线,右子段中的元素都大于分界线。所以整个序列也是有序的。
} 
int main() { 
    // 输入
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); 
    // 快速排序
    quick_sort(1, n); 
    // 输出
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);  
    return 0; 
}


使用sort函数


sort函数有三个参数,分别为头指针、尾指针和比较函数,其中如果排序对象定义了小于号的话,比较函数可省略。例如对于一个长为n的数组排序:

#include <bits/stdc++.h>
using namespace std;
int a[10] = {2, 3, 1, 5, 4};
int n = 5;
int main() {
    sort(a, a + n);  //sort函数的两个参数,头指针和尾指针
    for (int i = 0; i < n; ++i) cout << a[i] << ' ';
    cout << endl;
}

例题:


image.png



相关文章
|
4月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
101 2
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
65 1
|
2月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
126 0
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
69 0
|
3月前
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表(ACL)实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表(ACL)的应用,分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型,展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用,并提出性能优化及结合机器学习等未来研究方向。
95 4
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
138 17
|
3月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
82 0
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
217 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
47 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。

热门文章

最新文章