排序算法全解析：选择、冒泡、快速等9大经典算法实现

"本文档提供了一组经典的排序算法实现，包括选择排序、冒泡排序、快速排序、插入排序、希尔排序、归并排序、基数排序、计数排序以及小根堆排序。这些算法是数据结构与算法学习中的基础内容，对于理解和优化程序性能至关重要。" ### 1. 选择排序 (Selection Sort) 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序的主要步骤如下： - 遍历数组，找到最小值的位置。 - 将最小值与数组的第一个元素交换位置。 - 继续遍历剩余部分，找到剩余部分的最小值，与第二个位置的元素交换。 - 重复此过程，每次比较范围缩小一位，直至整个数组有序。 ### 2. 冒泡排序 (Bubble Sort) 冒泡排序也是一种简单的排序算法，通过重复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经过交换慢慢“浮”到数列的顶端。 - 从第一个元素开始，比较相邻的元素，如果前一个比后一个大，则交换它们的位置。 - 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 - 针对所有的元素重复以上的步骤，除了最后一个。 - 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 ### 3. 快速排序 (Quick Sort) 快速排序是由C.A.R. Hoare在1960年提出的一种排序算法。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。 - 选择一个基准元素 pivot。 - 将所有小于基准的元素移到其左边，大于基准的元素移到其右边，这一步称为分区操作。 - 分别对左右两边的子序列进行递归的快速排序。 ### 4. 插入排序 (Insertion Sort) 插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 ### 5. 希尔排序 (Shell Sort) 希尔排序是插入排序的一种更高效的改进版本。它通过设定一个间隔序列，将待排序的元素按照间隔进行分组，然后对每组进行插入排序。随着间隔逐渐减小，最后间隔为1时，整个序列变为有序。 ### 6. 归并排序 (Merge Sort) 归并排序是一种采用分治法的排序算法。它将待排序的序列分成若干个子序列，每个子序列是有序的，然后再将有序的子序列合并成完整的有序序列。 - 将序列一分为二，直到每个子序列只有一个元素。 - 合并子序列，通过比较元素的大小，将两个有序子序列合并为一个有序序列。 ### 7. 基数排序 (Radix Sort) 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。它不是基于比较的排序算法，而是通过分配和收集过程实现的。 ### 8. 计数排序 (Counting Sort) 计数排序是一种非基于比较的排序算法，适用于待排序的元素是有限的非负整数的情况。它通过统计每个元素出现的次数，然后根据统计结果直接确定每个元素在输出序列中的位置。 ### 9. 小根堆排序 (Heap Sort) 堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 以上就是九种经典的排序算法，每一种都有其适用场景和优缺点。理解并掌握这些排序算法，有助于提升编程能力，优化算法效率。