快速排序（整数）的C语言代码和JAVA代码-摩杜云开发者社区

一、问题描述

我们目前有一些数据，这些数据都是整数，然后我们现在需要做的就是把这些数据按照小到大排一下，然后输出出来。

二、问题的解决办法

首先确认一下分界点，我们常见的分界点是第一个点，第二个点，中间的一个点；

然后我们调整一下范围，也就说所有小于等于某个点的值在左半边，大于等于某个点的值在右半边。

递归处理左右两端。

案例如下：

我们首先手头有一些数据，这些数据我们为了好排序，可以把他们都放在数组当中，这样每个数据都有一个下标了，也就确定了它们的位置。如下：

我们选定了一个参考值，这里选的是中点位置的值，当然我们也可以直接选第一个位置的值，也就说x=q[l];

如上图所示，我们的分解值选为了8；下一步我们就进行位移：

由于q[i]一直小于x上面的值，然后一直i++,直到i=2,这个时候x=q[i],停下来，执行j--;

由于3<8，所以这个时候把q[i]和q[j]上面的值进行对调。变成新的数组

这个时候，由于q[i]=3<8,所以i++;后面q[i]=9>8，所以静止不动，q[j]=8=8，所以静止不动，然后我们再次进行换位，得到上述结果。

由于q[j]=9>8，这就使得j--;如下：

由于6<8,8=8，这个时候，把i,j对调；

再执行i++,此时i,j重合，我们的界也就分好了，做到了8左边的都小于等于8，8右边的都大于等于8。然后我们再次以8为界，把8左边的数和8右边的数进行如上的操作即可。

三、代码实现：

C：

#include<stdio.h>
const int N=1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int r){
    if(l>=r) return ;//判定边界

    int x=q[l],i=l-1,j=r+1;
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j){
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
        }
    }
    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;
}

JAVA：

import java.util.Scanner;;
public class quick_sort {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[100010];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        quick_s(arr,0,n-1);
        for(int i=0;i<n;i++){
            System.out.printf("%d ",arr[i]);
        }
    }
    public static void quick_s(int q[],int l ,int r) {
        int i=l-1;
        int j=r+1;
        int x=q[l+r>>1];
        if(l>=r) return;
        while(i<j){
            do i++;while(x>q[i]);
            do j--;while(x<q[j]);
            if(i<j){
                int t=q[i];
                q[i]=q[j];
                q[j]=t;
            }
            quick_s(q, l, j);
            quick_s(q, j+1, r);
        }
    }
}