排序，说白了就是让一堆数据按从小到大或者按从大到小的顺序排好队。

从小到大的顺序，叫升序。

从大到小的顺序，叫降序。

排序的方法有很多，各有各的绝活，以下这10个排序算法是公认比较有名的：

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。

这些排序算法，有的适合人多的场合，有的干小活儿利索。

咱们一个一个来看。

以下我将从算法的核心思想、逻辑思路和特点这3个方面来讲解，如何用C语言实现它们将在下一篇文章中介绍。

以西用我们习惯的从小到大的顺序排列来讲。

1. 冒泡排序 (Bubble Sort)

核心思想：像水底的气泡一样，小的数会慢慢“冒”到最前面。

逻辑思路：

从第一个数开始，和它右边邻居比大小，如果它比邻居大，就交换位置。然后比较第二和第三个数，一直比到最后一对。这样一趟下来，最大的数就像石头一样“沉”到了最底部。

然后忽略最后那个最大的数，对前面的数重复这个过程，直到所有数都排好。

特点：最简单，但效率也最低，就像一遍遍点名排队，稍微人多点就慢得急死人。

2. 选择排序 (Selection Sort)

核心思想：就像搞“人才选拔”，每次从乱序区挑最小的，放到已排序区的最前。（也可以反过来，每次选最大的，放在最后。）

逻辑思路：

假设左边是排好队的（开始为空），右边是乱糟糟的。我们就在右边这一堆里，从头到尾扫一遍，找出最小的那个。然后把这个最小的和乱糟糟这堆里的第一个数交换位置。这下，排好队的就多了一个。

重复这个过程，每次都在剩下的乱序里找最小的，放到有序区的末尾，直到所有人都被“选拔”完。

特点：比冒泡稍微好一点，但本质上还是慢，不管数据咋样，它都得老老实实从头到尾找一遍。

3. 插入排序 (Insertion Sort)

核心思想：就像我们打扑克牌时一张张理牌，把新摸的牌插到手上已排好序的牌里合适的位置。

逻辑思路：

默认第一个数已经是拿在手里的牌（有序的）。从第二个数（新摸的牌）开始，把它抽出来，然后和前面已经排好序的牌从后往前比较。如果前面的牌比它大，就把前面的牌往后挪一个位置，给它腾地儿。直到找到一个比它小的牌，就插在这个牌的后面。

重复这个过程，直到所有新牌都插入到位。

特点：对于小规模或者基本有序的数据，效率非常高，非常“智能”。但大数据量下就比较慢了。

4. 希尔排序 (Shell‘s Sort)

核心思想：插入排序的升级版，也叫“缩小增量排序”。它认为插入排序每次只挪动一位太慢了，于是先“分组跳着排”，让数据基本有序，最后再来一次标准的插入排序。

逻辑思路：

先选一个间隔（比如总数的一半），把所有间隔为这个数的数据分成一组，在组内进行插入排序。然后缩小间隔（比如减半），再分组排序。直到间隔缩小到1，此时就是一次标准的插入排序，因为数据已经基本有序了，所以这次排序会非常快。

特点：突破了O(n²)的瓶颈，是第一种高效率的排序算法。

5. 归并排序 (Merge Sort)

核心思想：分而治之。大事化小，小事化了。先把大队伍拆成两个小分队，分别把两个小分队排好序，然后再把两个有序的小分队合并成一个大的有序队伍。

逻辑思路：

递归地把数组对半拆开，直到每个小数组只剩一个元素（一个元素自然就是有序的）。然后开始“合并”：创建一个新数组，比较两个小数组的头一个元素，谁小就先把它放到新数组里，然后指针后移。这样一直比下去，直到两个小数组的元素都放到了新的大数组里。

特点：速度非常稳定，永远都是O(n log n)，缺点是需要额外一块内存空间来合并。

6. 快速排序 (Quick Sort)

核心思想：也是分而治之，但它是“挖坑填数”。选一个“基准值”，然后把队伍分成“比基准小的”和“比基准大的”两拨，基准值就在它最终该在的位置上了。再递归地去排那两拨。

逻辑思路：

从数组中挑一个元素（比如第一个或中间那个），称为“基准”。

重新排序，所有比基准小的都扔到它左边，所有比基准大的都扔到它右边。这个操作叫“分区”。

递归地把左边子数组和右边子数组重复前两步。

特点：平均速度是所有排序里最快的，因此叫“快速”排序。但如果基准值选得不好（比如每次都是最大或最小），效率会退化成冒泡排序。

7. 堆排序 (Heap Sort)

核心思想：利用“堆”这种数据结构（一种特殊的完全二叉树）来排序。每次都把最大（或最小）的元素从堆顶取走，剩下的调整好再取，直到取完。

逻辑思路：

把无序数组构建成一个大顶堆（父节点总是大于子节点），此时堆顶就是全局最大的数。

把堆顶的数（最大数）和数组末尾的数交换。此时最大数就归位到了最后。

忽略最后那个已归位的数，把剩下的数组重新调整成一个大顶堆。新的堆顶又是剩余数里最大的。

重复第2、3步，直到堆里只剩一个数。

特点：效率很高，而且不需要额外的空间，是一种非常优秀的排序算法。

8. 计数排序 (Counting Sort)

核心思想：不比较元素的大小，而是统计每个数出现了多少次。好比投票唱票，数一下有多少张票投给了“1号”，多少张投给了“2号”。

逻辑思路：

找出待排序数组中的最大值max，创建一个长度为max+1的计数数组，初始值全为0。

遍历数组，统计每个元素出现的次数，存入计数数组对应的下标位置（例如，数字3出现了5次，则count[3]=5）。

遍历计数数组，根据每个下标值的出现次数，依次把数字放回原数组。

特点：速度超级快，但只能用于整数排序，而且如果数据范围（max-min）很大，会非常耗内存。

9. 桶排序 (Bucket Sort)

核心思想：数据分桶，桶内排序。想象一下，先把数据按范围分到几个有序的桶里（比如1-10一桶，11-20一桶），然后对每个不是空的桶进行排序（可以用其他排序算法），最后按顺序把每个桶里的数据接起来。

逻辑思路：

设置一个定量的数组当作空桶。

遍历数据，把每个数据放到对应的桶里。

对每个非空的桶进行排序。

从不是空的桶里把排好序的数据拼接起来。

特点：是计数排序的升级版，适合数据分布均匀的场景，可以大大减少排序的规模。

10. 基数排序 (Radix Sort)

核心思想：按位排序，从低位到高位。不管数字多大，我们先比个位，再比十位，再比百位...

逻辑思路：

取得数组中的最大数，并取得其位数（即最大数是几位数）。

从最低位（个位）开始，根据该位上的数字，用稳定的排序算法（通常是计数排序）将数组排序一次。

接着依据十位数字排序，然后是百位...直到最高位。

排序完毕后，数组就变成一个有序序列。

特点：速度很快，也只能用于整数排序，可以看作是多次的、按位的桶排序。

总结

这十大算法可以分个类：

简单但慢：冒泡、选择、插入。入门必备，实战少用。

高效通用：快排、归并、堆排。面试必考，实战常用。其中快排综合性最强，归并稳定，堆排最省空间。

非比较型：计数、桶、基数。特点鲜明，用在特定场景下是“大杀器”。

希望这么一讲，能让你对排序算法的内在逻辑有个清晰的认识！下次再看到它们，就不会觉得是冷冰冰的代码了。

C语言入门 · 目录

上一篇C语言入门：易经八卦，今天来做一个好玩的程序

阅读 102

​