选择、冒泡、快速排序

一.选择排序

要点:按顺序依次选择数组中的元素,然后遍历数组找出数组中的最小值所在的元素,最后再交换这2个元素。只需要排n-1次。因为要通过2重循环实现排序过程,所以时间复杂度为O(n^2)。

#include<stdio.h>
int a[10000];
int n;
 
int main(){
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]); //输入要排序的n个数

    int idx;
    int tem;
    for(i=0;i<n-1;i++){ 
        idx=i; //每次选择要排的数为a[i],用idx存放最小值所在下标,i从0开始,遍历n-1次,即只需要排i-1次 
        for(j=i+1;j<n;j++){
            if(a[j]<a[idx]){
                idx=j;
            }
        }//寻找最小值所在的下标,随着i的增大,每次寻找的范围-1 
        tem=a[i];
        a[i]=a[idx];
        a[idx]=tem;    //用a[i]去交换每次循环中最小值的那个数 
    }
    
    for(i=0;i<n;i++){
        printf("%d ",a[i]);//从小到大输出排好的数 
    }
     return 0; 
}

二.冒泡排序

要点:要实现将n个数排序,只需要进行n-1次循环。每次循环都把当前最大的元素放在数组后面的合适位置,最终第一个元素即为最小值。因为要通过2重循环实现排序过程,所以时间复杂度也为O(n^2)。

#include<stdio.h>
int a[10000];
int n;

void swap(int *x, int *y){
    int t=*x;
    *x=*y;
    *y=t;
}//用来交换2个变量的值 

void bubble(int *a,int n){
    int i,j;
    for(i=1;i<n;i++){//外层循环,若需要排序的个数为n,只需要循环n-1,即排序n-1次;从第二个元素开始排序,循环结束后第一个元素即为最小值 
        for(j=0;j<n-i;j++){ //内层循环, 循环次数为 n-i;随i的增大而减小 
            if(a[j]>a[j+1])
               swap(&a[j],&a[j+1]);//比较相邻的2个数,并且将大的数往后放; 
        }
    }
}//冒泡排序的实现过程 

int main(){
    int i,j;
    scanf("%d",&n); 
    for(i=0;i<n;i++) scanf("%d",&a[i]);//输入n个数 
    bubble(a,n);//调用bubble函数进行排序 
    for(i=0;i<n;i++) printf("%d ",a[i]);//将排序好的数从小到大输出 
    return 0;
} 

三.快速排序

要点:利用分治和递归的思想,对冒泡排序的改进。时间复杂度为O(n log2 n)

#include<stdio.h>
int a[10000];
int n;

void fastsort(int l,int r){
    int i=l, j=r;
    int tem;
    int mid=a[(l+r)/2];//分治思想 
    do{
        while (a[i]<mid) i++;//在左半部分寻找比中间值大的数 
        while (a[j]>mid) j--;//在右半部分寻找比中间值小的数 
        if(i<=j){
            tem=a[i];
            a[i]=a[j];
            a[j]=tem;//交换左右2部分的数 
            i++;
            j--;//进行下一次寻找 
        } 
    }while(i<=j);
    
    if(l<j) fastsort(l,j);
    if(i<r) fastsort(i,r);//分别递归左右区间,重复上面步骤,直至两个数的边界 ;
}

int main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]); //输入要排序的n个数
    fastsort(1,n);
    for(i=1;i<=n;i++) printf("%d ",a[i]); //输出排好的n个数
} 

上一篇:数的三次方根


下一篇:2021-10-26