搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 计协的那点事儿 > 冒泡排序和选择排序(C语言)

冒泡排序和选择排序(C语言)

计协的那点事儿 2018-07-01

冒泡排序和选择排序(C语言)

 

1.冒泡排序

基本思想:比较相邻的两个数,如果前者比后者大,则进行交换。每一轮排序结束,选出一个未排序中最大的数放到数组后面。

#include<stdio.h>//冒泡排序算法void bubbleSort(int *arr, int n) {   

for (int i = 0; i<n - 1; i++)      

for (int j = 0; j < n - i - 1; j++)
{ //如果前面的数比后面大,进行交换
    if (arr[j] > arr[j + 1]) {             

 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
 }
}        }

int main()

 {   

 int arr[] = { 10,6,5,2,3,8,7,4,9,1 };   

 int n = sizeof(arr) / sizeof(int);
bubbleSort(arr, n);
printf("排序后的数组为:\n");   

for (int j = 0; j<n; j++)
printf("%d ", arr[j]);

printf("\n"); 
return 0;

分析:

最差时间复杂度为O(n^2),平均时间复杂度为O(n^2)。稳定性:稳定。辅助空间O(1)。

2.选择排序

基本思想:依次选出数组最小的数放到数组的前面。首先从数组的第二个元素开始往后遍历,找出最小的数放到第一个位置。再从剩下数组中找出最小的数放到第二个位置。以此类推,直到数组有序。

#include<stdio.h>

void SelectSort(int *a, int n) {  

 for (int i = 0; i < n; i++)
{int key = i; //临时变量用于存放数组最小值的位置
for (int j = i + 1; j < n; j++) {         

if (a[j] < a[key]) {    

               key = j;    //    记录数组最小值位置            }
       }            if (key != i)
 {int tmp = a[key]; a[key] = a[i]; a[i] = tmp;// 交换最小值            }
   }
}int main() {    int a[] = { 12,4,15,2,6,22,8,10,1,33,45,24,7 };  

 int n = sizeof(a) / sizeof(int);
SelectSort(a, n);

printf("排序好的数组为: "); 

for (int k = 0; k < n; k++)

printf("%d ", a[k]);
printf("\n");    return 0;
}

分析:

最差、最优、平均时间复杂度都为O(n^2)。辅助空间为O(1)。稳定性:不稳定。

排版:张译丹

审核:陈佳


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《冒泡排序和选择排序(C语言)》的版权归原作者「计协的那点事儿」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注计协的那点事儿微信公众号

计协的那点事儿微信公众号:LQJX2017

计协的那点事儿

手机扫描上方二维码即可关注计协的那点事儿微信公众号

计协的那点事儿最新文章

精品公众号随机推荐