快速排序c++&&java代码实现

快速排序的思想 （基于分治法）: 

每次选一个基准元素x，通过一次遍历将排序表划分为独立的两部分a[l,k-1],a[k+1,r];

其中左边的元素<=x,右边的1元素>x,然后递归下去，直到每个块的大小为1 ;

c++

#include<bits/stdc++.h>
using namespace std ;

void quickSort(vector<int>& q,int l,int r){
    if (l >= r) return;
    //设置分界点
    int x = q[l + r >> 1];
    //调整区间
    int 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 temp = q[i];
            q[i] = q[j];
            q[j] = temp;
        }
    }
    //对左侧递归排序
    quickSort(q, l, j);
    //对右侧递归排序
    quickSort(q, j + 1, r);
}

int main(){
	int n ; cin >> n ;
	vector<int> a(n) ;
	for(int& x : a) cin >> x ;
	quickSort(a,0,n-1) ;
	for(int& x : a) cout << x << " " ;
}

java

package sf;

import java.util.Scanner;

public class quicksort {

    public static void quickSort(int[] q, int l, int r) {
        if (l >= r) return;
        //设置分界点
        int x = q[l + r >> 1];
        //调整区间
        int 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 temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }
        //对左侧递归排序
        quickSort(q, l, j);
        //对右侧递归排序
        quickSort(q, j + 1, r);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] q = new int[n];
        for (int i = 0; i < n; i++) {
            q[i] = sc.nextInt();
        }
        quickSort(q, 0, n -1);
        for (int value : q) {
            System.out.print(value + " ");
        }
    }
}