AI 助理
备案控制台登录注册
开发者社区 大数据 文章 正文

排序算法汇总-C++版

2019-02-20 1543
版权
举报
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 直接插入排序 适用于少量数据的排序，直接插入排序是稳定的排序算法。基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。平均时间复杂度：O(n^2)空间复杂度：O(1)稳定性：稳定 #include ...

直接插入排序

适用于少量数据的排序，直接插入排序是稳定的排序算法。
基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20

//直接插入排序：将第一个数据看做一个顺序表，将后面的数据一次插入表中
void InsertSort(int a[], int n)  
{  
for(int i= 1; i<n; i++){  
     int j= i-1;   //表中最后一个数据
    int x = a[i];        //复制为哨兵，即存储待排序元素  
    while(j>=0 && x < a[j]){  //查找在有序表的插入位置  (遍历表)
        a[j+1] = a[j];  
        j--;         //元素后移  
    }  
    a[j+1] = x;      //插入到正确位置  
}  
  
} 

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
InsertSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

二分插入

基本思想是：直接插入排序是挨个的去比较，而二分插入排序则是利用二分搜索的原理，将待排序的元素与左侧已经排好序的队列的中间元素(n/2)进行比较
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20

//折半插入
void BInsertSort(int a[], int n)  
{  
for(int i= 1; i<n; i++){ 
    if(a[i] > a[i-1]){  //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
        continue;
    }
    int low=0,high=i;
    int x = a[i];        //复制为哨兵，即存储待排序元素  
    while(low<=high){  //查找在有序表的插入位置  (遍历表)
        int m=(low+high)/2;
        if(x<a[m]) {
            high=m-1;
        } else {
            low=m+1;
        }
    }  
    for(int j=i-1;j>=high+1;j--){
        a[j+1]=a[j];
    }
    a[high+1] = x;      //插入到正确位置  
}      
} 

int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}
cout<<"\n";
BInsertSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

希尔排序

基本思想是：希尔排序是在插入排序的基础上进行发展的，通过一个希尔增量先排序一定间隔的数据。待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
平均时间复杂度：O(N^3/2)
空间复杂度：O(1)
稳定性：不稳定

#include <iostream>
using namespace std;
#define LENGTH 20
void shellsort(int a[],int n) {  
for (int increment = n / 2; increment > 0; increment /= 2)
{
    for (int i = increment; i < n; i++)
    {
        int insert_num = a[i], j;
        for (j = i - increment; j >= 0; j -= increment)
        {
            if (a[j] > insert_num)
                a[j + increment] = a[j];
            else
                break;
        }
        a[j + increment] = insert_num;
    }
} 
}  
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}
cout<<"\n";
shellsort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

简单选择排序

基本思想是：要排序的一组数中，选出最小（最大）的一个数与第1个（最后）位置的数交换；然后在剩下的数当中再找最小（最大）的与第2个（倒数第二）位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20
void SelectSort(int r[],int n) {  
int i ,j , min ,max, tmp;  
for (i=1 ;i <= n/2;i++) {    
    // 做不超过n/2趟选择排序   
    min = i; max = i ; //分别记录最大和最小关键字记录位置  
    for (j= i+1; j<= n-i; j++) {  
        if (r[j] > r[max]) {   
            max = j ; continue ;   
        }    
        if (r[j]< r[min]) {   
            min = j ;   
        }     
  }    
  //该交换操作还可分情况讨论以提高效率  
  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   

}   
}  
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
SelectSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

冒泡排序

基本思想是：依次比较相邻的数据，将小数据放在前，大数据放在后
平均时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20
//设置一个标记来标志一趟比较是否发生交换
//如果没有发生交换，则数组已经有序
void bubbleSort(int a[],int n)
{
bool flag;
for (int i = 0; i < n; i++)
{
    flag = false;
    for (int j = 0; j < n - 1 - i; j++)
    {
        if (a[j] > a[j+1])
        {
            swap(a[j], a[j+1]);
            flag = true;
        }
    }
    if (!flag)
        break;
}
}
int main()
{
int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
bubbleSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

快速排序

基本思想是：选择一个基准元素，把待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
时间复杂度：平均O(n*lgn);最坏O(n^2)
空间复杂度：最好O(lgn)，最坏O(n)，平均O(lgn)
稳定性：不稳定。

#include <iostream>
using namespace std;
#define LENGTH 20
void QuickSort(int a[], int low, int high)
{
if (low < high)
{
    int x = a[high];//将输入数组的最后一个数作为主元，用它来对数组进行划分
    int i = low - 1;//i是最后一个小于主元的数的下标
        for (int j = low; j < high; j++)//遍历下标由low到high-1的数
    {
        if (a[j] < x)//如果数小于主元的话就将i向前挪动一个位置，并且交换j和i所分别指向的数
        {
            int temp;
            i++;
             temp = a[i];
          a[i] = a[j];
          a[j] = temp;
         }
       }
       //经历上面的循环之后下标为从low到i（包括i）的数就均为小于x的数了，现在将主元和i+1位置上面的数进行交换
       a[high] = a[i + 1];
    a[i + 1] = x;

    int q = i + 1;
    QuickSort(a, low, q - 1);
    QuickSort(a, q + 1, high);
}
}


        

          
        

        
        

          

          AI 代码解读
        

      
      
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}

