[数据结构与算法]快速排序、堆排序、归并排序

归并排序：

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