C语言程序设计十大排序—希尔排序

1.概念✅

  排序是数据处理的基本操作之一，每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法，排序后的数据更易于处理和查找。在计算机发展的历程中，在排序算法的研究一直深受人们重视，出现了很多算法，在思路、效率、应用等方面各有特色。通过学习排序算法，读者可以理解不同算法的优势和局限性，并根据具体情况选择最合适的算法，以提高程序的性能和效率。学习排序算法还有助于培养逻辑思维和问题解决能力，在解决其他类型的问题时也能够应用到类似的思维方法。

2.希尔排序🎈

  希尔排序（Shell Sort）是一种基于插入排序的排序算法，可以看作是插入排序的改进版。它通过将数组分成若干个子数组（每个子数组中的元素间隔为一个增量 gap）来进行分组排序，逐步缩小这个增量，最后当增量为 1 时，变成普通的插入排序。

  以a[]={12, 54, 34, 2, 3，8} 中的6个数，从小到大排序为例说明希尔排序的步骤：
 （1）gap = 6/2 = 3，对间距为3的数排序。共3组数的间距为3，这四组数分别是{12 ，2}、{34, 3}、{54, 8}。分别在这3组数内部做插入排序。例如{12,2}做插入排序的结果是{34,3}。在这一轮，每组内的数做插入排序时都要进入代码执行交换操作，共执行3次。经过这一轮操作，较大的数挪到了右边，更靠近它们排序后的终止位置。如下图：

 （2）gap =3/2 = 1，对间距为1的数排序，实际上gap=1的希尔排序就是基本的插入排序。不懂的看这篇文章 <插入排序>

---

假如说:a[]={12, 54, 34, 2, 3，8} 有8个数

 当gap = 4/2 = 2，对间距为2的数排序。共有2组数的间距为2，分别是{2, 8, 34, 0}、{3, 12, 34, 0}。分别做插入排序，如下图：

3.代码实现✅

3.1 直接写✨

#include <stdio.h>int main() {int arr[] = {12, 11, 13, 5, 6,8}; // 原始数组int n = sizeof(arr) / sizeof(arr[0]); // 数组大小int i; // 插入排序实现for ( i = 1; i < n; i++) {int key = arr[i];  // 当前待插入的元素int j = i - 1;// 将大于key的元素移到右侧while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 插入当前元素到正确的位置arr[j + 1] = key;}// 打印排序后的数组printf("排序过后的数组: \n");for ( i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

3.2 函数✨

#include <stdio.h>// 希尔排序函数
void shellSort(int arr[], int n) {int gap,i;// 确定初始增量for ( gap = n / 2; gap > 0; gap /= 2) {// 从gap开始，进行插入排序for ( i = gap; i < n; i++) {int temp = arr[i];  // 当前待排序的元素int j;// 移动大于temp的元素到gap位置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) {int i;for ( i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 34, 54, 2, 3,8}; // 原始数组int n = sizeof(arr) / sizeof(arr[0]); // 数组大小shellSort(arr, n); // 调用希尔排序函数printf("排序过后的数组: \n");printArray(arr, n); // 打印排序后的数组return 0;
}

4.总结✅

  希尔排序在多大程度上改善了插入排序？可以直接对比两个代码的计算量，感兴趣的小伙伴自己思考一下。
  根据严格的算法分析，希尔排序的计算复杂度约为O(n^1.5)，当n=10^5时，计算量约为3000万次，远小于O(n^2)的100亿次。
  最后概括希尔排序的思路。希尔排序是一种基于插入排序的排序算法，它将一个序列分成若干个子序列，对每个子序列使用插入排序，然后在对整个序列使用一次插入排序。shellSort()函数使用gap对数组进行分组，然后对每个子序列使用插入排序，最后将整个序列使用插入排序，在插入排序过程中，每次将元素插到已经排好序的序列中，而这个已经排好序的序列是由前面的插入排序操作得到的，每次操作都相当于将元素插到一个较小的序列中，因此可以更快地将元素插到正确的位置。

Perspective-takling