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

C++实现快速排序算法

2023-06-28 10:07:38 深夜i -- --

快速排序 C++ 算法

快速排序算法是一种高效的排序算法，其时间复杂度为O(nlogn)。C++是一种常用的编程语言，其提供了丰富的数据结构和算法库，非常适合实现各种排序算法，包括快速排序。

快速排序算法的基本思想是选择一个元素作为基准值，将待排序的序列分成两个部分，其中左侧部分的元素值小于基准值，右侧部分的元素值大于基准值。然后递归对两个部分进行排序，直到序列有序。

以下是C++实现快速排序算法的示例代码：


#include <iostream>
using namespace std;
void quickSort(int data[], int left, int right) {
  if (left < right) {
    int i = left, j = right, pivot = data[left];
    while (i < j) {
      while (i < j && data[j] >= pivot) j--;
      if (i < j) data[i++] = data[j];
      while (i < j && data[i] < pivot) i++;
      if (i < j) data[j--] = data[i];
    }
    data[i] = pivot;
    quickSort(data, left, i - 1);
    quickSort(data, i + 1, right);
  }
}
int main() {
  int data[] = {9, 5, 3, 7, 1, 8, 6, 2, 4};
  int len = sizeof(data) / sizeof(data[0]);
  quickSort(data, 0, len - 1);
  for (int i = 0; i < len; i++) {
    cout << data[i] << " ";
  }
  cout << endl;
  return 0;
}

这段代码中，快速排序算法的核心代码是quickSort函数。该函数以一个整数数组data、左侧索引left和右侧索引right作为参数。在函数内部，首先判断左侧索引是否小于右侧索引，如果是，则以left为基准值，并使用双指针i和j来对序列进行划分。具体来说，i和j从序列的两端开始遍历，若data[j]大于等于基准值，则向左移动j指针，直到找到一个小于基准值的数，将其放到i位置上，然后i指针向右移动一位。再从左侧开始遍历，若data[i]小于基准值，则向右移动i指针，直到找到一个大于等于基准值的数，将其放到j位置上，然后j指针向左移动一位。如此往返，直到i和j相遇为止，此时i所指的位置就是基准值的最终位置。然后递归地对基准值左侧和右侧的序列进行排序，直到整个序列变得有序。

在主函数中，我们定义了一个包含9个元素的int数组data，并对其进行快速排序。排序结束后，我们使用for循环遍历数组并输出结果。

快速排序算法是一种高效且常用的排序算法，它可以帮助我们实现各种对序列的操作。C++提供了一系列实用的排序算法库，但快速排序算法的实现依然具有一定的难度。通过理解其原理和代码实现，我们可以更好地应用此算法，并开发出更多高效、实用的算法，帮助我们在实际编程中取得更好的效果。

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

下一篇: C++求三个整数的平均值

评论区

()

相似文章