快速排序（整數）的C語言代碼和JAVA代碼-有解無憂

一、問題描述

我們目前有一些資料，這些資料都是整數，然后我們現在需要做的就是把這些資料按照小到大排一下，然后輸出出來，

二、問題的解決辦法

首先確認一下分界點，我們常見的分界點是第一個點，第二個點，中間的一個點；

然后我們調整一下范圍，也就說所有小于等于某個點的值在左半邊，大于等于某個點的值在右半邊，

遞回處理左右兩端，

案例如下：

我們首先手頭有一些資料，這些資料我們為了好排序，可以把他們都放在陣列當中，這樣每個資料都有一個下標了，也就確定了它們的位置，如下：

這個時候我們選好了分界值，如上所示，為8，下一步我們就進行位移：

由于8=8，所以i靜止不動，9>8，這就使得j--;如下：

三、代碼實作：

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);
        }
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548175.html

標籤：其他

上一篇：哈希專題總結(上)

下一篇：Python實作簡易版TCP代理