Java基本ソートアルゴリズム--クイックソート

10125 ワード


クイックソートの基本的な考え方は、ソートするデータを1回のソートで独立した2つの部分に分割し、一部のすべてのデータが他の部分のすべてのデータよりも小さくなった後、この方法で2つの部分のデータをそれぞれクイックソートし、ソートプロセス全体を再帰的に行うことで、データ全体が秩序化されたシーケンスになることです.
高速ソートアルゴリズムは,複数回の比較と交換によりソートを実現し,(1)まず配列を左右の2つの部分に分割する境界値を設定する.(2)境界値以上のデータを配列の右側,境界値未満のデータを配列の左側に集約する.この場合、左側の要素は境界値以下であり、右側の要素は境界値以上である.(3)次に,左と右のデータを独立して並べ替えることができる.左側の配列データについては、境界値を取って、その部分データを左右の2つの部分に分け、同じように左側に小さい値を配置し、右側に大きな値を配置することもできます.右側の配列データも同様の処理が可能である.(4)上記の手順を繰り返すと,これは再帰的定義であることがわかる.左の部分を再帰的に並べてから、右の部分の順序を再帰的に並べます.左、右の2つの部分の各データのソートが完了すると、配列全体のソートも完了します.
public class Test {
    public static int[] qsort(int arr[],int start,int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i<j) {
            while ((i<j)&&(arr[j]>pivot)) {
                j--;
            }
            while ((i<j)&&(arr[i]<pivot)) {
                i++;
            }
            if ((arr[i]==arr[j])&&(i<j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i-1>start) arr=qsort(arr,start,i-1);
        if (j+1<end) arr=qsort(arr,j+1,end);
        return (arr);
    }

    public static void main(String[] args) {
        int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
        int len = arr.length-1;
        arr=qsort(arr,0,len);
        for (int i:arr) {
            System.out.print(i+"\t");
        }
    }
    
}