题目：

快速排序的基本思路是在待排序的n个元素（无序区）中任取一个元素（通常取首元素）作为基准，把该元素放入最终位置后（称为基准归为），整个数据序列被基准分割成两个序列，所有不大于基准的元素放置在前面子序列（无序区1）中，所有不小于基准的元素放置在后面子序列（无序区2）中，并把基准排在这两个子序列的中间，这个过程称作划分。然后对两个子序列分别重复上述过程，直到每个子序列内只有一个元素或子序列为空为止。

这是一种二分法思想，每次将整个无序区一分为二，归位一个元素，对两个子序列采用同样的方式进行排序，直到子序列长度为1或0为止。

解一（移动法）：先置i = low，j = high，将基准n[low]放置到base中，循坏知道i = j为止，每轮循环让j从后向前找到一个小于base的元素n[j]，当j>i时将其前移到n[i]中，并执行i++（避免前移的元素重复比较），让i从前向后找到一个大于base的元素n[i]，当i<j时将其后移到n[j]中，并且执行j--（避免后移的元素重复比较）。循坏结束后将base放置在n[i]或者n[j]中。对应的算法如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int n[] = new int[x];
        for (int i = 0;i<n.length;i++){
            n[i] = scanner.nextInt();
        }
        QuickSort(n,0,n.length-1);
        for (int i = 0;i<n.length;i++){
            System.out.print(n[i]+" ");
        }
        scan.close();
    }

    public static int Partition(int n[],int low,int high){
        int i = low,j = high;
        int base = n[low];//以表首元素为准
        while (i<j){//从表两端交替向中间遍历，直到i = j为止
            while (i<j && n[j]>base){
                j--;//从后向前遍历，找一个小于基准的n[j]
            }
            if (i<j){
                n[i] = n[j];//n[j]前移覆盖n[i]
                i++;
            }
            while (i<j && n[i]<base){
                i++;//从前向后遍历，找一个大于基准的n[i]
            }
            if (i<j){
                n[j] = n[i];//n[i]后移覆盖n[j]
                j--;
            }
        }
        n[i] = base;//基准归为
        return i;//返回归位的位置
    }

    public static void QuickSort(int n[],int low,int high){
        if (low<high){//表中至少存在两个元素的情况
            int p = Partition(n,low,high);
            QuickSort(n,low,p-1);//对左子表递归排序
            QuickSort(n,p+1,high);//对右子表递归排序
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N=scan.nextInt();
        int arr[]=new int[N];
        for(int k=0;k<N;k++){
            arr[k]=scan.nextInt();
        }
        quickSort(arr,0,N-1);
        for(int l=0;l<N;l++){
            System.out.print(arr[l]+" ");
        }
    }

    public static void quickSort(int[] arr,int low,int high){
        if(low>=high){
            return;
        }
        int i=low-1;
        int j=high+1;
        int pivot=arr[low+high>>1];
        while(i<j){
            do{
                i++;
            }while(arr[i]<pivot);

            do{
                j--;
            }while(arr[j]>pivot);
     
            if(i<j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            }  
        }
        quickSort(arr,low,j);
        quickSort(arr,j+1,high);
    }
}

解二（区间划分法）：先用 base 存放基准 R [ s ]，将 R 划分为两个区间，前一个区间 R [ s .. i ］为"≤ base 元素区间"，初始时该区间仅含 R [ s ]，即置 i = s 。用 j 从 s +1开始遍历所有元素（满足 j ≤ t )，后一个区间 R [ i +1.. j -1］为"> base 元素区间"，初始时 j = s +1表示该区间也为空。对 R [ j ］的操作分为以下两种情况。
①若 R [ j ]≤ base ，应该将 R [ j ］移到"≤ base 元素区间"的末尾，采用交换方法，先执行 i +＋扩大"≤ base 元素区间"，再将 R [ j ］交换到 R [ i ]，最后执行 j +＋继续遍历其余元素。
②否则， R [ j ］就是要放到后一个区间的元素，不做交换，执行 j +＋继续遍历其余元素。
当 j 遍历完所有元素， R [ s .. i ］包含原来 R 中所有≤ base 的元素，再将基准 R [ s ］与 R [i］交换，这样基准 R [ i ］就归位了（ R [ s .. i -1]≤ R [ i ]，而 R [ i +1.. t ]> R [ i ])。对应的算法如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int n[] = new int[x];
        for (int i = 0;i<n.length;i++){
            n[i] = scanner.nextInt();
        }
        QuickSort(n,0,n.length-1);
        for (int i = 0;i<n.length;i++){
            System.out.print(n[i]+" ");
        }
        scan.close();
    }
    public static int Partition(int R[],int s,int t){
        int i = s,j = s+1;
        int base = R[s];//以表首元素为基准
        while (j<=t){//j从s+1开始遍历其他元素
            if (R[j]<=base){//找到小于或等于基准的元素R[j]
                i++;//扩大小于或等于base的元素区间
                if (i!=j){
                    int tmp = R[i];//将R[i]与R[j]交换
                    R[i] = R[j];
                    R[j] = tmp;
                }
            }
            j++;//继续遍历
        }
        int tmp = R[s];//将基准R[s]与R[i]进行交换
        R[s] = R[i];
        R[i] = tmp;
        return i;//返回归位的位置
    }
    public static void QuickSort(int n[],int low,int high){
        if (low<high){//表中至少存在两个元素的情况
            int p = Partition(n,low,high);
            QuickSort(n,low,p-1);//对左子表递归排序
            QuickSort(n,p+1,high);//对右子表递归排序
        }
    }
}

————————————————
版权声明：本文为CSDN博主「与我情绪共鸣374」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/2503_90258835/article/details/156086169