C++排序算法详解 |21xrx.com

C++排序算法详解

2023-06-27 17:55:25 深夜i -- --

C++ 排序算法详解

C++是一门非常流行的编程语言，它也提供了多种排序算法的实现。在本文中，我们将详细讨论C++中常用的排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。

1. 冒泡排序

冒泡排序是最简单的排序算法之一。在该算法中，通过多次迭代比较相邻的元素，将较大的元素向右侧“冒泡”，从而实现排序。

C++中实现冒泡排序的代码如下：


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

2. 选择排序

选择排序是另一个简单的排序算法。在该算法中，每次迭代选择未排序部分中的最小元素并将其放置到已排序的末尾。

C++中实现选择排序的代码如下：


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

3. 插入排序

插入排序是通过迭代将未排序部分的元素插入到已排序部分中的正确位置来排序的算法。

C++中实现插入排序的代码如下：


void insertion_sort(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;
  }
}

4. 快速排序

快速排序是一种高效的、递归的排序算法。在该算法中，通过选取一个元素作为“枢纽”（pivot），将元素划分为小于和大于该枢纽的两个子序列。对两个子序列递归进行相同的操作，最终完成排序。

C++中实现快速排序的代码如下：


void quick_sort(int arr[], int left, int right){
  if(left >= right)
    return;
  
  int pivot = arr[(left + right) / 2];
  int i = left;
  int j = right;
  while(i <= j){
    while(arr[i] < pivot){
      i++;
    }
    while(arr[j] > pivot)
      j--;
    
    if(i <= j){
      swap(arr[i], arr[j]);
      i++;
      j--;
    }
  }
  quick_sort(arr, left, j);
  quick_sort(arr, i, right);
}

5. 归并排序

归并排序是一种分治排序算法，通过将元素分组、排序和合并来实现排序。在归并排序中，将一组元素分成两个子序列，将这些子序列递归地排序，然后将它们合并为一个有序的序列。

C++中实现归并排序的代码如下：


void merge_sort(int arr[], int left, int right){
  if(left >= right)
    return;
  
  int mid = (left + right) / 2;
  merge_sort(arr, left, mid);
  merge_sort(arr, mid + 1, right);
  merge(arr, left, mid, right);
}
void merge(int arr[], int left, int mid, int right){
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int L[n1], R[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;
  int j = 0;
  int 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++;
  }
}

6. 堆排序

堆排序是一种基于堆（heap）数据结构的排序算法。在该算法中，首先将元素构建为一个堆，然后不断地从堆中取出最大值（或最小值），并将其放置到已排序的序列中。

C++中实现堆排序的代码如下：


void heap_sort(int arr[], int n){
  for(int i = n / 2 - 1; i >= 0; i--){
    heapify(arr, n, i);
  }
  for(int i = n - 1; i >= 0; i--){
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}
void heapify(int arr[], int n, int i){
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;
  if(left < n && arr[left] > arr[largest])
    largest = left;
  
  if(right < n && arr[right] > arr[largest])
    largest = right;
  
  if(largest != i){
    swap(arr[i], arr[largest]);
    heapify(arr, n, largest);
  }
}

总结：

通过以上介绍，我们了解到C++提供了多种排序算法的实现，每种排序算法都有其适用的场景和优缺点。在实际应用中，我们需要根据具体情况选择合适的排序算法来解决问题。

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

下一篇: C++内存申请太耗时，该怎么办？

评论区

()

相似文章