专栏首页Python编程 pyqt matplotlibC++ 插入排序,冒泡排序和选择排序

C++ 插入排序,冒泡排序和选择排序

大学的时候学过C,现在已经忘得七七八八了,现在想再学一下C/C++。

刚试着重写/温习了3个最简单的排序算法。

插入排序:依次将右边未排序的元素插入到左边已排序序列的合适位置。

时间复杂度:O(n^2)

float* sort_insertion(float a[], int len_a)
{
    /*插入排序 类似我们排序扑克牌*/
    for(int i=1; i < len_a; i++)
    {
        float to_insert = a[i];
        // 索引0到 i-1 已排好序
        int j;
        for(j = i-1; a[j] > to_insert and j >=0 ; j--)
            a[j+1] = a[j];//大的往后退一位
        a[j+1] = to_insert;//a[j] > to_insert 不成立时 j+1的值即是待插入的位置
    }
    return a;
}

冒泡排序和选择排序大学都学过,不再赘述。

冒泡排序:

时间复杂度:O(n^2)

float* sort_bubble(float a[], int len_a)
{
    /*冒泡排序 依次比较相邻的两个元素,如果顺序错误就将它们的位置交换 */
    float temp;
    for(int i=0; i < len_a-1; i++)
    {
        for(int j =0 ;j<len_a-1-i; j++)
            {
                if (a[j] > a[j+1])
                {
                    temp = a[j];
                    a[j] = a [j+1];
                    a[j+1] = temp;
                }
            }
    }
    return a;
}

选择排序:

时间复杂度:O(n^2)

float* sort_selection(float a[], int len_a)
{
    /*选择排序 依次将左边未排序序列中的最大元素,存放到右边已排序序列的左端 */
    int j;
    float temp;
    for(int i= len_a-1; i >= 0; i--)
    {
        //未排序序列:a[0]到a[i]
        //找到未排序序列的最大元素的位置
        int maxIndex = 0;
        for(j=1; j <= i; j++)
        {
            if (a[j] > a[maxIndex])
                maxIndex = j;
        }
        //交换
        temp = a[i];
        a[i] = a[maxIndex];
        a[maxIndex] = temp;
    }
    return a;
}

随机数组生成部分的代码如下:

#include <iostream>
#include <time.h>
using namespace std;
float* sort_insertion(float a[], int len_a);
float* sort_bubble(float a[], int len_a);
float* sort_selection(float a[], int len_a);

int main()
{
    const int len_b =100;
    float b[len_b];
    //int len_b = sizeof(b)/sizeof(b[0]);//求数组长度
    srand(time(NULL)); //srand()设置随机种子seed, seed 随时间变化
    for (int i=0; i<len_b; i++)
    {
        b[i] = rand()%101 -50.0f;//随机数 -50 到 50
        //cout <<b[i]<<endl;
    }
    sort_bubble(b,len_b);
    //cout<<endl;
    for (int i=0;i<len_b;i++)
        cout<<b[i]<<endl;
    return 0;
}

本文分享自微信公众号 - Python编程 pyqt matplotlib(wsplovePython),作者:wsp001

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • openCV 简单物体识别

    本篇的例子介绍使用numpy和 OpenCV ,仅根据识别对象的尺寸和颜色进行简单的物体识别。专业的图像识别须借助机器学习(含神经网络即深度学习),本篇不做介绍...

    用户6021899
  • 基于Logistic回归和Sigmoid函数的分类(二)

    梯度下降算法每次更新回归系数时都要遍历整个数据集,该方法在处理100个左右的数据集时尚可,但如果有上亿(m)的的样本和上千(n)的特征那么该方法的时间复杂度太高...

    用户6021899
  • TensorFlow-Slim 简介【转载】

    TF-Slim 是 TensorFlow 中一个用来构建、训练、评估复杂模型的轻量化库。TF-Slim 模块可以和 TensorFlow 中其它API混合使用。

    用户6021899
  • 【未完成】【leetcode第 165 场周赛】分割回文串 III

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 15:整理药名

    15:整理药名 总时间限制: 1000ms 内存限制: 65536kB描述 医生在书写药品名的时候经常不注意大小写,格式比较混乱。现要求你写一个程序将医生书...

    attack
  • HDU-5534-Partial Tree

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <algor...

    f_zyj
  • 剑指offer 构建乘积数组

    给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+...

    week
  • P2733 家的范围 Home on the Range

    题目背景 农民约翰在一片边长是N (2 <= N <= 250)英里的正方形牧场上放牧他的奶牛。(因为一些原因,他的奶牛只在正方形的牧场上吃草。)遗憾的是,他的...

    attack
  • P1631 序列合并

    题目描述 有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到 个和,求这 个和中最小的N个。 输入输出格式 输入格式: 第一行一个正整数N; 第...

    attack
  • HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2444

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券