排序法 C语言常考的十大排序法 数列、字符的排序_字符排序c语言

通过对近各大试卷题型分析，总结出 对于数据排序的十大方法，希望对大家有所帮助

方法一：冒泡排序法（升序排序法）

方法二：选择排序法

方法三：插入排序法

方法四：希尔排序法（Shell Sort）

方法五：归并排序法

方法六：快速排序法（交换排序法）

方法七：堆排序法

方法八：计数排序法

方法九：桶排序法

方法十：基数排序法

1.冒泡排序法

1.1 算法描述
步骤1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
步骤2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应               该会是最大的数；
步骤3: 针对所有的元素重复以上的步骤，除了最后一个；
步骤4: 重复步骤1~3，直到排序完成。

（1）对数列的排序：

#include <stdio.h>
#define sequence 10//自定义十个元素的数列
int main()
{
    int a[sequence] = {12,43,9,13,67,98,101,89,3,35 };//十个数的无序数列
                                                      //也可以改为用scanf输入
    int i, j, t;
    printf("此程序使用冒泡排序法排列无序数列！\n");
    //冒泡排序
    for (i = 0; i < 10 - 1; i++)//n个数的数列总共扫描n-1次
    {
        for (j = 0; j < 10 - i - 1; j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
        {
            if (a[j] > a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序）
            {
                t = a[j + 1];
                a[j + 1] = a[j];
                a[j] = t;
            }
        }
    }
    printf("排列好的数列是：\n");
    //输出排列好得吃数列
    for (i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

运行结果如下：

（2）对字符的排序

#include <stdio.h>
#define Character_groups 10//定义了十个字符的字符数组
int main()
{
    char a[Character_groups] = { 'i','l','o','v','e','y','o','u','y','x' };//十个数的无序数列  
   //也可以改用scanf函数输入字符
    int i, j;
    char t;
    printf("此程序使用冒泡排序法排列无序数列！\n");
    //冒泡排序
    for (i = 0; i < 10 - 1; i++)//n个数的数列总共扫描n-1次
    {
        for (j = 0; j < 10 - i - 1; j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
        {
            if (a[j] > a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序）
            {
                t = a[j + 1];
                a[j + 1] = a[j];
                a[j] = t;
            }
        }
    }
    printf("排列好的字符组是：\n");
    //输出排列好得吃数列
    for (i = 0; i < 10; i++)
    {
        printf("%c ", a[i]);
    }
    return 0;
}

运行结果如下：

     

           对字符串的排序----（自定义函数的方法实现）

#include <stdio.h>
 
void function(char a[], int m)
{
    //冒泡排序
    int i, j;
    char tmp;
    for (i = 0; i < m - 1; i++)//n个数的数列总共扫描n-1次
    {
        for (j = 0; j < m - i - 1; j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
        {
            if (a[j] > a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序）
            {
                tmp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = tmp;
            }
        }
    }
    return;
}
 
int main()
{
    void function(char a[], int);//尤其注意，此处的函数声明必须是char a[],因为这里穿的是地址，不能仅仅使用char
    int i;
    char a[10] = { 'i','l','o','v','e','y','o','u','y','x' };//十个数的无序字符数列
    printf("此程序使用冒泡排序法排列无序数列！\n");
    function(a, 10);//调用冒泡排序
    printf("排列好的字符组是：\n");
    //输出排列好得吃数列
    for (i = 0; i < 10; i++)
    {
        printf("%c ", a[i]);
    }
    return 0;
}

运行结果如下：

2.选择排序法

步骤1：初始状态：无序区为R[1…n]，有序区为空；
步骤2：第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排              序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使                    R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
步骤3：n-1趟结束，数组有序化了。

两层for循环实现 

#include <stdio.h>
 
int main()
{
    int i, j, k, n, tmp, a[1000];
    printf("请输入需要排序的数据个数\n");
    scanf("%d",&n);// 从键盘输入待排序的数据个数
    for (i = 0; i < n; i++) 
    { // 利用for循环依次将输入的数据放置在数组中
        scanf("%d",&a[i]);
    }
    for (i = 0; i < n - 1; i++) 
    {// 外层循环 变量i控制排序总共进行n-1轮
        k = i;
        for (j = i + 1; j < n; j++) 
        { //内层循环 变量j控制每轮进行比较的次数
            if (a[j] < a[k])
            {
                k = j;   //k记录每轮比较中的最小者的下标
                if (k != i) 
                { //将第i轮的最小者，与a[i]交换
                    tmp = a[i];
                    a[i] = a[k];
                    a[k] = tmp;
                }
            }
        }
    }
    printf("排序后的数据如下：\n");
    for (i = 0; i < n; i++) { // 利用for循环进行输出
        printf("%d\t", a[i]);
    }
    return 0;
}

     运行结果如下：

   自定义函数的方法实现

#include<stdio.h>
 
void SelectSort(int a[], int n) 
{ //选择排序
    int mix, tmp;
    int i, j;
    for (i = 0; i < n - 1; i++) 
    { //每次循环数组，找出最小的元素，放在前面，前面的即为排序好的
        mix = i; //假设最小元素的下标
        for (j = i + 1; j < n; j++) //将上面假设的最小元素与数组比较，交换出最小的元素的下标
            if (a[j] < a[mix])
                mix = j;
        //若数组中真的有比假设的元素还小，则交换
        if (i != mix) 
        {
            tmp = a[i];
            a[i] = a[mix];
            a[mix] = tmp;
        }
    }
}
 
int main()
{
    int a[10] = { 9,1,5,8,3,7,4,6,2,0 };
    int i;
    SelectSort(a, 10);
    for (i = 0; i < 10; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

 运行结果如下：

指针传参方法实现：

#include<stdio.h>
//指针方法实现十个整数的排序
int main()
{
    void sort(int x[], int n);//函数的声明
    int i, * p, a[10];//定义i，*p，数组a
    p = a;//把首元素的地址赋值给指针变量p
    printf("please enter 10 integer numbers:");
    for (i = 0; i < 10; i++)
    {
        scanf("%d", p++);//将从数组的每一个元素的地址都存到内存当中去
    }
    p = a;//再次将指针p指向首元素的地址
    sort(p, 10);//函数的调用
 
    for (p, i = 0; i < 10; i++)//输出语句    可以写p=a；或者直接写p
    {
        printf("%d ", *p);
        p++;
    }
    printf("\n");
    return 0;
}
 
void sort(int x[], int n)
{
    int i, j, k, t;
    for (i = 0; i < n - 1; i++)//外层循环控制比较的总趟数  n-1趟
    {
        k = i;//第一次先将下标0对应的元素作为最大元素的下标
        for (j=i+1; j < n ; j++)//内层循环控制每趟比较的总次数
        {
                if (x[j] > x[k])
                {
                    k = j; //k始终保存最大值元素的下标
                }    
        if(k!=i)//如果最大值元素的下标不是最前面的i，则交换元素值
        {
            t = x[i];
            x[i] = x[k];
            x[k] = t;
        }
            }
    }
}

代码运行结果如下：

3.插入排序法

步骤1: 从第一个元素开始，该元素可以认为已经被排序；
步骤2: 取出下一个元素，在已经排序的元素序列中从后向前扫描；
步骤3: 如果该元素（已排序）大于新元素，将该元素移到下一位置；
步骤4: 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
步骤5: 将新元素插入到该位置后；
步骤6: 重复步骤2~5。

（1）简单方法实现 

#include<stdio.h>
#include<string.h>
#define sequence 5
void insertSort(int a[])
{
    int i, j, temp;
    for (i = 1; i < sequence; i++)
    {
        temp = a[i];
        //当前数小于前一位数时
        if (a[i] < a[i - 1])
        {
            //将子序列重新排列为有序序列
            for (j = i - 1; temp < a[j]; j--)
            {
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }
}
int main()
{
    int a[] = { 45,32,56,71,12 };
    int i;
    printf("未排序前：\n");
    for (i = 0; i < sequence; i++)
    {
        printf("%d  ", a[i]);
    }
    printf("\n经过直接插入排序后：\n");
    insertSort(a);
    for (i = 0; i < sequence; i++)
    {
        printf("%d  ", a[i]);
    }
    return 0;
}

 运行结果如下：

 （2）自定义函数方法实现

#include <stdio.h>
 
void print(const int* a, const int length)
{
    int i;
    for (i = 0; i < length; i++) 
    {
        printf("%d ", a[i]);
    }
    putchar('\n');
}
 
void pushFront(int* a, const int length, const int key)
{
    //将所有a[j]到a[length]都往后推一格
    int tmp = a[length];
    for (int i = length; i > key; i--)
    {
        a[i] = a[i - 1];
    }
    a[key] = tmp;
}
 
void insertSort(int* a, const int length)
{
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[i] < a[j])
            {
                pushFront(a, i, j);
                break;
            }
        }
        print(a, i + 1);
    }
}
 
int main() 
{
    const int length = 5;
    int my_array[5] = { 1,5,4,3,7 };
    print(my_array, length);
    insertSort(my_array, length);
    return 0;
}

     运行结果如下：

 （3）折半插入排序法实现

#include<stdio.h>
#define N 10
 
//对数组a进行折半插入排序，n为数组的长度；
void Half_Sort(int a[])
{
    for (int i = 1; i < N; i++)
    {
        int x = a[i];   //将需要进行插入排序的元素赋值给x；
        int low = 0, high = i - 1;  //设置折半的头和尾；
        while (low <= high)
        {
            int mid = (low + high) / 2;  //设置中间元素，与插入的元素进行比较；
            if (x < a[mid])   //比较；
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (int j = i - 1; j >= low; j--)  //记录依次向后移；
            a[j + 1] = a[j];   //将当前这个值赋给这个元素的后一个元素；
        a[low] = x;   //插入记录；
    }
}
 
int main()
{
    int a[N] = { 3,2,8,5,4,7,6,9,1,10 };  //定义数组；
    printf("原始数据为:\n");
    for (int i = 0; i < N; i++)  //输出原始数据；
        printf("%d ", a[i]);
    printf("\n\n");
 
    Half_Sort(a);
    printf("使用插入排序后的数据为:\n");
    for (int i = 0; i < N; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

运行结果如下：