快速了解四种排序算法：希尔排序，堆排序，快速排序，冒泡排序（c语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了快速了解四种排序算法：希尔排序，堆排序，快速排序，冒泡排序（c语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一个程序员一生中可能会邂逅各种各样的算法，但总有那么几种，是作为一个程序员一定会遇见且大概率需要掌握的算法。

一：引言

1.1算法（algorithm ）

是指令的集合，是为解决特定问题而规定的一系列操作。它是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据集合作为输出。一个算法通常来说具有以下五个特性：

1. 输入：一个算法应以待解决的问题的信息作为输入。

2. 输出：输入对应指令集处理后得到的信息。

3. 可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。

4. 有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此整个算法也是在有限时间内可以结束的。

5. 确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。简单的说，算法就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是算法的逻辑形式，后者是算法的代码形式。

二：常见算法介绍

常见的排序算法，查找算法、图论算法和字符串算法等。

三：重点算法总结

今天我主要给大家介绍四种排序算法。如有错误。欢迎大家指正。

1.快速排序代码

这是一个经典的快速排序算法的实现。快速排序是一种高效的排序算法，通过选择一个基准值（pivot），将数组划分为两个子数组，并对子数组进行递归排序，最终将整个数组排序。

函数 quickSort 接受一个整型数组 arr、左边界 left 和右边界 right 作为参数。如果左边界大于等于右边界，则表示数组已经有序，直接返回。接下来，选择数组最左边的元素作为基准值 pivot。定义两个指针 i 和 j，分别从基准值的右边和左边开始搜索。在循环中，指针 i 从左向右搜索，找到第一个大于等于基准值的元素；指针 j 从右向左搜索，找到第一个小于等于基准值的元素。如果指针 i 小于等于指针 j，则交换它们所指向的元素，并且同时将指针 i 向后移动一位，指针 j 向前移动一位。循环结束后，将基准值与指针 j 所指向的元素交换位置，将基准值放置在正确的位置上。然后，对基准值左边的子数组和右边的子数组分别进行递归排序，即调用 quickSort 函数。这样，整个数组就会在递归过程中不断被划分和排序，最终实现排序的目的。快速排序时间复杂度：快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。。在平均情况下，快速排序的运行时间为O(nlogn)。

2.堆排序代码

void heapify(int arr[], int n, int i) { ... }：定义了一个函数 heapify，用于维护以 arr[i] 为根节点的子树成为一个最大堆。

int largest = i;：初始化一个变量 largest，表示当前子树的根节点。

int l = 2 * i + 1;：计算左子节点的索引。

int r = 2 * i + 2;：计算右子节点的索引。

if (l < n && arr[l] > arr[largest]) largest = l;：如果左子节点存在且大于当前最大值，则更新最大值的索引。

if (r < n && arr[r] > arr[largest]) largest = r;：如果右子节点存在且大于当前最大值，则更新最大值的索引。

if (largest != i) { ... }：如果最大值的索引发生了改变，则交换当前节点和最大值节点的值，并递归调用 heapify 函数以继续维护子树的最大堆性质。

void heapSort(int arr[], int n) { ... }：定义了一个函数 heapSort，用于对数组进行堆排序。

for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);：首先构建一个最大堆，从最后一个非叶子节点开始向上对每个子树进行 heapify 操作。

for (int i = n - 1; i >= 0; i--) { ... }：开始排序过程，将根节点（最大值）与数组末尾元素交换，然后对剩余的前缀数组进行 heapify 操作。

swap(arr[0], arr[i]);：交换数组的第一个元素和当前待排序部分的最后一个元素。

heapify(arr, i, 0);：对调整后的堆进行 heapify 操作，以继续维护最大堆性质。

堆排序时间复杂度为 O(log n)。

什么是堆呢？

堆其实就是一种特殊的队列——优先队列。

普通的队列游戏规则很简单：就是先进先出；但这种优先队列搞特殊，不是按照进队列的时间顺序，而是按照每个元素的优先级来比拼，优先级高的在堆顶。

3.希尔排序代码

void shellSort(int arr[], int n) { ... }：定义了一个函数 shellSort，用于对数组进行希尔排序。
for (int gap = n / 2; gap > 0; gap /= 2) { ... }：这个循环用于控制增量序列，初始化增量为数组长度的一半，每次循环结束将增量减半。
for (int i = gap; i < n; i++) { ... }：这个循环用于遍历待排序的数组，从增量 gap 开始，每次递增一个增量。
int temp = arr[i];：将当前位置的元素存储到临时变量 temp 中，以便后续移动元素。
int j;：声明一个变量 j，用于在内层循环中寻找插入位置。
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)：这个循环用于在已排序部分中找到合适的位置来插入当前元素 temp。条件 j >= gap 确保不越界，同时判断 arr[j - gap] > temp 表示找到合适位置。
arr[j] = arr[j - gap];：将元素向右移动，为待插入元素腾出位置。
arr[j] = temp;：将待插入元素插入到合适的位置。
希尔排序时间复杂度为O(n^1.5)