JAVAデータ構造とアルゴリズム――高速並べ替え
10146 ワード
JAVAデータ構造とアルゴリズム――高速並べ替え
クイックソート:
swapメソッド:
クイックソート:
/*
* O(nlogn), O(logn)
* */
public class QuickSort<E extends Comparable> {
Swap<E> s = new Swap<>();
/* */
public int sort(E[] L, int low, int hight){
E temp = L[low];
while(low < hight){
while(L[hight].compareTo(temp) > 0 && low < hight){
hight--;
}
s.swap(L, low, hight);
while(L[low].compareTo(temp) <= 0 && low < hight){
low++;
}
s.swap(L, low, hight);
}
// L[low] = temp;
return low;
}
/* */
public void quickSort(E[] L, int low, int hight){
if(low < hight){
int temp = sort(L, low, hight);
quickSort(L, low, temp - 1);
quickSort(L, temp + 1, hight);
}
}
public static void main(String[] args) {
QuickSort<Integer> quickSort = new QuickSort<>();
Integer[] data = {2, 4, 6, 1, 8, 2, 0, 3, -1};
quickSort.quickSort(data, 0, data.length - 1);
System.out.println(Arrays.toString(data));
}
}
swapメソッド:
public void swap(E[] data, int i, int j){
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}