快速排序

快速排序

基本思路

• 确认基准点 X
• 调整顺序
• 使用递归处理左右两端

1. 找到一个基准点X，一般取这一组数中间位置的，可以减少算法的复杂度。
2. 调整基准点左右两边的数，左边比它小，右边比它大。
3. 然后使用递归分别对左右两边再进行一二两步

---

实现顺序调整的方法

使用两个指针分别指向左右两端 i j

移动左边的 i，直到遇到第一个大于等于X的数停下

移动右边的 j， 直到遇到第一个小于等于X的数停下

交换两个指针所指的数，实现 i 左边 <=X , j 右边 >= X

交换完成后继续进行以上步骤， 直到 i >= j ,实现顺序交换

---

代码模板实现

#include <iostream>

using namespace std;

const int N = 1e6 + 10 ;
 
int q[N];
int n ; 

void quick_sort( int q[] , int l , int r )
{
    if (l >= r)					//排序完成，退出函数
        return; 
    int x = (q[l]+q[r]) /2;		//设置基准点
    int i = l -1 ;
    int j = r + 1 ;
    while( i < j )				//i 与 j 的每一次交换操作
    {
        do						
            i++;
        while (q[i] < x );
        do 
            j--;
        while (q[j] > x );
        if (i < j)  			//只有两个指针还没有互相越过的时候才可以交换
            swap(q[i] , q[j]);	//一样了就交换
        
    }
    
    quick_sort(q , l , j);     // 递归处理左右两边
    quick_sort(q , j + 1 , r); 
    
}

int main()
{
    scanf("%d" , &n);
    
    for ( int i = 0 ; i < n ; i++)
        scanf("%d", & q[i]);
    
    quick_sort( q, 0 , n - 1);
    
    for ( int i = 0 ;  i < n ; i++)
        printf("%d ", q[i]);
    
    return 0;
        
}

---

引申：快速选择算法

​ 给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n , k;
int q[N];

int quick_sort( int l, int r, int k )					//直接返回第k个数值
{
    if (l == r)     return q[l];						//相当于只有一个数字了，直接返回就可以了

    int x = (q[l] + q[r]) / 2, i = l - 1, j = r + 1;	//同快排的步骤
    
    while (i < j)
    {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (q[j] > x);
        if (i < j)
            swap(q[i], q[j]);
    }
    
    int sl = j- l +1;									//计算 左边的数字数目, 与k比较
    
    if( sl >= k)
    return  quick_sort( l, j, k );						//数目 大于 等于 k ， 只需要对左边进行递归就可以了
    											
    return  quick_sort( j + 1, r , k-sl);				//小于 k ， 则对右边进行递归
    
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
        
    printf("%d", quick_sort( 0, n - 1,k));
    return 0;
}

时间复杂度比直接快排要低。