C++与C语言的排序算法对比（插入，希尔，归并）
1. 引言
排序算法是计算机科学中的基础概念，广泛应用于数据处理和算法设计中。本文将通过插入排序、希尔排序、归并排序和选择排序这四种常见的排序算法，分别用C++和C语言实现，并对它们进行优劣对比，以帮助读者更好地理解这两种语言在实现算法时的差异。
2. 插入排序
插入排序是一种简单的排序算法，其基本思想是通过构建有序序列，将未排序的元素逐个插入到已排序的序列中。
C++实现
#include <iostream> using namespace std; 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; } } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }
C实现
#include <stdio.h> 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; } } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
对比分析
-
语言特性：C++使用
iostream库，提供了更高层次的输入输出方式（如cout），而C使用stdio.h库，依赖于printf函数。 -
可读性：C++代码看起来更简洁，而C语言的语法稍显繁琐。
-
性能：二者在时间复杂度上相同，均为O(n^2)，因此在性能上没有显著差异。
3. 希尔排序（动图点击）
希尔排序是插入排序的一种更高效的改进版本，通过对序列进行分组来提高效率。
C++实现
#include <iostream> using namespace std; 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; } } } int main() { int arr[] = {12, 34, 54, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); shellSort(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }
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; } } } int main() { int arr[] = {12, 34, 54, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); shellSort(arr, n); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; }
对比分析
-
性能：希尔排序的时间复杂度在O(n^(3/2))到O(n log n)之间，相较于插入排序更快，尤其是对于大规模数据。
-
可读性：C++和C的代码结构相似，但C++的类型和命名更易读。
-
灵活性：C++提供了更多的库支持，可能在大项目中更易于维护。
4. 归并排序（动图点击）
归并排序是一种有效的排序算法，它采用分治法，将大问题分解为小问题来解决。
C++实现
#include <iostream> using namespace std; void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int* L = new int[n1]; int* R = new int[n2]; for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } delete[] L; delete[] R; } void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, n - 1); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; }
C实现
#include <stdio.h> #include <stdlib.h> void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int* L = (int*)malloc(n1 * sizeof(int)); int* R = (int*)malloc(n2 * sizeof(int)); for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } free(L); free(R); } void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } int main() { int arr[] =
共勉 💪
同为未来的it人让我们在共同进步吧。
我很喜欢雷军的一段话：我们就悄悄的干，就算失败了咱也不丢人。