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