归并排序:
public static void p(int arr[],int L,int R){
if(arr.length()==0||arr==null) return;
if(L==R) return;
int mid = L+((R-L)>>1);
p(arr,0,mid);
p(arr,mid+1,R);
merge(arr,L,mid,R);
}
public static void merge(int arr[],int L,int mid,int R){
int p1 = L;
int p2 = mid+1;
int index = 0;
int help[] = new int[R-L+1];
while(p1<=mid&&p2<=R){
help[index++] = arr[p1]>arr[p2]?arr[p2++]:arr[p1++];
}
while(p1<=mid){
help[index++] = arr[p1++];
}
while(p2<=R){
help[index++] = arr[p2++];
}
for(int i = 0;i<help.length;i++){
arr[i+L] = help[i];
}
}
快速排序:
public static void quickSort(int arr[]){
if(arr.length<2||arr==null) return;
quickSort(arr,0,arr.length-1);
}
public static void quickSort(int arr[],int L,int R){
if(L<R){
swap(arr,L+(int)(Math.random()*(R-L+1)),R);
int p[] = partion(arr,L,R);
quickSort(arr,L,p[0]-1);
quickSort(arr,p[1]+1,R);
}
}
public static int[] partion(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,--more,L)
}else{
L++;
}
}
swap(arr,more,R);
return new int[]{less+1,more};
}
public static void swap(int arr[],int i,int j){
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
堆排序:
public static void HeapSort(int arr[]){
if(arr.length==0||arr==null) return;
for(int i = 0;i<arr.length-1,i++)
heapInsert(arr,i);
}
public static void heapInsert(int arr[],int index){
while(arr[(index-1)/2]<arr[index]){
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+1]<arr[left]?left:left+1;
largest = arr[largest]>arr[index]?largest:index;
if(largest==index) break;
swap(arr,largest,index);
index = largest;
left = left*2+1;
}
}
public static void swap(int arr[],int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}