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

排序算法汇总-C++版

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

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;
}

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;
}

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;
}

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;
}

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);
}
}

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;
}

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);              // 将未完成排序的部分继续进行堆排序
}
}

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;
}

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);
}
}

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;
}

QQ_20190220165650

文章标签：
C++
搜索推荐
人工智能
BI
存储
大数据
关键词：
算法c++
C++排序
排序算法C++
大向二
目录
相关文章
aliyun1792367740-35101
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题（C/C++）
【动态规划算法】蓝桥杯填充问题（C/C++）
aliyun1792367740-35101
40 0
阿客不是客
|
29天前
|
存储 算法 C++
高精度算法（加、减、乘、除，使用c++实现）
高精度算法（加、减、乘、除，使用c++实现）
阿客不是客
332 0
高精度算法（加、减、乘、除，使用c++实现）
aliyun1792367740-35101
|
1月前
|
存储 算法 决策智能
【算法】博弈论（C/C++）
【算法】博弈论（C/C++）
aliyun1792367740-35101
35 0
aliyun1792367740-35101
|
1月前
|
存储 算法 C++
【算法】哈希映射（C/C++）
【算法】哈希映射（C/C++）
aliyun1792367740-35101
26 0
aliyun1792367740-35101
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列（C/C++）
【算法】最长公共子序列（C/C++）
aliyun1792367740-35101
99 0
aliyun1792367740-35101
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法（C/C++）
一篇带你速通差分算法（C/C++）
aliyun1792367740-35101
48 0
aliyun1792367740-35101
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法（C/C++）
一篇带你速通前缀和算法（C/C++）
aliyun1792367740-35101
28 0
aliyun1792367740-35101
|
1月前
|
存储 算法 C++
弗洛伊德(Floyd)算法（C/C++)
弗洛伊德(Floyd)算法（C/C++)
aliyun1792367740-35101
58 0
aliyun1792367740-35101
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法（C/C++)
迪杰斯特拉(Dijkstra)算法（C/C++)
aliyun1792367740-35101
51 0
aliyun1792367740-35101
|
1月前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索（C/C++）
【算法解题思想】动态规划+深度优先搜索（C/C++）
aliyun1792367740-35101
42 0

热门文章

最新文章

  • 1
    c++ static 关键字
  • 2
    [C++再学习系列] 可访问性问题
  • 3
    matlab与C++以.mat文件方式进行数据相互流动
  • 4
    读书笔记 effective c++ Item 53 关注编译器发出的警告
  • 5
    c++工程包含测试
  • 6
    纪念逝去的岁月——C/C++字符串回文
  • 7
    C++智能指针(auto_ptr)详解
  • 8
    C++第1周项目2——日期结构体
  • 9
    C++11中的tuple应用：让函数返回多个值
  • 10
    C++ 中cout&lt;&lt;endl的实现
  • 1
    基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
    63
  • 2
    强化学习系列：A3C算法解析
    203
  • 3
    AES（Advanced Encryption Standard）是一种广泛使用的对称密钥加密算法，由美国国家标准技术研究所（NIST）制定。
    96
  • 4
    计算机视觉：目标检测算法综述
    147
  • 5
    `scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
    78
  • 6
    Python排序算法大PK：归并VS快速，谁才是你的效率之选？
    33
  • 7
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    39
  • 8
    深入剖析操作系统调度算法
    52
  • 9
    基于ACO蚁群优化算法的WSN网络路由优化matlab仿真
    57
  • 10
    分布式自增ID算法---雪花算法（SnowFlake）Java实现
    268

    • 相关课程

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

    • 相关电子书

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

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    DataWorks售前咨询