快速排序(quick Sort)

组别：提高组
难度：5

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

一、以中间数为基数

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

/**************************************************************** 
 * Description: C++ implementation of quickSort  
 *              以中间元素为基准，大于mid在右边，小于mid在左边
 * Author: Alex Li
 * Date: 2022-07-27 12:50:17
 * LastEditTime: 2023-11-11 22:47:43
****************************************************************/

#include <iostream>
using namespace std;
int arr[100];

void quickSort(int arr[], int l, int r){
    if (l >= r) return;

    int i = l, j = r, x = arr[(l + r) >> 1]; //x为中间元素值
    while (i < j){
        while (arr[i] < x)i++;
        while (arr[j] > x)j--;
        if (i < j) swap(arr[i], arr[j]);
    }
    quickSort(arr, l, j), quickSort(arr, j + 1, r);
}

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]<<' ';
    }
    
}

二、以最左边数字为基数

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

/**************************************************************
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)