一：冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换的元素，也就是说该数列已经排序完成。
冒泡排序的步骤如下：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的算法复杂度通常是 O(n^2)，其中 n 是数列中元素的数量。这意味着当数列的长度增加时，排序所需的时间会成倍增加。
#include <stdio.h> void bubbleSort(int arr[], int n) { int i, j, temp; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 190 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
运行结果：
二：选择排序 (Selection Sort)
选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序的步骤如下：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
选择排序算法的特点是：
- 它不受输入数据的影响，无论什么数据，所需的排序时间都是相同的。
- 它不是一种稳定的排序算法，因为相同元素的顺序可能会被改变。
- 它的空间复杂度为 O(1)，因为它只需要一个额外的存储空间来交换元素。
- 它的平均时间复杂度和最坏时间复杂度都是 O(n^2)，其中 n 是数列中元素的数量。
#include <stdio.h> void selectionSort(int arr[], int n) { int i, j, min_idx, temp; for (i = 0; i < n - 1; i++) { min_idx = i; for (j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } int main() { int arr[] = { 19, 52, 42, 2, 77, 31 }; int n = sizeof(arr) / sizeof(arr[0]); selectionSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
运行结果：
三：插入排序 (Insertion Sort)
插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place（即在原始数组上进行操作）排序，这意味着它不需要额外的存储空间。
插入排序的步骤如下：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
插入排序是稳定的排序算法，因为它不会改变相同元素之间的顺序。
插入排序的时间复杂度：
- 最好情况：当输入数组已经是有序的，时间复杂度是 O(n)。
- 最坏情况：当输入数组是逆序的，时间复杂度是 O(n^2)。
- 平均情况：时间复杂度是 O(n^2)。
插入排序的空间复杂度是 O(1)，因为它只需要一个额外的存储空间。
#include <stdio.h> void insertionSort(int arr[], int n) { int i, key, j, temp; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } int main() { int arr[] = { 38, 27, 43, 3, 9, 82 }; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
运行结果：
四：希尔排序 (Shell Sort)
希尔排序（Shell Sort）是插入排序的一种更高效的改进版本。它是由Donald Shell于1959年提出的。希尔排序通过将原始数据集分割成若干子序列，分别对这些子序列进行插入排序，然后再逐渐减少子序列的间隔，继续进行排序，直至整个数据集的间隔为1。
希尔排序的关键思想是将原始数据集分成多个子序列，每个子序列的元素之间存在一定的间隔。初始时，间隔可以是数据集大小的一半或者某个特定的序列（如希尔增量序列）。然后，对每个子序列进行插入排序。随着算法的进行，间隔逐渐减小，直到间隔为1，此时整个数据集作为一个子序列进行插入排序。
希尔排序的步骤如下：
- 选择一个增量序列，例如初始增量为 n/2，然后依次减半。
- 按照增量分组，对每组使用插入排序算法排序。
- 逐步减少增量，重复步骤2，直到增量减少到1，完成整个数据集的排序。
希尔排序的时间复杂度：
- 最好情况：当增量序列选择得当时，时间复杂度可以达到 O(n log n)。
- 平均情况：时间复杂度通常在 O(n (log n)^2) 到 O(n^(3/2)) 之间，具体取决于增量序列的选择。
- 最坏情况：时间复杂度是 O(n^2)。
希尔排序的空间复杂度是 O(1)，因为它是原地排序算法。
#include <stdio.h> void shellSort(int arr[], int n) { int i, j, gap, temp; gap = n / 2; while (gap > 0) { for (i = gap; i < n; i++) { temp = arr[i]; j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = temp; } gap = gap / 2; } } int main() { int arr[] = { 8, 3, 2, 7, 4, 6, 5 }; int n = sizeof(arr) / sizeof(arr[0]); shellSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
运行结果：
五：并归排序 (Merge Sort)
并归排序（Merge Sort）是一种分治算法，由约翰·冯·诺伊曼在1945年发明。它采用分治法（Divide and Conquer）的策略来把数据结构分为更小的子问题来解决，然后将子问题的解合并以解决原来的问题。
并归排序的基本思想是：
- 分解：将数组递归地分成两半，直到每个子数组只包含一个元素。
- 解决：由于每个子数组只有一个元素，它们自然就是有序的。
- 合并：将有序的子数组合并成更大的有序数组。
并归排序的步骤如下：
- 如果数组只有一个元素或者为空，它已经是有序的，直接返回。
- 将数组分成两个子数组，每个子数组包含原数组一半的元素。
- 对两个子数组分别进行归并排序。
- 将排序后的两个子数组合并成一个有序数组。
并归排序的时间复杂度：
- 最好、最坏和平均情况的时间复杂度都是 O(n log n)，其中 n 是数组中元素的数量。
并归排序的空间复杂度：
- 由于需要额外的空间来存储子数组和合并后的数组，空间复杂度为 O(n)。
#include <stdio.h> #include <stdlib.h> // 合并两个有序子数组为一个有序数组 void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; // 左子数组的元素个数 int n2 = right - mid; // 右子数组的元素个数 // 创建临时数组来存储两个子数组的元素 int* leftArr = (int*)malloc(n1 * sizeof(int)); int* rightArr = (int*)malloc(n2 * sizeof(int)); // 将元素复制到临时数组中 for (int i = 0; i < n1; i++) { leftArr[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { rightArr[j] = arr[mid + 1 + j]; } // 合并两个子数组为一个有序数组 int i = 0; // 左子数组的索引 int j = 0; // 右子数组的索引 int k = left; // 合并后数组的索引 while (i < n1 && j < n2) { if (leftArr[i] <= rightArr[j]) { arr[k] = leftArr[i]; i++; } else { arr[k] = rightArr[j]; j++; } k++; } // 将剩余的元素放入合并后的数组中 while (i < n1) { arr[k] = leftArr[i]; i++; k++; } while (j < n2) { arr[k] = rightArr[j]; j++; k++; } // 释放临时数组的内存 free(leftArr); free(rightArr); } // 归并排序递归函数 void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // 计算中间索引 // 递归地对左右子数组进行排序 mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // 合并两个有序子数组 merge(arr, left, mid, right); } } // 案例用法 int main() { int arr[] = { 51, 12, 18, 11, 31 ,4,76,45,90}; int n = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, n - 1); printf("Sorted array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
运行结果：
六：快速排序 (Quick Sort)
快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它同样采用分治法（Divide and Conquer）的策略，但与归并排序不同，快速排序在平均和最好情况下的时间复杂度为 O(n log n)，且它是一种原地排序算法，空间复杂度为 O(log n)。
快速排序的基本思想是：
- 选择基准：从数组中选择一个元素作为基准（pivot）。
- 分解：重新排列数组，所有比基准小的元素放在基准的左边，所有比基准大的元素放在基准的右边。
- 递归：递归地将上述两个子数组排序。
快速排序的步骤如下：
- 选择一个基准元素，可以是数组的第一个元素、最后一个元素、中间元素或随机元素。
- 将数组分为两部分，左边部分包含所有小于基准的元素，右边部分包含所有大于基准的元素。
- 对基准左边和右边的子数组递归地执行快速排序。
- 当子数组的大小减小到1或0时，递归结束。
快速排序的时间复杂度：
- 最好和平均情况：O(n log n)
- 最坏情况：O(n^2)，当每次都选择到最大或最小元素作为基准时（例如，数组已经完全排序或逆序）。
快速排序的空间复杂度：
- 平均情况下：O(log n)，因为递归栈的深度是 log n。
- 最坏情况下：O(n)，当递归深度为 n 时。
#include <stdio.h> int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int arr[] = { 102, 37, 86, 19, 1, 51 }; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
运行结果：
七：堆排序 (Heap Sort)
堆排序（Heap Sort）是一种基于比较的排序算法，它利用了二叉堆（Binary Heap）数据结构的特性来实现排序。堆排序可以被认为是一种改进的归并排序，因为它也分为分解和合并两个阶段，但它不需要额外的存储空间来创建子数组。
堆排序的基本思想是：
- 构建最大堆：将待排序的数组转换成最大堆，即父节点的值总是大于或等于其子节点的值。
- 交换和调整：将堆顶元素（最大值）与最后一个元素交换，缩小堆的范围，然后调整堆，以保持最大堆的性质。
- 重复：重复步骤2，直到堆的大小减少到1。
堆排序的步骤如下：
- 将无序序列构建成一个最大堆。
- 将堆顶元素（最大值）与最后一个元素交换，缩小堆的范围，剩余元素重新调整为最大堆。
- 重复步骤2，直到堆的大小为1。
堆排序的时间复杂度：
- 最好、最坏和平均情况的时间复杂度都是 O(n log n)。
堆排序的空间复杂度：
- 由于是原地排序，空间复杂度为 O(1)。
#include <stdio.h> void heapify(int arr[], int n, int i) { int largest = i; 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) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); heapSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
运行结果：
八：计数排序 (Counting Sort)
计数排序（Counting Sort）是一种非比较型排序算法，它通过使用一个额外的数组（计数数组）来统计输入数组中每个元素出现的次数，然后根据这些计数来确定每个元素在输出数组中的位置。
计数排序的基本思想是：
- 统计计数：遍历输入数组，对于每个元素，增加计数数组中对应元素的计数。
- 计算累积计数：将计数数组中的每个计数转换为累积计数，累积计数表示每个元素及其之前所有元素的总数。
- 构建输出数组：从输入数组的最后一个元素开始，根据元素的值在计数数组中查找其累积计数，这将告诉我们该元素在输出数组中的位置。将元素放置在正确的位置，并将计数数组中相应元素的计数减少。
计数排序的步骤如下：
- 找到输入数组中的最大值和最小值，以确定计数数组的大小。
- 创建一个计数数组，长度为最大值与最小值之差加1，并初始化所有元素为0。
- 遍历输入数组，对于每个元素，增加计数数组中相应位置的计数。
- 将计数数组中的每个计数转换为累积计数。
- 创建输出数组，长度与输入数组相同。
- 从输入数组的最后一个元素开始，根据元素的值，在计数数组中找到其累积计数，这将告诉我们该元素在输出数组中的位置。将元素放置在正确的位置，并将计数数组中相应元素的计数减少。
计数排序的时间复杂度：
- 最好、最坏和平均情况的时间复杂度都是 O(n + k)，其中 n 是输入数组的大小，k 是整数的范围。
计数排序的空间复杂度：
- 空间复杂度是 O(k)，其中 k 是整数的范围。
#include <stdio.h> #include <stdlib.h> void countingSort(int arr[], int n) { // 找到最大值和最小值 int max = arr[0], min = arr[0]; for (int i = 1; i < n; ++i) { if (arr[i] > max) { max = arr[i]; } if (arr[i] < min) { min = arr[i]; } } // 计算计数数组的长度 int range = max - min + 1; // 创建并初始化计数数组 int* count = (int*)malloc(range * sizeof(int)); for (int i = 0; i < range; ++i) { count[i] = 0; } // 统计每个元素出现的次数 for (int i = 0; i < n; ++i) { count[arr[i] - min]++; } // 还原排序后的数组 int index = 0; for (int i = 0; i < range; ++i) { while (count[i] > 0) { arr[index++] = i + min; count[i]--; } } // 释放动态分配的内存 free(count); } // 测试函数 int main() { int arr[] = { 4, 2, 7, 1, 5, 2 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); countingSort(arr, n); printf("Sorted array: "); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); return 0; }
运行结果：
数据结构是计算机科学中存储、组织数据的方式，它不仅影响数据的存储效率，也影响对数据的操作效率。排序算法是数据结构中非常重要的一部分，用于将一系列元素按照特定的顺序重新排列。
1. 冒泡排序（Bubble Sort）
- 基于重复遍历要排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。
2. 选择排序（Selection Sort）
- 通过重复地在未排序序列中找到最小（或最大）元素，并将其放置在排序序列的开头。
3. 插入排序（Insertion Sort）
- 通过构建有序序列，对未排序数据从后向前扫描，找到相应位置并插入。
4. 希尔排序（Shell Sort）
- 是插入排序的一种更高效的改进版本，通过将原始数据集分割成若干子序列，分别对这些子序列进行插入排序。
5. 归并排序（Merge Sort）
- 使用分治法的一个非常高效的排序算法，将已排序的子序列合并为有序序列。
6. 快速排序（Quick Sort）
- 通过选取一个“基准”元素，并将数列分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
7. 堆排序（Heap Sort）
- 利用堆这种数据结构所设计的一种排序算法，通过构建最大堆或最小堆来实现排序。
8. 计数排序（Counting Sort）
- 非基于比较的排序算法，适用于一定范围内的整数排序，通过统计每个数字出现的次数来排序。
这些排序算法可以根据不同的标准进行分类：
- 按时间复杂度分类：
- 平方级复杂度：冒泡排序、选择排序、插入排序、希尔排序（最坏情况）。
- 线性对数级复杂度：归并排序、快速排序、堆排序。
- 线性级复杂度：计数排序（当数据范围不大时）。
- 按空间复杂度分类：
- 原地排序（空间复杂度为 O(1)）：冒泡排序、选择排序、插入排序、希尔排序、快速排序。
- 非原地排序（需要额外空间）：归并排序（需要 O(n) 的额外空间）、计数排序（需要 O(k) 的额外空间，k 是数据范围）。
- 按稳定性分类：
- 稳定的排序算法：冒泡排序、插入排序、希尔排序、归并排序。
- 不稳定的排序算法：选择排序、快速排序、堆排序、计数排序。
- 按是否基于比较分类：
- 基于比较的排序算法：冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序。
- 非基于比较的排序算法：计数排序（当数据范围已知时）、桶排序、基数排序。
每种排序算法都有其适用场景和优缺点，选择合适的排序算法需要根据实际问题的特点来决定。
