C语言希尔排序(附带源码和解析)
希尔排序是一种高效的排序算法,由 Donald Shell 于 1959 年提出。这种算法是插入排序的一种更高效的改进版本。希尔排序的核心思想是将整个待排序的序列分割成若干子序列,然后分别进行直接插入排序,以此达到减少排序时间的目的。
希尔排序的基本原理
希尔排序的工作原理可以分为以下几个步骤:
- 选择一个增量序列 t1, t2, ..., tk,其中 ti > tj(i < j),tk = 1;
- 按增量序列个数 k,对序列进行 k 趟排序;
- 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。
希尔排序的关键在于增量序列的选择。常见的增量序列有希尔增量、Hibbard 增量、Sedgewick 增量等。在本文中,我们将使用希尔增量,即每次将增量缩小为原来的一半,直到增量为 1。
让我们通过一个具体的例子来理解希尔排序的工作过程。假设我们有以下待排序的数组:
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
我们选择初始增量为数组长度的一半,即 5。
第一趟排序(增量为 5):
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0] | | | 8 3 0 | | | 9 5 6 | | 1 4 | | 7 6 | 2 排序后:[3, 5, 1, 6, 2, 8, 9, 4, 7, 0]
第二趟排序(增量为 2):
[3, 5, 1, 6, 2, 8, 9, 4, 7, 0] | | | | | 3 5 1 6 2 | | | | | 5 1 6 2 0 排序后:[1, 2, 3, 4, 0, 5, 7, 6, 9, 8]
第三趟排序(增量为 1,即普通插入排序):
[1, 2, 3, 4, 0, 5, 7, 6, 9, 8] 排序后:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
C语言实现希尔排序
下面是希尔排序的 C 语言实现:
#include <stdio.h> void shellSort(int arr[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, n); shellSort(arr, n); printf("排序后数组: "); printArray(arr, n); return 0; }
运行结果:
原始数组: 8 9 1 7 2 3 5 4 6 0 排序后数组: 0 1 2 3 4 5 6 7 8 9
希尔排序的性能和优缺点
希尔排序的时间复杂度与增量序列的选择有关。在最坏情况下,希尔排序的时间复杂度为 O(n²),但在平均情况下,其时间复杂度为 O(n^1.3)。相比于简单插入排序的 O(n²),希尔排序在处理大规模数据时表现更为出色。
希尔排序的优点包括:
- 对于中等规模的数据,希尔排序的性能表现良好。
- 希尔排序是原地排序算法,不需要额外的存储空间。
- 对于部分有序的数组,希尔排序的效率较高。
希尔排序的缺点包括:
- 增量序列的选择对排序的性能影响较大,不同的增量序列可能导致不同的时间复杂度。
- 希尔排序不是稳定的排序算法,即相同键值的记录可能会在排序后改变其相对次序。
总结
希尔排序是一种高效的排序算法,它通过将待排序序列分割成若干子序列进行插入排序,从而提高了排序的效率。虽然其时间复杂度不如一些更先进的排序算法(如快速排序、归并排序),但在处理中等规模数据时,希尔排序仍然是一个不错的选择。
你可能还想关注其它 9 种排序算法:
- C语言冒泡排序(附带源码和解析)
- C语言快速排序(附带源码和解析)
- C语言选择排序(附带源码和解析)
- C语言插入排序(附带源码和解析)
- C语言归并排序(附带源码和解析)
- C语言堆排序(附带源码和解析)
- C语言计数排序(附带源码和解析)
- C语言桶排序(附带源码和解析)
- C语言基数排序(附带源码和解析)
声明:《算法系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。