【算法】快速排序的递归实现算法（两种实现）

思想：

、

 

 

具体操作：

1.先以第一个元素为key（枢纽），设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2.然后i++开始往后移动，j--开始往前移动，直到找到一个i，第i位的值大于key，再找到一个j，第j位的值小于key

3.则交换第i位和第j位的值

4.继续操作，重复2和3步骤，直到i=j；则将现在的i位置上的值和key交换。这个时候key前正好都是小于它的数，后面都是大于它的数，从而key正好到了排好序后正确的位置。

5，之后将第i位之前和i之后的数分别独立出，进行1，2，3，4操作，直到最后每个独立序列中支有一个元素，那么快排完成。

按照此方法：

输入：先输入进行合并排序元素的个数，然后依次随机输入（或随机生成）每个数字。

输出：元素排序后的结果。

示例：输入：8  9  1  2  4  8  6  15  8，输出：1  2  4  6  8  8  9  15

#include <bits/stdc++.h>

using namespace std;

int div(int a[],int left,int right){
    int key=a[left];  //第一个值作为基准值
    int i=left,k=right;
    // 将< x的元素交换到左边区域
    // 将> x的元素交换到右边区域
    while(i<k){
        while(i<k&&a[i]<=key)i++;
        while(a[k]>key)k--;
        if(i<=k) swap(a[i],a[k]);
    }
    swap(a[left],a[k]);   //基准值到达最终位置
    return k;
}


void quicksort(int a[],int left,int right){
    if(left<right){//序列有效
        int p = div(a,left,right);
        quicksort(a,left,p-1);//对左半段排序
        quicksort(a,p+1,right);//对右半段排序
    }
}

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    quicksort(a,0,n-1);
    for(int i=0;i<n;i++)cout<<a[i]<<" ";
    return 0;
}

 

 

另一种写法：

把找到的小于key 的直接扔到左边，大于key的扔到右边，直到最后再将key值归位

#include <stdio.h>
#include <stdlib.h>

void quick_sort(int *a, int left, int right)
{

    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }

    int i = left;
    int j = right;
    int key = a[left];

    while(i < j)  
    {
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
        while(i < j && key <= a[j])j--;
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
        a[i] = a[j];

        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        while(i < j && key >= a[i])i++
        a[j] = a[i];
    }
    a[i] = key;//基准值到达最终位置
    
    quick_sort(a, left, i - 1);//对左半段排序
    quick_sort(a, i + 1, right);//对右半段排序
}

int main(void)
{
    int N;
    scanf("%d",&N);
    int a[N], i;


    printf("Please enter %d number of sorting: ", N);
    for(i = 0; i < N; i++)
    {
        scanf("%d", &a[i]);
    }

    quick_sort(a, 0, N - 1);

    printf("In sorted order: ");
    for(i = 0; i < N; i++)
    {
        printf("%d \n", a[i]);

    }

    return 0;
}