"C语言经典排序算法源码"
在IT领域，排序算法是基础且重要的知识，对于任何面试者来说，理解和掌握排序算法都是必不可少的技能。本文将介绍几种经典的排序算法的C语言实现，包括冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序以及二分插入排序。
1. 冒泡排序(Bubble Sort)
冒泡排序是一种简单的交换排序，通过重复遍历待排序的数组，比较相邻元素并根据需要交换它们的位置。冒泡排序的时间复杂度在最坏的情况下是O(n^2)，其中n是数组的长度。
```c
void BubbleSort(int v[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (v[j] > v[j + 1]) {
temp = v[j];
v[j] = v[j + 1];
v[j + 1] = temp;
}
}
}
}
```
2. 选择排序(Selection Sort)
选择排序通过每次从未排序的部分找到最小（或最大）的元素，放到已排序部分的末尾，直到全部待排序的数据元素排完。选择排序的时间复杂度也是O(n^2)。
```c
void SelectionSort(int v[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (v[j] < v[minIndex]) {
minIndex = j;
}
}
temp = v[i];
v[i] = v[minIndex];
v[minIndex] = temp;
}
}
```
3. 插入排序(Insertion Sort)
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在最好的情况下（即输入数组已经排序）达到线性时间复杂度O(n)。
```c
void InsertionSort(int input[], int len) {
int i, j, temp;
for (i = 1; i < len; i++) {
temp = input[i];
j = i - 1;
while (j >= 0 && input[j] > temp) {
input[j + 1] = input[j];
j--;
}
input[j + 1] = temp;
}
}
```
4. 希尔排序(Shell Sort)
希尔排序是插入排序的一种更高效的版本，通过将待排序的数组元素按某个增量分组，对每组使用直接插入排序算法排序，然后逐渐减少增量，直到增量为1，最后进行一次插入排序。
```c
void ShellSort(int v[], int n) {
int gap, i, j, temp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
for (j = i - gap; (j >= 0) && (v[j] > v[j + gap]); j -= gap) {
temp = v[j];
v[j] = v[j + gap];
v[j + gap] = temp;
}
}
}
}
```
5. 快速排序(Queue Sort)
快速排序是一种分治策略的排序算法，通过选取一个基准元素，将数组分为两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分再分别进行快速排序。
6. 堆排序(Heap Sort)
堆排序利用了堆这种数据结构，将待排序的数组构造成一个大顶堆或小顶堆，然后将堆顶元素与末尾元素交换，调整堆，重复这个过程直到所有元素都被排序。
7. 二分插入排序(Half Insertion Sort)
二分插入排序是插入排序的一个变种，它使用二分查找来确定插入位置，从而减少了比较次数，提高了效率。
```c
void HalfInsertSort(int a[], int len) {
int i, j, temp, low, high, mid;
for (i = 1; i < len; i++) {
temp = a[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] > temp) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (j = i - 1; j > high; j--) {
a[j + 1] = a[j];
}
a[high + 1] = temp;
}
}
```
这些排序算法各有优缺点，适用于不同的场景。理解并熟练掌握这些算法，对于解决实际问题和应对面试挑战都非常有帮助。
我的内容管理
展开
