C++程序实现排序算法 |21xrx.com

C++程序实现排序算法

2023-07-05 12:57:53 深夜i -- --

C++ 程序排序算法

排序算法是计算机科学中非常重要的一种基础算法。在C++程序设计中，为了解决各类数据排序的问题，我们需要采用不同的排序算法。本文将会介绍几种常用的排序算法并给出相应的C++程序实现。

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过不断比较相邻的两项，如果它们的顺序不对就交换它们的位置，直到所有的元素都有序为止。下面是冒泡排序的C++代码：


void bubble_sort(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]); // swap是C++中自带的交换函数
      }
    }
  }
}

选择排序（Selection Sort）通过每次找到未排序部分的最小值来实现排序。具体来说，它从未排序部分中找到最小的元素，并将其放到已排序部分的末尾。下面是选择排序的C++代码：


void selection_sort(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[i], arr[min_idx]);
  }
}

插入排序（Insertion Sort）通过将一个元素插入已排好序的列表中来进行排序。具体来说，它从未排序部分中取出一个元素，并将其插入到已排序部分的适当位置。下面是插入排序的C++代码：


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

快速排序（Quick Sort）采用分治法的思路来进行排序。它通过不断地选取基准值来将序列分为两部分，然后对这两部分分别进行排序。下面是快速排序的C++代码：


void quick_sort(int arr[], int l, int r) {
  if (l < r) {
    int pivot = partition(arr, l, r);
    quick_sort(arr, l, pivot-1);
    quick_sort(arr, pivot+1, r);
  }
}
int partition(int arr[], int l, int r) {
  int pivot = arr[r];
  int i = l-1;
  int j;
  for (j = l; j < r; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i+1], arr[r]);
  return i+1;
}

以上是常用的几种排序算法及其对应的C++代码实现。在实际应用中，应根据具体情况选择合适的排序算法。同时，也可以利用不同的排序算法进行组合使用，以节省时间和空间的开销，提高排序效率。

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

下一篇: 如何在C++中求一个整数的位数

评论区

()

相似文章