超详细解析C++实现快速排序算法的方法

什么是快速排序？

快速排序是一种高效的排序算法。因为采用了分治法的思想，利用递归实现，每次排序只需比较部分元素，而不需要像冒泡排序和插入排序那样需要从头到尾对比每个元素，因此效率非常高。

快速排序算法的基本思想

快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，使得前面的记录的关键字均小于后面的记录的关键字，然后再依次对前后两部分的记录进行排序，递归完成最终的排序。

快速排序算法的实现

第一步：确定基准元素

快速排序算法的核心之一是确定一个基准元素，通常我们选择第一个或者最后一个元素作为基准元素，即以a[left]或a[right]为基准元素。

int partition(int a[],int left,int right)
{
   int pivot=a[left]; //以a[left]作为基准元素
   while(left<right){
        //从右向左查找小于基准元素的数
        while(left<right && a[right]>=pivot) right--;
        a[left]=a[right]; //将小于基准元素的数放到左边
        //从左向右查找大于基准元素的数
        while(left<right && a[left]<=pivot) left++;
        a[right]=a[left]; //将大于基准元素的数放到右边
    }
    a[left]=pivot; //将基准元素归位
    return left;   //返回基准元素的位置
}

第二步：分割数组

将数组分为两部分，以一次排序后的基准元素位置分割，左边的数都小于基准元素，右边的数都大于基准元素。

void quickSort(int a[], int left, int right)
{
    if (left < right)
    {
        int pos = partition(a, left, right); //pos为基准元素的位置
        quickSort(a, left, pos-1);  //递归排序基准元素左边的数组
        quickSort(a, pos+1, right); //递归排序基准元素右边的数组
    }
}

第三步：完整代码实现

#include <bits/stdc++.h>
using namespace std;
int partition(int a[],int left,int right)
{
   int pivot=a[left]; //以a[left]作为基准元素
   while(left<right){
        //从右向左查找小于基准元素的数
        while(left<right && a[right]>=pivot) right--;
        a[left]=a[right]; //将小于基准元素的数放到左边
        //从左向右查找大于基准元素的数
        while(left<right && a[left]<=pivot) left++;
        a[right]=a[left]; //将大于基准元素的数放到右边
    }
    a[left]=pivot; //将基准元素归位
    return left;   //返回基准元素的位置
}
void quickSort(int a[], int left, int right)
{
    if (left < right)
    {
        int pos = partition(a, left, right); //pos为基准元素的位置
        quickSort(a, left, pos-1);  //递归排序基准元素左边的数组
        quickSort(a, pos+1, right); //递归排序基准元素右边的数组
    }
}
int main()
{
    int n;
    cout<<"请输入数组大小:"<<endl;
    cin>>n;
    int a[n];
    cout<<"请输入"<<n<<"个数:"<<endl;
    for(int i=0;i<n;i++)
        cin>>a[i];
    quickSort(a,0,n-1);
    cout<<"排序后的数组为:"<<endl;
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

示例说明

示例一

在第一次排序时，选择数组[6,3,8,2,9,1]的第一个数6作为基准元素，用左右指针分别从数组的两端开始扫描。

• 右指针扫描，找到小于基准元素的数，此时右指针扫描到的数是1。
• 左指针扫描，找到大于基准元素的数，此时左指针扫描到的数是8。
• 交换左右指针扫描到的数，即将左指针扫描到的8和右指针扫描到的1位置互换。
• 重复上述步骤，直至左右指针相遇，此时将基准元素6与左指针指向的位置互换。
• 数组[6,3,8,2,9,1]第一次排序完成，以基准元素6为中心，左边的数都小于6，右边的数都大于6。左边的数是[3,2,1]，右边的数是[8,9]。

示例二

在第二次排序时，选择数组[3,2,1]的第一个数3作为基准元素，用左右指针分别从数组的两端开始扫描。

• 右指针扫描，找到小于基准元素的数，此时右指针扫描到的数是1。
• 左指针扫描，找到大于基准元素的数，此时左指针扫描到的数是2。
• 交换左右指针扫描到的数，即将左指针扫描到的2和右指针扫描到的1位置互换。
• 重复上述步骤，直至左右指针相遇，此时将基准元素3与左指针指向的位置互换。
• 数组[3,2,1]第二次排序完成，以基准元素3为中心，左边的数都小于3，右边的数都大于3。左边的数是[2,1]，右边的数是[]。

总结

通过以上示例可以看出，每次排序后都会确定一个基准元素，并将数组分成两部分，再对左右两部分进行递归排序，最终完成排序。在实现快速排序算法时，要注意基准元素的选择和分割数组的步骤。