C语言实现：冒泡、选择、快速排序法

"这篇资源包含了C语言实现的五种排序算法的源代码，适用于VC6.0编译环境。" 本文将详细介绍C语言中的五种排序算法：冒泡排序、选择排序、插入排序、快速排序以及希尔排序。这些排序算法是计算机科学中基础且重要的数据处理方法，广泛应用于各种编程场景。 ### 冒泡排序（Bubble Sort） 冒泡排序是最简单的排序算法之一，通过不断交换相邻两个元素的位置来达到排序目的。如果前一个元素比后一个元素大，则交换它们的位置。这个过程会重复n-1次（n为数组长度），每次遍历都会确保最大的元素“浮”到数组的末尾。冒泡排序的时间复杂度为O(n^2)。 ```c void Bubble(int*a, int n) { int i, j, temp; for (i = 0; i < n - 1; i++) for (j = i + 1; j < n; j++) if (a[i] > a[j]) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } ``` ### 选择排序（Choice Sort） 选择排序的工作原理是在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的时间复杂度同样为O(n^2)。 ```c void Choise(int*a, int n) { int i, j, k, temp; for (i = 0; i < n - 1; i++) { k = i; for (j = i + 1; j < n; j++) if (a[k] > a[j]) k = j; if (i != k) { temp = a[i]; a[i] = a[k]; a[k] = temp; } } } ``` ### 插入排序（Insertion Sort） 插入排序的工作方式类似于玩扑克牌，每次取出一张牌并插入到已排序的牌堆中的正确位置。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在最好情况（输入数组已经部分有序）下的时间复杂度为O(n)，最坏情况为O(n^2)。 ```c void Insert(int*a, int n) { int i, j, key; for (i = 1; i < n; i++) { key = a[i]; j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } ``` ### 快速排序（Quick Sort） 快速排序是一种高效的排序算法，采用了分治策略。它选取一个“基准”值，将数组分为两部分，一部分的所有元素都小于基准，另一部分的所有元素都大于基准，然后对这两部分再分别进行快速排序。快速排序的平均时间复杂度为O(n log n)，但在最坏情况下（输入数组已经部分有序）会退化为O(n^2)。 ```c void Quick(int*a, int i, int j) { int m, n, k, temp; m = i; n = j; k = a[(i + j) / 2]; do { while (a[m] < k && m < j) m++; // 找到大于k的元素 while (a[n] > k && n > i) n--; // 找到小于k的元素 if (m <= n) { temp = a[m]; a[m] = a[n]; a[n] = temp; m++; n--; } } while (m <= n); if (i < n) Quick(a, i, n); // 对左半部分递归排序 if (m < j) Quick(a, m, j); // 对右半部分递归排序 } ``` ### 希尔排序（Shell Sort） 希尔排序是插入排序的一种更高效的改进版本，通过比较相距一定间隔的元素来排序，随着间隔逐渐减小，最后进行一次普通的插入排序。希尔排序的时间复杂度一般认为介于O(n)和O(n^2)之间，取决于所选择的间隔序列。 由于希尔排序的实现较为复杂，这里不再给出具体代码，但它是基于插入排序的优化，通过增加元素间的比较距离来减少总的比较次数，从而提高效率。 以上就是C语言中常见的五种排序算法的介绍及其实现，每种算法都有其适用场景和优缺点，开发者可以根据实际需求选择合适的排序算法。