C++中的各种排序算法 |21xrx.com

C++中的各种排序算法

2023-07-10 12:29:15 深夜i -- --

C++ 排序算法快速排序归并排序冒泡排序

在C++编程中, 排序算法是最基础且基本的算法之一, 对于任何程序员来说都是必须学会的技能。因为排序算法被广泛应用于各个领域，例如数据科学, 金融学, 电子商务以及计算机科学等。本篇文章将介绍各种排序算法和它们的C++实现。

1. 冒泡排序

冒泡排序是一种简单且可读性很高的算法。它的思想是反复的比较相邻的两个元素, 如果它们的顺序是错误的, 就交换它们的位置，直到所有元素有序排列。下面是一个冒泡排序的C++实现。


void bubbleSort(int arr[], int n) {
  int i, j;
  for(i = 0; i < n-1; i++) {
    for(j = 0; j < n-i-1; j++) {
      if(arr[j] > arr[j+1]) {
        swap(arr[j], arr[j+1]);
      }
    }
  }
}

2. 插入排序

插入排序的思路是假设前面的元素是有序的, 将待排序元素插入到已经排好序的元素中。在实践中，它比bubbleSort和selectionSort要快。下面是一个插入排序的C++实现。


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

3. 选择排序

选择排序的思路是在未排序的序列中查找最小的元素，然后将该元素放到序列的起始位置。接着再从剩余的元素中找到最小的元素, 并将其放到已排序序列的末尾。下面是一个选择排序的C++实现。


void selectionSort(int arr[], int n){
  int i, j, min_idx;
  for (i = 0; i < n-1; i++){
    min_idx = i;
    for (j = i+1; j < n; j++){
      if (arr[j] < arr[min_idx])
        min_idx = j;
      
    }
    swap(arr[min_idx], arr[i]);
  }
}

4. 快速排序

快速排序是一种很快的排序算法。它的核心是partition函数，该函数选择一个枢纽，然后将小于它的元素放在其左侧，大于它的元素放在其右侧。在每个子数组中递归地执行此操作，直到所有元素排序完成。下面是一个快速排序的C++实现。


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++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1], arr[high]);
  return (i + 1);
}
void quickSort(int arr[], int low, int high) {
  if (low < high){
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
  }
}

总结

本文介绍了C++中常见的排序算法，包括冒泡排序，插入排序，选择排序和快速排序。不同的排序算法适用于不同类型的数据和程序需求, 选择正确的算法对于程序执行效率至关重要。因此，了解和掌握不同算法的原理和用法，对于成为一名优秀的程序员来说是非常重要的。

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

下一篇: C++中如何结束if语句？

评论区

()

相似文章