快速排序c与java实现

java实现

import java.util.Scanner;

public class TangRongjie {
    //快速排序（基于Hoare划分）
    public static int hoarePartition(int[] num, int start, int end) {
        //使用当前第一个元素作为中轴
        int p = num[start];
        //i从最左边开始扫描（除去中轴元素），j从最右边扫描
        int i = start, j = end + 1;
        //循环扫描，知道i所在元素大于中轴元素，j所在元素小于中轴
        while(true) {
            //i循环时可能超过数组边界，故加end限制
            do {i++;}while(i < end && num[i] < p);
            //因为j递减时，中轴p可以作为边界限制，则不用加j的其他限制
            do {j--;}while(num[j] > p);
            if(i >= j)
                break;
            //交换i，j位置的元素，再继续
            swap2(num, i, j);
        }
        //将j所在元素与中轴元素交换
        swap2(num, start, j);
        //返回中轴元素所在位置
        return j;
    }
    public static void quickSort(int[] num, int start, int end) {
        int index;
        if(start < end) {
            index = hoarePartition(num, start, end);
            //对左边递归排序
            quickSort(num, start, index - 1);
            //对右边递归排序
            quickSort(num, index + 1, end);
        }
    }
    //交换指定位置的两个元素
    public static void swap2(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        int[] num = new int[n];
        
        for(int i = 0; i < num.length; i++)
            num[i] = in.nextInt();
        
        //调用算法
        quickSort(num, 0, n - 1);
        for(int i = 0; i < num.length; i++)
            System.out.print(num[i] + " ");
        
        in.close();
    }
}

c实现

#include<cstdio>
#include<algorithm>

using namespace std;

//划分 
int Partition(int A[], int left, int right){
    int temp = A[left];
    while(left < right){
        while(left < right && A[right] > temp)
            right--;
        A[left] = A[right];
        while(left < right && A[left] <= temp)
            left++;
        A[right] = A[left];
    }
    A[left] = temp;
    return left;
}
//递归排序 
void quickSort(int A[], int left, int right){
    if(left < right){
        int pos = Partition(A, left, right);
        quickSort(A, left, pos-1);
        quickSort(A, pos+1, right);
    }
} 

int main(){
    int A[100], n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    quickSort(A, 0, n-1);
    for(int i = 0; i < n; i++)
        printf("%d ", A[i]);
    return 0;
}

附加 C++实现

注意标记处，主要为防止超时，可以考虑数组[1, 2]

实现1
实现2