アルゴリズム→並べ替えアルゴリズム
2408 ワード
ソートの挿入
並べ替え
クイックソート
/**
*
* @param arr
*/
public static > void insertSort(T [] arr) {
int j;
for(int i=1 ; i0 && tmp.compareTo(arr[j-1])<0; j--)
arr[j] = arr[j-1];
arr[j] = tmp;
}
}
並べ替え
/**
*
* @param arr
*/
public static > void sort(T [] arr) {
T[] tmp = (T[])new Comparable[arr.length];
mergeSort(arr, tmp, 0, arr.length-1);
}
public static > void mergeSort(T [] arr, T [] tmp, int left, int right) {
if(left < right) {
int center = (left+right)/2;
mergeSort(arr, tmp, left, center);
mergeSort(arr, tmp, center+1, right);
merge(arr, tmp, left, center+1, right);
}
}
public static > void merge(T [] arr, T [] tmp, int leftpos, int rightpos, int rightend) {
int tmppos = leftpos;
int leftend = rightpos-1;
int eleNums = rightend-leftpos+1;
while(leftpos <= leftend && rightpos <= rightend) {
if(arr[leftpos].compareTo(arr[rightpos]) <=0)
tmp[tmppos++] = arr[leftpos++];
else
tmp[tmppos++] = arr[rightpos++];
}
while(leftpos <= leftend)
tmp[tmppos++] = arr[leftpos++];
while(rightpos<=rightend)
tmp[tmppos++] = arr[rightpos++];
for(int i=0;i
クイックソート
/**
*
* @param arr
*/
public static > void quicksort(T [] arr) {
sort(arr, 0, arr.length-1);
}
public static > int quickSort(T [] arr, int start, int end) {
int mid = (start+end)/2;
T pivot = arr[mid];
while(start <= end) {
while(arr[start].compareTo(pivot)<0)
start++;
while(arr[end].compareTo(pivot)>0)
end--;
if(start<=end) {
T tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
start++;
end--;
}
}
return start;
}
public static > void sort(T [] arr, int start, int end) {
int mid = quickSort(arr, start, end);
if(start