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

C++实现快速排序算法

2023-06-27 10:10:39 深夜i -- --

C++ 快速排序算法分治法时间复杂度

快速排序是一种常见的基于比较的排序算法，它的思想是归并排序的思想，将一个大的无序数列分割成两个子数列，然后将子数列继续递归分割，直到每个子数列只有一个元素为止，最后将子数列合并成一个有序数列。

C++语言可以很方便地实现快速排序算法，这里我们来看一下如何使用C++实现快速排序。

首先我们需要一个函数来实现分割数组的功能。这里我们选择将数组的右边界作为枢纽元素，从左往右扫描数组，比枢纽元素小的放到左边，比枢纽元素大的放到右边，最后将枢纽元素和左边的最后一个元素交换位置，返回左边的最后一个元素的下标。


int partition(int arr[], int left, int right)
{
  int pivot = arr[right];
  int i = left - 1;
  for(int j=left; j<right; j++)
  {
    if(arr[j] < pivot)
    {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i+1], arr[right]);
  return i + 1;
}

接着我们需要一个递归函数进行分治。该函数先调用partition函数将数组分成两个部分，然后再递归对左右两部分进行处理。


void quicksort(int arr[], int left, int right)
{
  if(left < right)
  {
    int p = partition(arr, left, right);
    quicksort(arr, left, p-1);
    quicksort(arr, p+1, right);
  }
}

最后我们可以在main函数中调用quicksort函数来排序一个数组。


int main()
{
  int arr[] = 1;
  int n = sizeof(arr)/sizeof(arr[0]);
  quicksort(arr, 0, n-1);
  for(int i=0; i<n; i++)
  {
    cout<<arr[i]<<" ";
  }
  return 0;
}

以上就是使用C++实现快速排序算法的方法，相比于其他排序算法，快速排序算法的时间复杂度较低，通常情况下可以达到O(nlogn)的时间复杂度。

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

下一篇: C++基础学完后，如何进一步提升能力？

评论区

()

相似文章