C++实现快速排序算法，随机生成100个数进行排序 |21xrx.com

C++实现快速排序算法，随机生成100个数进行排序

2023-07-04 17:03:30 深夜i -- --

C++ 快速排序算法随机生成 100个数排序

快速排序是一种常见的排序算法，其时间复杂度为O(nlogn)，而且它的实现也非常简单。本文将介绍如何用C++实现快速排序算法，并在随机生成的100个数上进行排序。

快速排序的基本思想是选择一个关键值，然后将待排序数据分成两个部分，比关键值小的在左边，比关键值大的在右边。通过递归的方式，最终将整个数据排序。以下是C++实现快速排序算法的代码：


#include<iostream>
using namespace std;
int partition(int arr[], int low, int high)
{
  int pivot = arr[high];
  int i = low - 1;
  for (int j = low; j < high; 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 pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}
int main()
{
  int arr[100], n = 100;
  srand(0);
  for (int i = 0; i < n; i++)
  {
    arr[i] = rand() % (n * 10);
  }
  quickSort(arr, 0, n - 1);
  for (int i = 0; i < n; i++)
  {
    cout << arr[i] << " ";
  }
  return 0;
}

在以上代码中，我们首先随机生成了100个数字，数字范围为0到1000，然后我们对其进行快速排序。最后，我们将排好序的数组输出。

在运行这个程序后，会发现打印的结果是经过排好序的。这就证明了我们的快速排序算法是正确的。

在实现快速排序算法时，需要注意以下几点：

1. 快速排序算法是一种原地排序算法，其空间复杂度为O(1)。

2. 在选择关键值时，最好是选择位于数据中间的元素，这可以通过计算数据坐标来实现。

3. 由于快速排序算法的时间复杂度为O(nlogn)，因此它在处理大量数据时表现得非常出色。

总的来说，C++实现快速排序算法是一个非常简单的过程。只需要一些基本的知识和编程技巧，就能够实现这个排序算法并应用到实际中去。

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

下一篇: 如何在C++中调用Mathematica？

评论区

()

相似文章