C语言中的5种简单排序算法，适合小白
目录
- 基本概要：
- 1.冒泡排序（Bubble Sort）
- 2.快速排序（Quick Sort）
- 3.插入排序（Insertion Sort）
- 4.简单选择排序（Simple Selection Sort）
- 5.希尔排序（Shell Sort）
- 总结
基本概要：
本文主要介绍五种简单常用的排序算法：冒泡排序，快速排序，插入排序，选择排序，希尔排序。包括它们的基本思想和代码实现。值得一说的是：插入排序，冒泡排序，选择排序平均情况下的时间复杂度为，因此在排序数据较少的情况下较好；而希尔排序和快速排序的平均时间复杂度为，因此在排序数据较多的情况下较好，但是对于快速排序而言，数据基本有序时反而不好，接下来会详细阐述。（皆以从小到大的顺序排列）
1.冒泡排序（Bubble Sort）
基本思想：
冒泡排序是一个非常好理解的排序，顾名思义——冒泡，此时将要排序的数据从上至下排列，从最上面的数（第一个数据）开始对相邻的两个数据进行比较，较小的数据往上浮，较大的数据往下沉，达到排序的效果。
（1）对每一对相邻的元素进行比较，若第一个比第二个大，则调换这两个元素的位置，依次两两比较直到数据的最后一对，此为一轮操作。
（2）重复n轮此操作（n为元素的个数），不过每轮结束后的最后一个元素不用参与下一轮的比较，因为经历一轮排序后，最后一个元素一定比前面所有的元素都要大。
（3）因此每一轮需要比较的元素都在减少，一直到没有数可比较为止。（不过为了减少比较次数，可以记录每轮是否有数据的交换，如果没有交换，表明当前数据已经按从小到大的顺序拍好了，可直接跳出循环）
代码实现：
#include<stdio.h>
int main() {
int n, m, i, j, temp;
int arr[100];
scanf_s("%d", &n); //scnaf_s是更为安全的输入方式；n为元素的个数；
for (i = 0; i < n; i++) {
scanf_s("%d", &arr[i]); //输入数据；
}
m = n; //因为每进行一次第一轮循环，需要排序的数据都要“--”，因此定义变量m=n；
for (i = 0; i < n; i++) {
int exchange = 0; //记录这一轮会不会有数据的交换；
for (j = 0; j < m-1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
exchange = 1;
}
}
m--;
if (!exchange) //若没有数据的交换，则数据已经排列完毕，跳出循环；
break;
}
for (i = 0; i < n; i++) {
printf("%d ", arr[i]); //输出
}
return 0;
}2.快速排序（Quick Sort）
快速排序是这五类中平均性能最优的排序算法，其中运用了分治的思想，并且调用了递归函数，因此也是这五类中最难的一个。
基本思想：
快速排序的重点在于找一个基准值，将数列分为两部分——大于基准值的放在右边，小于基准值的 放在左边。然后分别对这两部分重复次操作，一分为二，二分为四······直到每个元素自成一部分。
1.将数据的中间元素设为基准值，初始化令 指向最左边个元素，令 指向最右边个元素，通过从左往右找一个大于基准数的数，通过从右往左找一个小于基准数的数，交换两数的位置，直到。
2.如此不断的细分递归，达到排序的目的
代码实现：
#include<stdio.h>
void Quicksort(int a[], int left, int right) { //快排函数
int temp;
int mid = a[(left + right) / 2]; //找基准值
int i = left;
int j = right;
//在左侧找一个大于基准值的数，在右侧找一个小于基准数的数，然后交换位置
while (i <= j) {
while (a[i] < mid) i++;
while (a[j] > mid) j--;
if (i <= j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < right) Quicksort(a, i, right); //递归
if (j > left) Quicksort(a, left, j); //递归
}
int main() {
int n, m, i;
int arr[100];
scanf_s("%d", &n);
for (i = 0; i < n; i++) {
scanf_s("%d", &arr[i]); //输入
}
Quicksort(arr, 0, n - 1); //调用函数
for (i = 0; i < n; i++) {
printf("%d ", arr[i]); //输出
}
return 0;
}3.插入排序（Insertion Sort）
基本思想：
将数据分为两组——一组是有序的，一组是无序的，将无序数据中的元素依次插入到有序数据中，从而将整个数据变为有序的（这里的分组是潜意识的，实际上并不会用两个数组来分）
1.初始时，将第一个元素分为有序组（因为只有一个元素，所以认为它是排好序的），其余元素分为无序组
2.因此只需从第二个元素开始，依次在有序组中找到自己的位置，插入即可，直到最后一个元素。
3.但这并不意味着只需要一次循环，因为在“找自己的位置”的过程中，需要将自己与前面的元素相比较，若是自己较小，则将那个元素后移一位；若是自己较大，则将自己插入到上一次比较的位置
代码实现：
#include<stdio.h>
int main() {
int n, m, i, j, temp;
int arr[100];
scanf_s("%d", &n);
for (i = 0; i < n; i++) {
scanf_s("%d", &arr[i]); //输入
}
for(i=1; i<n; i++) //从无序组的第一个元素开始
if(arr[i] < arr[i-1]) // 判断是否要向前寻找插入的位置
{
int temp = arr[i];
for(j=i-1; j>=0 && arr[j]>temp; j--) //将大于自己的数依次向后挪位
arr[j+1] = arr[j];
arr[j+1] = temp; //插入
}
for (i = 0; i < n; i++) {
printf("%d ", arr[i]); //输出
}
return 0;
}4.简单选择排序（Simple Selection Sort）
基本思想：
设一个数据集有n个元素，选择这n个元素中最小的一个与第一个元素交换位置，再在剩下的n-1个元素中选择最小的一个与第二个元素交换位置，直到在最后两个元素中选择最小的一个放在倒数第二的位置上，排序完成。
代码实现：
#include<stdio.h>
int main() {
int n, m, i, j, p, temp;
int arr[100];
scanf_s("%d", &n);
for (i = 0; i < n; i++) {
scanf_s("%d", &arr[i]); //输入
}
for (i = 0; i < n - 1; i++) {
p = i; //p用于记录最小元素的下标
for (j = i + 1; j < n; j++) { //找到剩下元素中最小的那一个
if (arr[p] > arr[j])
p = j;
}
temp = arr[i]; //temp是交换两数时的中间变量
arr[i] = arr[p];
arr[p] = temp;
}
for (i = 0; i < n; i++) {
printf("%d ", arr[i]); //输出
}
return 0;
}5.希尔排序（Shell Sort）
希尔排序是插入排序的优化，它先将待排序列进行预排序，然后对次序列进行一次插入排序，不一样的是经过预处理之后的插入排序时间复杂度为
基本思想：
定义一个间隔gap，在一组数据中，将相隔为gap的元素作为一个组，对组内元素执行简单的插入排序，然后不断缩小gap重复此操作，完成数据的预处理，直到gap=1，表示对所有数进行插入排序，算法终止。
1.初始化（n为元素个数），将数据中所有距离为gap的元素分在一组（此时这组数据会被分成个组，每组有两个元素，对每个组进行排序）
2.接着缩小gap至，将数据中所有距离为gap的元素分在一组（此时这组数据会被分成个组，每组有四个元素，对每个组进行排序）
3.重复直到gap=1，此时数据为一组，有n个元素，简单插入排序即可。
代码实现：
#include<stdio.h>
int main() {
int n, m, i, j, temp,gap;
int arr[100];
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]); //输入
}
for(gap=n/2; gap>0; gap/=2)
for(i=gap; i<n; i++)
for(j=i-gap; j>=0 && arr[j]>arr[j+gap]; j-=gap){
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
for (i = 0; i < n; i++) {
printf("%d ", arr[i]); //输出
}
return 0;
}总结
原文地址：https://blog.csdn.net/Finecsr/article/details/124410411