一.选择排序:
要点:按顺序依次选择数组中的元素,然后遍历数组找出数组中的最小值所在的元素,最后再交换这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个数
}