C语言的5种简单排序算法

您所在的位置：网站首页 › c语言中的快速排序 › C语言的5种简单排序算法

C语言的5种简单排序算法

2024-05-28 19:00| 来源: 网络整理| 查看: 265

基本概要：

1.冒泡排序（Bubble Sort）

基本思想：

代码实现：

2.快速排序（Quick Sort）

基本思想：

代码实现：

3.插入排序（Insertion Sort）

基本思想：

代码实现：

4.简单选择排序（Simple Selection Sort）

基本思想：

代码实现：

5.希尔排序（Shell Sort）

基本思想：

代码实现：

基本概要：

本文主要介绍五种简单常用的排序算法：冒泡排序，快速排序，插入排序，选择排序，希尔排序。包括它们的基本思想和代码实现。值得一说的是：插入排序，冒泡排序，选择排序平均情况下的时间复杂度为 $O\left ( n^{2} \right )$ ，因此在排序数据较少的情况下较好；而希尔排序和快速排序的平均时间复杂度为 $O\left ( nlogn \right )$ ，因此在排序数据较多的情况下较好，但是对于快速排序而言，数据基本有序时反而不好，接下来会详细阐述。（皆以从小到大的顺序排列）

1.冒泡排序（Bubble Sort）基本思想：

冒泡排序是一个非常好理解的排序，顾名思义——冒泡，此时将要排序的数据从上至下排列，从最上面的数（第一个数据）开始对相邻的两个数据进行比较，较小的数据往上浮，较大的数据往下沉，达到排序的效果。

（1）对每一对相邻的元素进行比较，若第一个比第二个大，则调换这两个元素的位置，依次两两比较直到数据的最后一对，此为一轮操作。

（2）重复n轮此操作（n为元素的个数），不过每轮结束后的最后一个元素不用参与下一轮的比较，因为经历一轮排序后，最后一个元素一定比前面所有的元素都要大。

（3）因此每一轮需要比较的元素都在减少，一直到没有数可比较为止。（不过为了减少比较次数，可以记录每轮是否有数据的交换，如果没有交换，表明当前数据已经按从小到大的顺序拍好了，可直接跳出循环）

代码实现： #include 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.将数据的中间元素设为基准值，初始化令 $i$ 指向最左边个元素，令 $j$ 指向最右边个元素，通过 $i++$ 从左往右找一个大于基准数的数，通过 $j--$ 从右往左找一个小于基准数的数，交换两数的位置，直到 $i=j$ 。

2.如此不断的细分递归，达到排序的目的

代码实现： #include void QuickSort(int a[], int begin, int end) { if (begin >= end) return; //一趟的实现 int key = a[begin]; int piti = begin; int left = begin; int right = end; while (left < right) { while (left < right && a[right] >= key) { right--; } a[piti] = a[right]; piti = right; while (left < right && a[left] 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 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）

希尔排序是插入排序的优化，它先将待排序列进行预排序，然后对次序列进行一次插入排序，不一样的是经过预处理之后的插入排序时间复杂度为 $O\left ( n \right )$

基本思想：

定义一个间隔gap，在一组数据中，将相隔为gap的元素作为一个组，对组内元素执行简单的插入排序，然后不断缩小gap重复此操作，完成数据的预处理，直到gap=1，表示对所有数进行插入排序，算法终止。

1.初始化 $gap=\frac{n}{2}$ （n为元素个数），将数据中所有距离为gap的元素分在一组（此时这组数据会被分成 $\frac{n}{2}$ 个组，每组有两个元素，对每个组进行排序）

2.接着缩小gap至 $\frac{n}{4}$ ，将数据中所有距离为gap的元素分在一组（此时这组数据会被分成 $\frac{n}{4}$ 个组，每组有四个元素，对每个组进行排序）

3.重复直到gap=1，此时数据为一组，有n个元素，简单插入排序即可。

代码实现： #include 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=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; }

小白文一篇

【本文地址】

C语言的5种简单排序算法

C语言的5种简单排序算法

今日新闻

推荐新闻