C语言排序算法详解：冒泡、选择、插入、快速排序等

C语言排序算法详解

在C语言中，排序算法是数据结构与算法学习的核心内容之一。本文将介绍几种常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序以及归并排序，并提供相应的代码示例，帮助您理解和掌握这些算法。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历待排序的数组，比较相邻的两个元素，如果它们的顺序错误就交换它们，直到没有需要交换的元素为止。

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]) { 
        // 交换arr[j]和arr[j + 1] 
        int temp = arr[j]; 
        arr[j] = arr[j + 1]; 
        arr[j + 1] = temp; 
      } 
    } 
  } 
}

2. 选择排序

选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

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; 
      } 
    } 
    // 交换arr[minIndex]和arr[i] 
    int temp = arr[minIndex]; 
    arr[minIndex] = arr[i]; 
    arr[i] = temp; 
  } 
}

3. 插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

void insertionSort(int arr[], int n) { 
  int i, key, j; 
  for (i = 1; i < n; i++) { 
    key = arr[i]; 
    j = i - 1; 

    /* 将大于key的元素向后移动一位 */ 
    while (j >= 0 && arr[j] > key) { 
      arr[j + 1] = arr[j]; 
      j = j - 1; 
    } 
    arr[j + 1] = key; 
  } 
}

4. 快速排序

快速排序是一种高效的排序算法，其基本思想是选择一个基准元素，将数组分成两个子数组，一个子数组中的所有元素都小于基准元素，另一个子数组中的所有元素都大于基准元素，然后递归地对两个子数组进行排序。

int partition(int arr[], int low, int high) { 
  int pivot = arr[high]; 
  int i = (low - 1); 

  for (int j = low; j <= high - 1; j++) { 
    if (arr[j] < pivot) { 
      i++; 
      // 交换arr[i]和arr[j] 
      int temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
    } 
  } 
  // 交换arr[i + 1]和arr[high]（或pivot） 
  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) { 
    /* pi是分区索引，arr[pi]现在位于正确的位置 */ 
    int pi = partition(arr, low, high); 

    // 分别对左右子数组进行排序 
    quickSort(arr, low, pi - 1); 
    quickSort(arr, pi + 1, high); 
  } 
}

5. 归并排序

归并排序是一种基于分治法的排序算法。其基本思想是将待排序的数组分成两个子数组，分别对这两个子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。

void merge(int arr[], int l, int m, int r) { 
  int i, j, k; 
  int n1 = m - l + 1; 
  int n2 = r - m; 

  /* 创建临时数组 */ 
  int L[n1], R[n2]; 

  /* 将数据复制到临时数组L[]和R[] */ 
  for (i = 0; i < n1; i++) 
    L[i] = arr[l + i]; 
  for (j = 0; j < n2; j++) 
    R[j] = arr[m + 1 + j]; 

  /* 合并临时数组到arr[l..r]*/ 
  i = 0; // 初始化第一个子数组的索引 
  j = 0; // 初始化第二个子数组的索引 
  k = l; // 初始化合并子数组的索引 
  while (i < n1 && j < n2) { 
    if (L[i] <= R[j]) { 
      arr[k] = L[i]; 
      i++; 
    } else { 
      arr[k] = R[j]; 
      j++; 
    } 
    k++; 
  } 

  /* 复制L[]的剩余元素 */ 
  while (i < n1) { 
    arr[k] = L[i]; 
    i++; 
    k++; 
  } 

  /* 复制R[]的剩余元素 */ 
  while (j < n2) { 
    arr[k] = R[j]; 
    j++; 
    k++; 
  } 
} 

void mergeSort(int arr[], int l, int r) { 
  if (l < r) { 
    // (l+r)/2可能会溢出 
    int m = l + (r - l) / 2; 

    // 对左右子数组进行排序 
    mergeSort(arr, l, m); 
    mergeSort(arr, m + 1, r); 

    merge(arr, l, m, r); 
  } 
}

总结

本文介绍了几种常见的C语言排序算法，包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。每种算法都有其优缺点，选择合适的算法取决于具体的应用场景。