C语言常用的排序算法总结 |21xrx.com

C语言常用的排序算法总结

2023-10-25 21:07:48 深夜i 14 0

排序算法 C语言常用总结

排序是计算机科学中常见的基本操作之一，而C语言作为一种广泛应用的编程语言，拥有丰富且高效的排序算法。本文将总结一些常用的C语言排序算法，并介绍它们的原理和实现方法。

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单但效率较低的排序算法。它重复地比较相邻的元素，如果顺序错误就交换位置，直到整个序列有序为止。该算法的时间复杂度为O(n^2)。冒泡排序的实现如下：

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. 插入排序（Insertion Sort）

插入排序是一种简单且效率较高的排序算法。它从第二个元素开始，将当前元素与前面的元素比较并插入到正确的位置，直到整个序列有序为止。该算法的时间复杂度为O(n^2)。插入排序的实现如下：

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

3. 快速排序（Quick Sort）

快速排序是一种常用且高效的排序算法。它通过选择一个基准元素，将序列分隔成较小和较大的两部分，然后递归地对这两部分进行排序。该算法的时间复杂度为O(nlogn)。快速排序的实现如下：

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

4. 归并排序（Merge Sort）

归并排序是一种稳定且高效的排序算法。它将序列拆分成较小的子序列，然后将这些子序列逐一进行合并排序，直到整个序列有序为止。该算法的时间复杂度为O(nlogn)。归并排序的实现如下：

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];
  for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
  for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];
  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++;
  }
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}
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);
  }
}

以上是几种常用的C语言排序算法的总结。通过合理选择适合问题的排序算法，可以提高程序的性能和效率。在实际应用中，还要根据排序的规模和数据特点，选择合适的算法来解决排序问题。

上一篇: idea打包java可执行jar包

下一篇: OpenCV无法连接摄像头：如何解决问题

评论区

相似文章