C语言零基础——简单的排序算法（4种）

背景：输入十个数，以降序排列的形式输出

这里介绍选择排序法、冒泡排序法 两大基础经典排序法

两个程序的区别仅在trans()函数的排序方法不同，为方便复制体验，以完整代码呈现

1、选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

步骤：

1. 从待排序的数据元素中选出最小（大）的一个元素，存放在序列的起始位置。

2. 然后再从剩余未排序元素中寻找最小（大）元素，然后放到已排序序列的末尾。

3. 以此类推，直到所有元素均排序完毕。

#include<stdio.h>
#define N 10//宏定义
int b[N];//函数声明
void menu();//函数声明
int input()//函数声明
int trans(int a);//函数声明
void show(int b);//函数声明
​
main()
{
  menu();//函数调用
  b=input();//函数调用
  b=trans(b);//函数调用
  show(b);//函数调用
}
​
void menu()//菜单函数
{
printf("***********************\n");
printf("本程序能将输入的整数降序排列\n");
printf("***********************\n");
}
​
int input()//输入十个数
{
  printf("请输入十个整数");
  int i;
  int a[10];
  for(i=1;i<=10;i++)
  {
    printf("%d:",i);
    scanf("%d",&a[i-1]);
  }
  return a;
}
​
int trans(int a);//选择排序法
{
  int max,i,j;
  for(i=0;i<N-1;i++)
  {
    max=i;
    for(j=i+1;j<N;j++)
      if(a[i]>a[max])
        max=j;
    if(max!=j)
    {
      t=a[max];
      a[max]=a[i];
      a[i]=t;
    }
  }
  return a;
}
​
void show(int b)//输出排序好的数组元素
{
  int i;
  for(i=0;i<10;i++)
   printf("%d",b[i]);
}

tips:

这里复习以下几点：

• #define 为宏定义，在开头改N的值，即可改变所有N的值

• 这里选用的是选择排序法，需要记住这个套路（选择排序具体体现在函数trans()）

• C语言要多用自定义函数，养成模块化的习惯

• trans函数传递的是数组的首地址（即首字母）

2、冒泡排序法

冒泡排序的基本思想是重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。

步骤：

1. 比较相邻的两个元素，如果第一个比第二个大，就交换它们两个。

2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

#include<stdio.h>
#define N 10//宏定义
void menu();//函数声明
int input()//函数声明
int trans(int a);//函数声明
void show(int b);//函数声明
main()
{
  int b[N];//函数声明
  menu();//函数调用
  b=input();//函数调用
  b=trans(b);//函数调用
  show(b);//函数调用
}
​
void menu()//菜单函数
{
printf("***********************\n");
printf("本程序能将输入的整数降序排列\n");
printf("***********************\n");
}
​
int input()//输入十个数
{
  printf("请输入十个整数");
  int i;
  int a[10];
  for(i=1;i<=10;i++)
  {
    printf("%d:",i);
    scanf("%d",&a[i-1]);
  }
}
​
int trans(int a);//冒泡排序法
{
  int t,i,j;
  for(i=0;i<N-1;i++)
    for(j=0;j<N-1-i;j++)
      if (a[j] > a[j+1])
      { 
        t = a[j];
        a[j] = a[j+1];
        a[j+1] = t;
      }
}
​
void show(int b)//输出排序好的数组元素
{
  int i;
  for(i=0;i<10;i++)
   printf("%d",b[i]);
}

3、插入排序法

插入排序的基本思想是将一个记录插入到已排序好的有序表中，从而得到一个新的、数量加一的有序表。这个过程一直重复，直到所有记录都被插入到有序表中。

步骤：

1. 从无序元素中取出第一个元素，将其插入到有序序列中（有序序列初始时只包含一个元素，即无序序列的第一个元素）。

2. 对于无序序列中的第二个元素起，按以下步骤操作：

• 比较有序序列中的最后一个元素与要插入的元素，如果后者小于前者，则将有序序列中的元素后移一位。

• 重复上述比较和后移操作，直到找到合适的插入位置或到达有序序列的开头。

• 将元素插入到找到的位置。

1. 重复步骤2，直到所有元素都被插入到有序序列中。

#include<stdio.h>
#define N 10
​
void menu();
int input();
void insertSort(int a[]);
void show(int b[]);
​
int main() {
    int b[N];
    menu();
    input();
    insertSort(b);
    show(b);
    return 0;
}
​
void menu() {
    printf("***********************\n");
    printf("本程序能将输入的整数降序排列\n");
    printf("***********************\n");
}
​
int input() {
    printf("请输入十个整数：\n");
    int i, a[10];
    for (i = 0; i < 10; i++) {
        printf("%d: ", i + 1);
        scanf("%d", &a[i]);
    }
    return a[0]; // 返回数组的第一个元素，因为数组在函数间传递时会退化为指针
}
​
void insertSort(int a[]) {
    int i, j, key;
    for (i = 1; i < N; i++) {
        key = a[i];
        j = i - 1;
​
        // 将a[i]插入到已排序序列a[0...i-1]中的适当位置
        while (j >= 0 && a[j] < key) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key;
    }
}
​
void show(int b[]) {
    int i;
    for (i = 0; i < 10; i++)
        printf("%d ", b[i]);
    printf("\n");
}

4、快速排序法

快速排序的基本思想是分治法，通过一个基准值将数据分为两部分，一部分数据比基准值小，另一部分数据比基准值大，然后递归地排序这两部分。

步骤：

1. 选择一个基准值（pivot）。

2. 重新排列数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

• 对基准值左边的子数列进行快速排序。

• 对基准值右边的子数列进行快速排序。

1. 由于基准值已经位于正确的位置，所以不需要再对基准值进行排序。

2. 递归到基准值的左右子数列都为空时，整个数列就完成了排序。

#include<stdio.h>
#define N 10
​
void menu();
int input();
void quickSort(int a[], int low, int high);
int partition(int a[], int low, int high);
void show(int b[]);
​
int main() {
    int b[N];
    menu();
    input();
    quickSort(b, 0, N - 1);
    show(b);
    return 0;
}
​
void menu() {
    printf("***********************\n");
    printf("本程序能将输入的整数降序排列\n");
    printf("***********************\n");
}
​
int input() {
    printf("请输入十个整数：\n");
    int i, a[10];
    for (i = 0; i < 10; i++) {
        printf("%d: ", i + 1);
        scanf("%d", &a[i]);
    }
    return a[0]; // 返回数组的第一个元素，因为数组在函数间传递时会退化为指针
}
​
void quickSort(int a[], int low, int high) {
    if (low < high) {
        int pi = partition(a, low, high);
​
        quickSort(a, low, pi - 1);  // Before pi
        quickSort(a, pi + 1, high); // After pi
    }
}
​
int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = (low - 1);
​
    for (int j = low; j <= high - 1; j++) {
        if (a[j] > pivot) {
            i++;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
​
    int temp = a[i + 1];
    a[i + 1] = a[high];
    a[high] = temp;
​
    return (i + 1);
}
​
void show(int b[]) {
    int i;
    for (i = 0; i < 10; i++)
        printf("%d ", b[i]);
    printf("\n");
}

p.s.

小红书，知乎等平台搜索知识薪火站（或youzuos），也会上传相应笔记，感谢关注。

有建议欢迎提出！