八大排序算法的C语言实现

博主：小蓝
发布时间：2025 年 03 月 04 日
237 次浏览
暂无评论
4197字数
分类： Linux 技术杂烩

排序算法是计算机科学中一个非常重要的基础内容，几乎每个编程语言都提供了内置的排序方法。今天，我们将深入分析并提供八种常见排序算法的C语言实现，并对每种算法进行详细解析。这些排序算法分别是：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、希尔排序和计数排序。

### 1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它通过重复地遍历待排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就交换它们。每一轮遍历后，最大的元素就像气泡一样“冒”到数列的末尾。

```c
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
```

**解释**：

* 外层循环控制遍历次数，每一轮遍历后，最小的元素就会“浮”到最前面。
* 内层循环进行相邻元素的比较与交换。

### 2. 选择排序（Selection Sort）

选择排序每次遍历未排序部分，选择最小的元素与当前部分的第一个元素交换，直到整个数组有序。

```c
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小值到前面
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
```

**解释**：

* 外层循环确定当前遍历的起始位置。
* 内层循环查找未排序部分中的最小元素并进行交换。

### 3. 插入排序（Insertion Sort）

插入排序将数组分为已排序和未排序两部分，逐个从未排序部分取出元素，并插入到已排序部分中合适的位置。

```c
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
```

**解释**：

* 外层循环逐步将未排序的元素插入到已排序部分。
* 内层循环在已排序部分查找插入的位置。

### 4. 快速排序（Quick Sort）

快速排序是一种分治法排序算法，通过一个“基准”元素将数组分成两部分，小于基准的元素放左边，大于基准的元素放右边，然后递归排序这两部分。

```c
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; 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);
    }
}
```

**解释**：

* `partition`函数用于将数组根据基准值分割成两部分。
* `quickSort`递归地对每一部分进行排序。

### 5. 归并排序（Merge Sort）

归并排序也是一种分治法的排序算法，它将数组分成两半，递归排序这两半，再将排序后的两部分合并成一个有序数组。

```c
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
```

**解释**：

* 将数组递归分为两部分，直至每部分只有一个元素。
* 然后通过 `merge`函数将已排序的子数组合并。

### 6. 堆排序（Heap Sort）

堆排序利用堆这种数据结构来排序数组。堆是一个完全二叉树，堆排序的核心在于构建最大堆和调整堆。

```c
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        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);
    }
}
```

**解释**：

* `heapify`函数用于维护堆的性质。
* `heapSort`将数组调整为堆，然后进行排序。

### 7. 希尔排序（Shell Sort）

希尔排序是插入排序的改进版，它通过一个步长序列来逐步减少元素间的间隔进行排序。

```c
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 = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}
```

**解释**：

* 通过不同的步长进行多轮插入排序，不断缩小步长，直至最后步长为1。

### 8. 计数排序（Counting Sort）

计数排序是一种非比较排序算法，它通过统计数组中每个元素出现的次数来确定其位置。

```c
void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i];

int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;

for (int i = 0; i < n; i++) count[arr[i]]++;

int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}
```

**解释**：

* 利用计数数组来记录每个元素的出现次数，然后根据次数填充原数组。

---

### 总结

每种排序算法都有其特点和适用场景。通过对比它们的时间复杂度、空间复杂度和实际应用中的表现，我们可以选择最适合的排序方法。在实际开发中，选择合适的排序算法能显著提高程序效率。

蓝易云是一家专注于香港及国内数据中心服务的提供商，提供高质量的服务器租用和云计算服务、包括免备案香港服务器、香港CN2、美国服务器、海外高防服务器、国内高防服务器、香港VPS等。致力于为用户提供稳定,快速的网络连接和优质的客户体验。

最后修改：2025 年 03 月 04 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

八大排序算法的C语言实现

小蓝 • 2025 年 03 月 04 日

### 1. 冒泡排序（Bubble Sort）

**解释**：

* 外层循环控制遍历次数，每一轮遍历后，最小的元素就会“浮”到最前面。
* 内层循环进行相邻元素的比较与交换。

### 2. 选择排序（Selection Sort）

选择排序每次遍历未排序部分，选择最小的元素与当前部分的第一个元素交换，直到整个数组有序。

**解释**：

* 外层循环确定当前遍历的起始位置。
* 内层循环查找未排序部分中的最小元素并进行交换。

### 3. 插入排序（Insertion Sort）

插入排序将数组分为已排序和未排序两部分，逐个从未排序部分取出元素，并插入到已排序部分中合适的位置。

**解释**：

* 外层循环逐步将未排序的元素插入到已排序部分。
* 内层循环在已排序部分查找插入的位置。

### 4. 快速排序（Quick Sort）

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);
    }
}
```

**解释**：

* `partition`函数用于将数组根据基准值分割成两部分。
* `quickSort`递归地对每一部分进行排序。

### 5. 归并排序（Merge Sort）

归并排序也是一种分治法的排序算法，它将数组分成两半，递归排序这两半，再将排序后的两部分合并成一个有序数组。

int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
```

**解释**：

* 将数组递归分为两部分，直至每部分只有一个元素。
* 然后通过 `merge`函数将已排序的子数组合并。

### 6. 堆排序（Heap Sort）

堆排序利用堆这种数据结构来排序数组。堆是一个完全二叉树，堆排序的核心在于构建最大堆和调整堆。

```c
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

**解释**：

* `heapify`函数用于维护堆的性质。
* `heapSort`将数组调整为堆，然后进行排序。

### 7. 希尔排序（Shell Sort）

希尔排序是插入排序的改进版，它通过一个步长序列来逐步减少元素间的间隔进行排序。

**解释**：

* 通过不同的步长进行多轮插入排序，不断缩小步长，直至最后步长为1。

### 8. 计数排序（Counting Sort）

计数排序是一种非比较排序算法，它通过统计数组中每个元素出现的次数来确定其位置。

```c
void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i];

int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;

for (int i = 0; i < n; i++) count[arr[i]]++;

int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}
```

**解释**：

* 利用计数数组来记录每个元素的出现次数，然后根据次数填充原数组。

---

### 总结

八大排序算法的C语言实现

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

微信视频号视频下载工具WeChatVideoDownloader

Win11系统优化工具-Windows11一键设置

YDArk - 系统内核工具

XPay-自建个人免签收款支付系统

Windows微软常用运行库合集一键安装

Flex 弹性布局与 Stack 叠层定位详解

SQL技能手册：实用查询指南

firewalld中ipset与zone的功能区别

高防cdn是什么意思

如何利用MySQL建立覆盖原表的索引优化查询性能

八大排序算法的C语言实现

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

八大排序算法的C语言实现

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款