C语言中的几种排序算法

C语言中的几种排序算法

在编程练习时，我们经常会遇到一些将一串乱序的数字排列成有序的数列（递增，递减）的问题，以此起到解决问题的效果。目前我使用的比较熟练的有三种排序算法，冒泡排序法，快速排序法，另外一个是C++中的sort算法。

1. 冒泡排序法 冒泡排序法是比较好理解，硬排的一种算法，缺点是当数列的元素过大时，排序的效率会比较低，时间复杂度会比较高。最好的情况时，复杂度为O（n），最差的为O（n*n），做题时经常会出现超时的现象。 冒泡排序法使用两层for循环嵌套，第一层循环确定以那个元素开始比较，第二层循环在数组内比较大小。 *代码如下

#include<stdio.h>
int a[100];//数组定义在main函数外，防止元素个数过多爆栈，且数组内元素自动清零
int main()
{
          
   
    int n,i,j,tmp;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)//第i个元素与本行所有元素比较
    {
          
   
        if(a[i]>a[j])//递增
        {
          
   
            tmp=a[i];
            a[i]=a[j];
            a[j]=tmp;//交换值，大的数顺序提前
        }
    }
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}

2. 快速排序法（quicksort） 快速排序法运用了分治策略和递归算法，主要先定义一个基准点（一般选在数组中间），在基准点的两端开始排序，左边遇到比基准点大的，右边遇到比基准点小的，交换数值。 *代码如下

#include<stdio.h>
int a[100];
void quicksort(int a[],int left,int right)
{
          
   
    int i=left,j=right,mid=a[(i+j)/2],tmp;
    while(i<j)
    {
          
   
        while(a[i]<mid)i++;//找到比基准点大的退出循环
        while(a[j]>mid)j--;//找到比基准点小的退出循环
        if(i<=j)
        {
          
   
            tmp=a[i];
            a[i]=a[j];
            a[j]=tmp;
            i++;//左边继续往后遍历
            j--;//右边继续往前遍历
        }
    }
    //i>j指遍历错开基准点，此时分为左右两部分，继续递归执行quicksort
    if(left<j)quicksort(a,left,j);
    if(i<right)quicksort(a,i,right);
}
int main()
{
          
   
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    quicksort(a,0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}

3. sort（C++） sort是C++中的一个函数，使用时要包含头文件#include， sort函数的模板有三个参数：

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); （1）第一个参数first：是要排序的数组的起始地址。

（2）第二个参数last：是结束的地址（最后一个数据的后一个数据的地址）sort(数组名，数组名+数组元素个数，排序方法)

（3）第三个参数comp是排序的方法：可以是从升序也可是降序。如果第三个参数不写，则默认的排序方法是从小到大排序。

元素自身包含了比较关系，如int，double等基础类型，可以直接进行比较greater() 递减， less() 递增（省略）

*代码如下

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp1(int x,int y)
{
          
   
    return x>y;//x>y时，bool型返回true，x置于y前
}
bool cmp2(int x,int y)
{
          
   
    return x<y;//x>y时，bool型返回true，x置于y前
}
int a[105];
int main()
{
          
   
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n,greater<int>());//从大到小
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    sort(a,a+n,cmp1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    sort(a,a+n,less<int>());//从小到大
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    sort(a,a+n,cmp2);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

后续会继续补充