快速排序(quick Sort)

组别：提高组
难度：5

OJ平台：P1147

快速排序是基于分治的思想
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。(下面两个例子分别用数组中间的数为基准数，和最左边的数做为基准数)
2．分区过程，将比基准数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

一、以中间数为基数

以中间值为基准的代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2022-07-27 12:50:17
 * 最后修改: 2025-01-15 18:10:15
 * 文件描述: C++ implementation of quickSort  
 *          以中间元素为基准，大于mid在右边，小于mid在左边
****************************************************************/
#include <iostream>
using namespace std;

// 全局变量数组
int arr[100];

void quickSort(int l, int r) {
    if (l >= r) return; // 递归终止条件

    int i = l, j = r, x = arr[(l + r) >> 1]; // 选择中间值为 pivot
    while (i <= j) {
        while (arr[i] < x) i++; // 从左向右找大于等于 pivot 的元素
        while (arr[j] > x) j--; // 从右向左找小于等于 pivot 的元素
        if (i <= j) { // 如果 i 和 j 未交叉，交换两者
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    // 递归调用
    if (l < j) quickSort(l, j);
    if (i < r) quickSort(i, r);
}

int main() {
    int n;
    cout << "Please input a number for array size: ";
    cin >> n;

    cout << "Please input " << n << " elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    quickSort(0, n - 1); // 直接调用 quickSort

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}

二、以最左边数字为基数

以数列最左侧数字为基准数的实现：

/**************************************************************
C++ implementation of quickSort 
date::2023-3-14
author: ALex Li 
version: 1.0
***************************************************************/

#include <iostream>
using namespace std;
int arr[100];
void quickSort(int array[],int left,int right)
{	int i,j;
	if(left<right){
		i=left;j=right;
		int temp=array[left];
		do{	
			while(array[j]>temp && i<j)
				j--;
			if(i<j){
                array[i]=array[j];
				i++;
			}
            while(array[i]<temp && i<j)
			    i++;
			if(i<j){
                array[j]=array[i];
				j--;
			}
		}while(i<j);
		array[i]=temp;
		
		quickSort(array,left,i-1);
		quickSort(array,i+1,right);
	}
}
int main(){
   int n;
   cout<<"please input a number for array size: ";
   cin>>n;
   cout<<"please input "<<n<<" elements of array: ";
   for (int i = 0; i < n; i++)
   {
       cin>>arr[i];
   }
    quickSort(arr,0,n-1);
    for (int i = 0; i <n ; i++)
    {
        cout<<arr[i]<<' ';
    }
    
}

快速排序是最优和平均时间复杂度都是O(nlogn)，最坏O(n²) (每次划分只得到一个比上次划分少一个记录的子序列)

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

快速排序(quick Sort)