C++ 快排算法 |21xrx.com

C++ 快排算法

2023-07-01 10:16:30 深夜i -- --

C++ 快排算法排序分治法递归

快速排序（Quicksort）算法是一种高效的排序算法，由英国计算机科学家 Tony Hoare 在 1959 年首次提出。它是基于分治法（Divide and Conquer）的思想，并且是递归的。

C++ 是一种强大的编程语言，具有丰富的库函数和语法特性。在 C++ 中，实现快速排序算法可以通过递归函数和指针的运用。下面我们将介绍如何使用 C++ 实现快速排序算法。

首先，我们需要定义一个函数来实现快速排序。函数的输入为待排序的数组和数组的起始和终止索引。函数的逻辑如下：

1. 如果起始索引大于等于终止索引，即数组的大小为 0 或 1，则不需要进行排序，直接返回。

2. 选择一个基准元素，一般选择数组的第一个元素。

3. 使用两个指针，一个从起始索引开始向后移动，一个从终止索引开始向前移动，直到两个指针相遇。

4. 将比基准元素小的元素移到左边，比基准元素大的元素移到右边。

5. 递归调用快速排序函数，对左半部分和右半部分进行排序。

下面是使用 C++ 实现快速排序算法的代码：


#include <iostream>
void quicksort(int* arr, int start, int end) {
  if (start >= end)  // 递归出口
    return;
  
  
  int pivot = arr[start]; // 选择基准元素
  int left = start, right = end;
  
  while (left < right) {
    while (left < right && arr[right] >= pivot)  // 从右往左找第一个比基准元素小的元素
      right--;
    
    arr[left] = arr[right]; // 将右边小于基准元素的元素移到左边
    
    while (left < right && arr[left] <= pivot) { // 从左往右找第一个比基准元素大的元素
      left++;
    }
    arr[right] = arr[left]; // 将左边大于基准元素的元素移到右边
  }
  
  arr[left] = pivot; // 将基准元素放到合适的位置
  
  quicksort(arr, start, left - 1); // 对左半部分递归调用快速排序
  quicksort(arr, left + 1, end); // 对右半部分递归调用快速排序
}
int main() {
  int arr[] = 1;
  int size = sizeof(arr) / sizeof(arr[0]);
  
  quicksort(arr, 0, size - 1);
  
  std::cout << "Sorted array: ";
  for (int i = 0; i < size; i++) {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  
  return 0;
}

在上述代码中，我们使用一个简单的例子来演示快速排序算法的实现。首先，定义一个数组 `[6, 5, 3, 1, 8, 7, 2, 4]`，然后调用 `quicksort` 函数对数组进行排序。最后，打印排序后的数组。

通过运行上述代码，我们可以得到输出结果：`Sorted array: 1 2 3 4 5 6 7 8`。说明快速排序算法按照升序对数组进行了排序。

快速排序算法的时间复杂度为 O(nlogn)，其中 n 是数组的大小。它是一种非常高效的排序算法，在实际应用中被广泛使用。

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

下一篇: C++网校：学习C++编程的线上课程平台

评论区

()

相似文章