各种排序模板

1. 快速排序：

public static void QuickSort(int[] A, int l, int r) {  if (l >= r)  return;  int i = l, j = r;  int pivot = A[i];  while(i < j) {  while(i < j && A[j] >= pivot)  j--;  A[i] = A[j];  while(i<j && A[i] <= pivot)  i++;  A[j] = A[i];  }  A[i] = pivot;  QuickSort(A, l, i - 1);  QuickSort(A,i + 1, r);  }

 private static int partition(int A[], int low, int high) {  if (low >= high)  return -1;  int i = low, j = high;  int pivot = A[i];  while(i < j) {  while(i < j && A[j] >= pivot)  j --;  A[i] = A[j];  while( i < j && A[i] <= pivot)  i ++;  A[j] = A[i];  }  A[i] = pivot;  return i;  //返回中间枢纽索引  }  public static void sortByStack(int[] a) {   Stack<Integer> stack = new Stack<Integer>();   //初始状态的左右指针入栈   stack.push(0);   stack.push(a.length - 1);   while (!stack.isEmpty()) {   //出栈进行划分   int high = stack.pop();   int low = stack.pop();   int pivotIndex = partition(a, low, high);   //保存中间变量   if (pivotIndex > low) {       //如果中间值枢纽索引，不在第一个   stack.push(low);   stack.push(pivotIndex - 1);   }   if (pivotIndex < high && pivotIndex >= 0) {       //如果中间值枢纽不在最后一个   stack.push(pivotIndex + 1);   stack.push(high);   }   }  }

2. 归并排序

private int tmp[n];
public void mergeSort(int A[], int l, int r){
    if (l >= r) return;
    int mid = (l + r) >> 1;
    mergeSort(A, l, mid);
    mergeSort(A, mid + 1, r);
    //两个有序数组合并：
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if (A[i] <= A[j])
           tmp[k++] = A[i++];
        else
            tmp[k++] = A[j++];
    }
    while(i <= mid) tmp[k++] = A[i++];
    while(j <= r) tmp[k++] = A[j++];
    //复制
    for (int i = l, j = 0; i <= r; i++, j++) A[i] = tmp[j];
}