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

C++实现快速排序算法

2023-07-10 01:28:50 深夜i -- --

C++ 快速排序算法实现

快速排序是一种高效的排序算法，C++中可以轻松实现。快速排序算法的基本思想是通过递归将待排序序列划分成两个子序列，其中一部分比另一部分小，然后继续对子序列进行排序直到整个序列已经有序。

快速排序的过程分为以下几个步骤：

1. 选择一个枢轴元素（一般选择待排序序列第一个元素）。

2. 将待排序序列划分成两个子序列，其中比枢轴元素小的放到左侧，比枢轴元素大的放到右侧。

3. 对左右两个子序列分别递归地进行上述两步操作，直到子序列只剩下一个元素。

4. 最后将排序好的子序列合并起来得到整个有序序列。

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


#include<iostream>
using namespace std;
void QuickSort(int a[],int left,int right) {//left为子序列首，right为子序列尾
  if(left>=right) return;
  int i=left,j=right;
  int pivot=a[left]; //选择第一个元素为枢轴元素
  while(i<j) {//将比枢轴元素小的放左侧，比其大的放右侧
    while(i<j && a[j]>=pivot) j--;
    if(i<j) a[i++]=a[j];
    while(i<j && a[i]<=pivot) i++;
    if(i<j) a[j--]=a[i];
  }
  a[i]=pivot; //把枢轴元素放到正确位置上
  QuickSort(a,left,i-1);//递归排序左子序列
  QuickSort(a,i+1,right);//递归排序右子序列
}
int main(){
  int a[]={1,3,5,2,4,6,8,7,9,0};
  int len=sizeof(a)/sizeof(a[0]);
  QuickSort(a,0,len-1);//对整个数组进行排序
  for(int i=0;i<len;i++) cout<<a[i]<<" ";
  cout<<endl;
  return 0;
}

代码中的QuickSort函数用于递归排序子序列，参数left和right分别表示子序列的首尾元素下标。首先选择第一个元素为枢轴元素，然后将待排序子序列中比枢轴元素小的放到左侧，比其大的放到右侧，最后将枢轴元素放到左右子序列的中间正确位置上。递归调用QuickSort函数即可对左右子序列进行排序，直到子序列只剩下一个元素，排序完成。

快速排序的时间复杂度为O(nlogn)，是一种实用最广泛的排序算法，其实现方式也是相对比较简单的。

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

下一篇: C++重载与隐藏

评论区

()

相似文章