cout<<"\n";
QuickSort(b,0,LENGTH-1);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定。

#include <iostream>
using namespace std;
#define LENGTH 20
// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(int arr[], int len, int index)
{
int left = 2*index + 1; // index的左子节点
int right = 2*index + 2;// index的右子节点

int maxIdx = index;
if(left<len && arr[left] > arr[maxIdx])     maxIdx = left;
if(right<len && arr[right] > arr[maxIdx])     maxIdx = right;

if(maxIdx != index)
{
    swap(arr[maxIdx], arr[index]);
    adjust(arr, len, maxIdx);
}

}

// 堆排序
void heapSort(int arr[], int size)
{
// 构建大根堆（从最后一个非叶子节点向上）
for(int i=size/2 - 1; i >= 0; i--)
{
    adjust(arr, size, i);
}
 for(int i=0;i<size;i++){
     cout<<arr[i]<<" ";    
}
cout<<"\n";
// 调整大根堆
for(int i = size - 1; i >= 1; i--)
{
    swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
    adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
}
}


        

          
        

        
        

          

          AI 代码解读
        

      
      
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
    
}

cout<<"\n";
heapSort(b,LENGTH);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

归并排序

基本思想是：将待排序序列递归分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
时间复杂度：最差O(nlogn)
时间复杂度：平均O(nlogn)
空间复杂度：O(n)
稳定性：稳定

#include <iostream>
using namespace std;
#define LENGTH 20
/*该函数将数组下标范围[l,m]和[m+1,r]的有序序列合并成一个有序序列*/
void Merge(int *a,int l, int m, int r)
{
int begin1 = l;       
int begin2 = m + 1;  
int j=l; 
int k=0; 
int len = r-l+1;
int *b = new int[len];

while(begin1<=m && begin2<=r)  
{  
    if(a[begin1]<=a[begin2])  
        b[k++] = a[begin1++];  
    else  
        b[k++] = a[begin2++];  
}  
while(begin1<=m)  {
    b[k++] = a[begin1++];  
}
   
while(begin2<=r)  {
    b[k++] = a[begin2++]; 
}
    
   for(int i=0;i<len;i++)  
{  
    a[j++] = b[i];  
} 
delete []b;
}

 /*二路归并排序（递归实现）*/
void MergeSort(int *a, int l, int r)
{
if(l<r)
{
    int m = (l+r)/2;
    MergeSort(a,l,m);
    MergeSort(a,m+1,r);
    Merge(a,l,m,r);
}
}


        

          
        

        
        

          

          AI 代码解读
        

      
      
int main()
{

int b[LENGTH];
for(int i=0;i<LENGTH;i++){
    printf("%d ",b[i]);
}
cout<<"\n";
MergeSort(b,0,LENGTH-1);
for(int i=0;i<LENGTH;i++)
    cout<<b[i]<<" ";

return 0;
}

        

          
        

        
        

          

          AI 代码解读

QQ_20190220165650

