将一个字符串从小到大排序输出_字符串从小到大排序算法

方法一普通排序（啥也不是时间复杂度o（n……2））：

#include<stdio.h>
int main(void)
{
    char a[1000000];
    scanf("%s",a);
    int n=0;
    for(int i=1;a[i-1]!='\0';n++,i++)
    ;
    /*
    for(int i=1;n>=i;i++)//正常应该这么写
    {
        for(int j=1;n>j;j++)
        {
            if(a[j-1]>a[j])
            {
                char t=a[j-1];
                a[j-1]=a[j];
                a[j]=t;
            }
        }
    }
    */
    int i,j;//如果编译器不行还是把ij定义在外面吧。。。
    for(i=1;n>=i;i++)
    {
        for(j=1;n>j;j++)//不能等于防止越界
        {
            if(a[j-1]>a[j])
            {
                char t=a[j-1];
                a[j-1]=a[j];
                a[j]=t;
            }
        }
    }
    
        puts(a);
}

 

 方法二：冒泡排序（最简单的比较快的方法时间复杂度O（n……2））：

（就是第一种优化一下，每一次少算一个，因为最后一个一定排好了）

#include<stdio.h>
int main(void)
{
    char a[1000000];
    scanf("%s",a);
    int n=0;
    for(int i=1;a[i-1]!='\0';n++,i++)
    ;
    int i,j;//如果编译器不行还是把ij定义在外面吧。。。
    for(i=1;n>=i;i++)
    {
        for(j=1;n-i>=j;j++)//不能等于防止越界
        {
            if(a[j-1]>a[j])
            {
                char t=a[j-1];
                a[j-1]=a[j];
                a[j]=t;
            }
        }
    }
    
        puts(a);
}

方法三：插入排序（每次找最小值）O（n……2）：

#include<stdio.h>
void swap(char *a,char *b)
{
    char t=*a;
    *a=*b;
    *b=t;
}
int main(void)
{
    char a[1000000];
    scanf("%s",a);
    int n=0;
    for(int i=1;a[i-1]!='\0';n++,i++)
    ;
    int i,j=1;//如果编译器不行还是把ij定义在外面吧。。。
    for(i=1;n>=i;i++)
    {
        int min=j-1;
        for(int k=j;n>=k;k++)
            if(a[k-1]<a[min])
            min=k-1;
        swap(&a[min],&a[j-1]);//交换两个值
        j++;
    }
    
        puts(a);
}

方法四：快排（最基本的排序）（O（nlogn）比较快）：

#include<stdio.h>
void swap(char *a,char *b)
{
    char t=*a;
    *a=*b;
    *b=t;
}
void q_sort(int l ,int r ,char a[])
{
    if(l>=r)return;
    int mid=(l+r)>>1;
    char x=a[mid];
    int i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)
        {
            swap(&a[i],&a[j]);
        }
    }
    q_sort(l,j,a);
    q_sort(j+1,r,a);
    return ;
}
int main(void)
{
    int n=0;
    char a[100000];
    scanf("%s",a);
    for(int i=1;a[i-1]!='\0';i++,n++)
    ;
    q_sort(0,n-1,a);
    for(int i=1;n>=i;i++)
    printf("%c",a[i-1]);
    return 0;
}

方法五归并排序（稳定，O（nlongn））：

#include<stdio.h>
char c[100010];
void merge_sort(char a[],int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j])c[k++]=a[i++];
        else
        c[k++]=a[j++];
    }
    while(i<=mid)c[k++]=a[i++];
    while(j<=r)c[k++]=a[j++];
    for(i=l,j=0;j<k;i++,j++)
    {
        a[i]=c[j];
    }
    return;
}
int main(void)
{
    int n;
    char a[100000];
    scanf("%s",a);
    for(int i=1;a[i-1]!='\0';i++,n++)
    ;
    merge_sort(a,0,n-1);
    
    puts(a);
    return 0;
}

方法六：（桶排序O（n））

#include<stdio.h>
int main(void)
{
    int a[400]={0};
    char b;
    while(scanf("%c",&b)!=EOF)
    {
        a[b]++;
    }
    for(int i=1;400>=i;i++)
    {
        for(int j=1;a[i-1]>=j;j++)
        printf("%c",i-1);
    }
    return 0;
}

方法七q_sort;

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a, const void *b)
{
    return *(char*)a - *(char*)b; //由小到大排序
    //return *(int *)b - *(int *)a; 由大到小排序
}
int main(void)
{
    int n;
    char a[10000];
    scanf("%s",a);
    for(int i=1;a[i-1]!='\0';i++,n++)
    ;
    qsort(a, n, sizeof(char), cmp);
    puts(a);
    return 0;
}

还有诸多例如堆排序，选择排序。等等，其实也就快排和归并有点用，其他都没什么用。。。

供自己以后复习使用