浅谈冒泡排序与选择排序（C语言）

浅浅的花香味﹌ 2022-05-15 06:52 267阅读 0赞

排序算法有很多，在这里先来聊一聊冒泡排序和选择排序。理解还是不够清楚，后续会继续修改。

*  **冒泡排序**：首先进行第一轮比较，将第一个数与后面所有的数进行比较，遇到后面的数比第一个数大，则交换两者的位置；继续与后面的数比较，直到比较完，一轮下来就找到了最大的数，并将其放在第一个位置；后面从第二数开始，继续比较，一直这样下去，直到比较完。

**代码实现：以对学生成绩排序为例；**

void DataSort(int score[],int n){
    	int i,j,temp;
    	for(i=0;i<n-1;i++){
    		for(j=i+1;j<n;j++){
    			if(score[j]>score[i]){
    				temp = score[j];
    				score[j] = score[i];
    				score[i] = temp;
    			}
    		}
    		
    	}
    }

**全部代码：实现录入学生某门课程成绩，并将其进行降序排列；**

#include<stdio.h>
    
    //交换排序(冒泡排序)，实现对学生成绩的排名 
    #define N 40
    int ReadScore(int score[]); //读取学生某门课的成绩
    void DataSort(int score[],int n);  //对学生成绩进行排名
    void PrintScore(int score[],int n); //输出排序后的学生成绩
     
    int main(){
    	int score[N],n;
    	n = ReadScore(score); //输入学生成绩，返回学生人数
    	printf("Total students are %d\n",n);
    	DataSort(score,n);
    	printf("Sorted scores:");
    	PrintScore(score,n);
    	return 0;
    }
    
    //读取学生成绩，输入负数表示结束 
    int ReadScore(int score[]){
    	int i = -1; //保证循环体内i从0开始 
    	printf("Please input score:\n");
    	do{
    		i++;
    		scanf("%d",&score[i]);
    	}while(score[i]>=0);
    	return i;
    } 
    
    //对学生成绩进行降序排列
    void DataSort(int score[],int n){
    	int i,j,temp;
    	for(i=0;i<n-1;i++){
    		for(j=i+1;j<n;j++){
    			if(score[j]>score[i]){
    				temp = score[j];
    				score[j] = score[i];
    				score[i] = temp;
    			}
    		}
    		
    	}
    } 
    
    void PrintScore(int score[],int n){
    	int i;
    	for(i=0;i<n;i++){
    		printf("%4d",score[i]);
    	}
    	printf("\n");
    }

**结果：**

![70][]

*  **选择法排序：**对冒泡排序的改进，通过设置key，用于记录最大数下标，每一轮只进行一次交换；

**代码实现：**

//对学生成绩进行升序排列
    void DataSort(int score[],int n){
    	int i,j,k,temp;
    	for(i=0;i<n-1;i++){
    		k=i;
    		for(j=i+1;j<n;j++){
    			if(score[j]<score[k]){
    				k=j;                //记录最大下标位置 
    			}
    		}
    		if(k != i){                 //若最大数所在的下标位置不在下标位置，则交换 
    			temp = score[k];
    			score[k] = score[i];
    			score[i] = temp;
    		}
    	}
    }

**两者比较：**

**冒泡排序比选择排序交换次数多，但时间和空间效率差不多，时间复杂度都为O(n2)。**

**有错误的地方望大家指出，欢迎交流~**

[70]: /images/20220515/e7fc04737567481ebde3cce81b9960b1.png