ソートのいくつかの実装

バブルソート

 public static void bubble(int[] arr){
 if(arr == null || arr.length < 2){
 return;
 }
 for(int end = arr.length - 1; end > 0; end--){
 for(int i = 0;i < end; i++){
 if(arr[i] > arr[i+1]){
 swap(arr, i, i + 1);
 }
 }
 }
 }
 public static void swap(int[] arr, int i, int j){
 int temp = arr[i];
 arr[i] = arr[i+1];
 arr[i+1] = temp;
 }

挿入ソート

 public static void insertSort(int[] arr){
 if(arr == null || arr.length < 2){
 return;
 }
 for(int i = 1; i < arr.length; i ++){
 for(int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--){
 swap(arr,j,j+1);
 }
 }
 }
 public static void swap(int[] arr,int i,int j){
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }

合計ソート

 public static void moergeSort(int[] arr){
 if(arr == null || arr.length < 2){
 return;
 }
 mergeProcess(arr,0,arr.length-1);
 }
 public static void mergeProcess(int[] arr,int l,int r){
 if(l == r){
 return;
 }
 int mid = (l + r) / 2;
 mergeProcess(arr,l,mid);
 mergeProcess(arr,mid + 1,r);
 merge(arr,l,mid,r);
 }
 public static void merge(int[] arr,int l,int m,int r){
 int[] help = new int[r - l + 1];
 int i = 0;
 int p1 = l;
 int p2 = m + 1;
 while(p1 <= m && p2 <= r){
 help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
 }
 while(p1 <= m){
 help[i++] = arr[p1++];
 }
 while(p2 <= r){
 help[i++] = arr[p2++];
 }
 for(i = 0; i < help.length; i++){
 arr[l+i] = help[i];
 }
 }

クイックソート

public class QuickSort {
 public static void quickSort(int[] arr){
 if(arr == null || arr.length < 2){
 return;
 }
 quickSort(arr,0,arr.length - 1);
 }
 public static void quickSort(int[] arr,int l,int r){
 if(l < r){
 //ランダム高速ソート 時間計算量 O(N)* logN)
 swap(arr,l + (int)(Math.random() * (r - l + 1)),r);
 int[] p= partition(arr,l,r);
 quickSort(arr,l,p[0] -1);
 quickSort(arr,p[1],r);
 }
 }
 public static int[] partition(int[] arr,int l,int r){
 int less = l - 1;
 int more = r;
 while(l < more){
 if(arr[l] < arr[r]){
 swap(arr,++less,l++);
 }else if(arr[l] > arr[r]){
 swap(arr,l,--more);
 }else{
 l++;
 }
 }
 return new int[]{less+1, more};
 }
 public static void swap(int[] arr,int l,int r){
 int temp = arr[l];
 arr[l] = arr[r];
 arr[r] = temp;
 }
}

ヒープソート

public class HeapSort {
 public static void heapSort(int[] arr){
 if(arr == null || arr.length < 2){
 return;
 }
 for(int i = 0;i < arr.length;i++){
 heapInsert(arr,i);
 }
 int size = arr.length;
 swap(arr,0,--size);
 while(size > 0){
 heapify(arr,0,size);
 swap(arr,0,--size);
 }
 }
 public static void heapInsert(int[] arr,int index){
 while(arr[index] > arr[(index -1 ) / 2]){
 swap(arr,index,(index-1) / 2);
 index = (index -1) / 2;
 }
 }
 public static void heapify(int[] arr,int index,int size){
 int left = index * 2 + 1;
 while(left < size){
 int largest = left + 1 < size && arr[left] < arr[left+1] ? left + 1 : left;
 largest = arr[largest] > arr[index] ? largest : index;
 if(largest == index){
 break;
 }
 swap(arr,largest,index);
 index = largest;
 left = index * 2 + 1;
 }
 }
 public static void swap(int[] arr,int i,int j){
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
}