文章标签：
C++
搜索推荐
人工智能
BI
存储
大数据
关键词：
C++排序
算法c++
排序算法C++
大向二
+关注
24文章
目录
打赏
0
0
0
0
6
分享
相关文章
陌陌谣
|
1月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中，迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点，确保高效稳定的网络环境。该算法通过计算最短路径，提升数据传输速率与稳定性，实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用，为企业信息化建设提供有力支持。
陌陌谣
72 15
游客akle7anmklvj6
|
1月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中，公司局域网管理至关重要。哈希表作为一种高效的数据结构，通过哈希函数将关键值（如IP地址、账号）映射到数组索引，实现快速的插入、删除与查找操作。例如，在员工登录验证和设备信息管理中，哈希表能显著提升效率，避免传统线性查找的低效问题。本文以C++为例，展示了哈希表在局域网管理中的具体应用，包括设备MAC地址与IP分配的存储与查询，并探讨了优化哈希函数和扩容策略，确保网络管理高效准确。
游客akle7anmklvj6
39 1
陌陌谣
|
16天前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中，局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而，出于网络安全管理、资源合理分配以及合规性要求等多方面的考量，对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控，涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法，深入探讨其在局域网计算机监控场景中的应用，并通过详尽的代码示例进行阐释。
陌陌谣
37 4
陌陌谣
|
2月前
|
存储 监控 算法
公司监控上网软件架构：基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代，公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录，具备高效插入、删除操作及节省内存的优势，助力企业实时追踪员工上网行为，提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为，并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式，但实际开发还需考虑安全性、隐私保护等多方面因素。
陌陌谣
40 0
公司监控上网软件架构：基于 C++ 链表算法的数据关联机制探讨
RossyYan
|
3月前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序（头歌实践教学平台习题）【合集】
本关任务是实现二路归并算法，即将两个有序数组合并为一个有序数组。主要内容包括： - **任务描述**：实现二路归并算法。 - **相关知识**： - 二路归并算法的基本概念。 - 算法步骤：通过比较两个有序数组的元素，依次将较小的元素放入新数组中。 - 代码示例（以 C++ 为例）。 - 时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。 - **测试说明**：平台会对你编写的代码进行测试，提供输入和输出示例。 - **通关代码**：提供了完整的 C++ 实现代码。 - **测试结果**：展示代码运行后的排序结果。 开始你的任务吧，祝你成功！
RossyYan
101 10
RossyYan
|
3月前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括： - **任务描述**：实现希尔排序算法。 - **相关知识**： - 排序算法基础概念，如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列（增量序列）的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧，如循环嵌套和索引计算。 - **测试说明**：提供了测试输入和输出示例，帮助验证代码正确性。 - **我的通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了代码运行的测试结果。 通过这些内容，读者可以全面了解希尔排序的原理和实现方法。
RossyYan
93 10
RossyYan
|
3月前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序（头歌实践教学平台习题）【合集】
快速排序是一种高效的排序算法，基于分治策略。它的主要思想是通过选择一个基准元素（pivot），将数组划分成两部分。一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序，最终使整个数组有序。(第一行是元素个数，第二行是待排序的原始关键字数据。本关任务：实现快速排序算法。开始你的任务吧，祝你成功！
RossyYan
77 7
RossyYan
|
3月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类（头歌实践教学平台习题）【合集】
1. **相关排序和查找算法的原理**：介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**：讲解如何定义`Array`类，包括类的声明和实现，以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**：探讨内存管理和正确访问数组元素的方法，确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**：解释排序和查找函数的参数传递方式及返回值处理，确保函数功能正确实现。 通过掌握这些知识，可以顺利地将排序和查找算法封装到`Array`类中，并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
RossyYan
75 5
RossyYan
|
3月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
130 2
游客akle7anmklvj6
|
4月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中，局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法，用于管理用户的上网行为，如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性，确保了高效的查找、插入和删除操作。文中提供了C++代码示例，展示了如何实现该算法，并强调其在网络管理中的应用价值。
游客akle7anmklvj6
64 7

热门文章

最新文章

  • 1
    算法为舟 思想为楫：AI时代，创作何为？
    7
  • 2
    阿里云 AI 搜索开放平台：从算法到业务——AI 搜索驱动企业智能化升级
    26
  • 3
    基于GA遗传优化TCN-GRU时间卷积神经网络时间序列预测算法matlab仿真
    15
  • 4
    基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
    5
  • 5
    AI训练师入行指南（三）：机器学习算法和模型架构选择
    13
  • 6
    Video-T1：视频生成实时手术刀！清华腾讯「帧树算法」终结闪烁抖动
    4
  • 7
    基于AES的遥感图像加密算法matlab仿真
    11
  • 8
    基于免疫算法的最优物流仓储点选址方案MATLAB仿真
    7
  • 9
    基于GA遗传优化TCN时间卷积神经网络时间序列预测算法matlab仿真
    6
  • 10
    基于遗传优化算法的多AGV栅格地图路径规划matlab仿真
    18
  • 1
    C++为什么有参数依赖查找（ADL）？
    117
  • 2
    c++开发redis module问题之避免多个C++模块之间因重载operator new而产生的冲突，如何解决
    79
  • 3
    c++开发redis module问题之如果Redis加载了多个C++编写的模块，并且它们都重载了operator new，会有什么影响
    62
  • 4
    c++开发redis module问题之为什么在使用RedisModule_GetApi之前要通过((void**)ctx)[0]这种方式获取其地址
    95
  • 5
    Rust与C++的区别及使用问题之对于大量使用C++实现的产品来说，迁移到Rust的问题如何解决
    99
  • 6
    Rust与C++的区别及使用问题之Rust项目中组织目录结构的问题如何解决
    113
  • 7
    开发与运维C++问题之C++部分原有的数据发送能力如何解决
    57
  • 8
    开发与运维C++问题之在iLogtail新架构中在C++主程序中新增插件的概念如何解决
    88
  • 9
    开发与运维编译问题之在C++中在使用std::mutex后能自动释放锁如何解决
    130
  • 10
    开发与运维编译问题之在C++中创建一个简单的自旋锁如何解决
    56

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • C++ 入门教程开发文档
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    oss创建bucket
    目录
    AI助理

    你好，我是AI助理

    可以解答问题、推荐解决方案等