首页 > 其他分享 >排序2-选择排序

排序2-选择排序

时间:2024-04-21 22:34:28浏览次数:35  
标签:arr min int MAX 选择 ++ 排序

排序2-选择排序


每次找到最值的下标, 最后交换元素, 每次遍历的元素减少. 减少了交换元素的次数. 性能较冒泡排序更好一点, 但时间复杂度仍是$O(n^2)$


交换元素

//交换
void Swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

打印数组

void PrintArray(int arr[]){
    int len = MAX;
    for (int i = 0; i < len; i++){
        cout << arr[i] << " ";
    }
    cout << endl;    
}

选择排序

void SelectSort(int arr[], int length){
    for (int i = 0; i < length; i++){
        int min = i; //默认第一个为最小元素
        for (int j = i+1; j < length; j++){
            if(arr[j]>arr[min])
                min = j; //更新最小元素的下标
        }
        if(min!=i) //如果最小元素不是初始值, 就交换位置
            Swap(&arr[min],&arr[i]);
    }    
}

冒泡排序

void BubbleSort(int arr[]){
    int flag = 0; //0表示false, 标志没有排序好
    int len = MAX;
    for (int i = 0; i<len; i++){
        flag = 1; //如果flag没有被更新为0, 认为已经排序好了
        for (int j = 0; j < len-1-i; j++){
            if(arr[j]>arr[j+1]){
                flag = 0; //认为没有排序好
                Swap(&arr[j], &arr[j+1]);
            }
        }
    }
}

测试

int main(){
    int arr[MAX];
    srand((unsigned int)time(NULL));
    for (int i = 0; i < MAX; i++){
        arr[i] = rand() % MAX;
    }

    int arr2[MAX];
    srand((unsigned int)time(NULL));
    for (int i = 0; i < MAX; i++){
        arr2[i] = rand() % MAX;
    }

    long t1 = getSystemTime();
    SelectSort(arr,MAX);
    long t2 = getSystemTime();

    long t3 = getSystemTime();
    BubbleSort(arr);
    long t4 = getSystemTime();

    cout << "选择排序时间:" << t2-t1 << endl;
    cout << "冒泡排序时间:" << t4-t3 << endl;

    system("pause");
    return 0;
}

标签:arr,min,int,MAX,选择,++,排序
From: https://www.cnblogs.com/HIK4RU44/p/18149639

相关文章

  • 过滤与排序
    排序与过滤​ 查询所有才需要过滤,排序是按照某个规则排序排序简单使用导入类OrderingFilter在视图类重写filter_backends属性,在列表内填入导入的类重写ordering_fields属性,在列表内填入字段classBookView(ModelViewSet):queryset=Book.objects.all()serial......
  • 排序1-冒泡排序
    排序1-冒泡排序冒泡排序的次数是递减的,第一次确定了最大元素的位置,所以第二次只需要进行n-1次排列,第二次确定了第二大元素的位置,所以第三次只需要进行n-2次排列,以此类推for(inti=0;i<len;i++){//每次遍历的次数是递减的//所以j=len-1-i......
  • uni app uview新增商品页(无限级分类选择和多图上传)
    uniappuview新增商品页(无限级分类选择和多图上传)给自己的牛腩商品库UNIAPP加的一个新增功能,就是通用的新增页面,用的uview2(https://uviewui.com/components/intro.html),能选择无限级分类和多图上传,自已觉得这个新增页面在以后做uniapp项目的时候很多地方会用到吧,先记下来了,以......
  • 归并排序
    归并排序左部分有序 ---> 右部分有序 --->整体有序查看代码//https://leetcode.cn/problems/sort-an-array/importjava.util.Arrays;classSolution{publicstaticfinalintMAX_N=100001;publicstaticint[]help=newint[MAX_N];publi......
  • 选择语句 - if、if-else 和 switch
    选择语句- if、if-else 和 switch项目2023/08/014个参与者反馈 本文内容if语句switch语句C#语言规范另请参阅if、if-else 和 switch 语句根据表达式的值从多个可能的语句选择要执行的路径。仅当提供的布尔表达式的计算结果为 true 时,if,if 语......
  • 说说常见的排序算法有哪些?区别?
    一、是什么排序是程序开发中非常常见的操作,对一组任意的数据元素经过排序操作后,就可以把他们变成一组一定规则排序的有序序列排序算法属于算法中的一种,而且是覆盖范围极小的一种,彻底掌握排序算法对程序开发是有很大的帮助的对与排序算法的好坏衡量,主要是从时间复杂度、空间复......
  • 国内chatGPT中文版网站有哪些?国内人工智能百花齐放!该如何选择?
    人工智能技术在中国的快速发展和普及,使得国内的人工智能产业日益壮大。在这些领域中,自然语言处理技术和聊天机器人已经取得了显著的进展。ChatGPT作为一种基于深度学习的聊天机器人模型,在国内得到了广泛的关注和应用。目前,有几个国产ChatGPT中文版网站备受瞩目。国产chatGPT汇总:......
  • 希尔排序
    #include<iostream>#include<cmath>usingnamespacestd;intmain(){intn;cin>>n;inta[n+5];for(inti=0;i<n;i++){cin>>a[i];}for(doublei=n;i>1;){i=round(i/2);for(i......
  • 希尔排序
    #include<bits/stdc++.h>usingnamespacestd;intmain(){ stringa="liuyixing"; for(doublei=9;i>1;){ i=round(i/2); for(intj=0;j+i<9;j++){ if(a[j]>a[j+(int)i]){ swap(a[j],a[j+(int)i]); } } } for(inti=0;i<......
  • JZ33 二叉排序树的后序遍历序列
    classSolution{public://判断该数组是不是某二叉搜索树的后序遍历的结果。//如果是则返回true,否则返回false//注意传入参数是一个int类型的vector容器boolVerifySquenceOfBST(vector<int>sequence){if(sequence.empty()) //二叉树......