【算法】快速排序

算法简介

  快速排序是一种非常高效的算法。首先排序速度比较快，这个从名字就可以看出来，快速排序的平均时间复杂度为O(nlogn)，最坏情况为O(n2)，最好情况为O(n)。而且快速排序是一种原地排序算法，只需要很小的栈作为辅助空间，很适合大数据集的比较。

算法思想

  快速排序算法是分为分割和递归两部分。分割指的是将选取一个基准值，然后将序列分割为左边小于该基准值，右边大于该基准值两部分。 递归指的是分别对左边和右边两部分再次分割，当递归到底时，序列便排序完成。

快速排序流程如下

代码实现

void swap(int* a,int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//分割代码，将序列 区间[l,r-1]分为[l,j],[j+1,r]两部分
int partation(int arr[],int l,int r)
{
     int select = arr[l];
    int index = l;
    for(int i=l;i<r;i++){
        if(arr[i] < select){
            swap(&arr[index+1],&arr[i]);
            index++;
        }
    }
    swap(&arr[l],&arr[index]);
    return index;

}

//递归代码： 对数组区间为[l,r)区间内元素进行快速排序
void QuickSort(int arr[],int l,int r)
{
    if(l>=r) return;
    int pip_index = partation(arr,l,r);
    QuickSort(arr,l,pip_index);
    QuickSort(arr,pip_index+1,r);
}

  上面便是快速排序的基本实现原理，但是上述代码有一点缺陷，如果需要排序的序列内重复的元素非常多，会大大影响快速排序的效率，下面为大家介绍一下三路快排的思想以及实现代码

  三路快排的实现思想非常简单，顾名思义，就是将序列分为三部分，小于基准值，等于基准值，大于基准值这三部分。

void swap(int* a,int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//三路快排： 对数组区间为[l,r)区间内元素进行快速排序
void QuickSort(int arr[],int l,int r)
{
    int i = l+1;   
    int select = arr[l];
    int sm_idx = l; //区间[l+1,sm_idx]
    int bg_idx = r; //区间[bg_idx,r)
    
    if(l >= r)return;    
    
    while(i<bg_idx){
        if(arr[i] < select){
            swap(&arr[i],&arr[sm_idx+1]);
            sm_idx++;
            i++;
        }else if(arr[i] > select){
            swap(&arr[i],&arr[bg_idx-1]);
            bg_idx--;
        }else{
            i++;
        }
    }
    swap(&arr[l],&arr[sm_idx]);
    QuickSort(arr,l,sm_idx);
    QuickSort(arr,bg_idx,r);    
}