归并排序

  1. import java.util.Arrays;
  3. public class Merge {
  4.     public static void main(String[] args) {
  5.         int[] a = {9,8,7,6,5,4,3,2,1,0};
  6.         new Merge().sort(a,10);
  7.         System.out.println(Arrays.toString(a));
  8.     }
  10.     public void sort(int[] a, int n) {
  11.         mergesort(a,0, n-1);
  12.     }
  14.     public void mergesort(int[] a, int left, int right){
  15.         if(left>=right)
  16.             return;
  17.         int mid = (right+left)/2;
  18.         mergesort(a, left, mid);
  19.         mergesort(a, mid+1, right);
  20.         merge(a, left, mid, right);
  21.     }
  23.     //将a[left,mid] 和 a[mid+1, right]合并为a[left, right]
  24.     public void merge(int[] a, int left, int mid, int right){
  25.         int i = left;
  26.         int j = mid+1;
  27.         int t = 0;
  28.         int[] temp = new int[right-left+1];
  29.         while (i<=mid && j<=right){
  30.             if(a[i]<=a[j]){
  31.                 temp[t++] = a[i++];
  32.             }else {
  33.                 temp[t++] = a[j++];
  34.             }
  35.         }
  37.         //判断哪个子数组还有元素
  38.         int start = i;
  39.         int end = mid;
  40.         if(j<=right){
  41.             start = j;
  42.             end = right;
  43.         }
  45.         while(start <= end){
  46.             temp[t++] = a[start++];
  47.         }
  49.         //将temp数组拷回a[left,right]
  50.         //if (right - left + 1 >= 0) System.arraycopy(temp, 0, a, left + 0, right - left + 1);
  51.         for (int k = 0; k <= right-left; k++) {
  52.             a[left+k] = temp[k];
  53.         }
  54.     }
  55. }

堆排序

  1. /**
  2.  * 堆排序
  3.  */
  4. public class HeapSort {
  6.     /**
  7.      * 排序
  8.      * 堆元素是从数组下标0开始
  9.      * @param arr
  10.      */
  11.     public static void sort(int[] arr) {
  12.         if (arr.length <= 1) {
  13.             return;
  14.         }
  16.         // 1、建堆
  17.         buildHeap(arr);
  19.         // 2、排序
  20.         int k = arr.length - 1;
  21.         while (k > 0) {
  22.             // 将堆顶元素（最大）与最后一个元素交换位置
  23.             swap(arr, 0, k);
  24.             // 将剩下元素重新堆化，堆顶元素变成最大元素
  25.             heapify(arr, --k, 0);
  26.         }
  27.     }
  29.     /**
  30.      * 建堆
  31.      *
  32.      * @param arr
  33.      */
  34.     private static void buildHeap(int[] arr) {
  35.         // (arr.length - 1) / 2 为最后一个叶子节点的父节点
  36.         // 也就是最后一个非叶子节点，依次堆化直到根节点
  37.         for (int i = (arr.length - 1) / 2; i >= 0; i--) {
  38.             heapify(arr, arr.length - 1, i);
  39.         }
  40.     }
  42.     /**
  43.      * 堆化
  44.      *
  45.      * @param arr 要堆化的数组
  46.      * @param n   最后堆元素下标
  47.      * @param i   要堆化的元素下标
  48.      */
  49.     private static void heapify(int[] arr, int n, int i) {
  50.         while (true) {
  51.             // 最大值位置
  52.             int maxPos = i;
  53.             // 与左子节点（i * 2 + 1）比较，获取最大值位置
  54.             if (i * 2 + 1 <= n && arr[i] < arr[i * 2 + 1]) {
  55.                 maxPos = i * 2 + 1;
  56.             }
  57.             // 最大值与右子节点（i * 2 + 2）比较，获取最大值位置
  58.             if (i * 2 + 2 <= n && arr[maxPos] < arr[i * 2 + 2]) {
  59.                 maxPos = i * 2 + 2;
  60.             }
  61.             // 最大值是当前位置结束循环
  62.             if (maxPos == i) {
  63.                 break;
  64.             }
  65.             // 与子节点交换位置
  66.             swap(arr, i, maxPos);
  67.             // 以交换后子节点位置接着往下查找
  68.             i = maxPos;
  69.         }
  70.     }
  72. }

快速排序

  1. public class QuickSort {
  3.   // 快速排序，a是数组，n表示数组的大小
  4.   public static void quickSort(int[] a, int n) {
  5.     quickSortInternally(a, 0, n-1);
  6.   }
  8.   // 快速排序递归函数，p,r为下标
  9.   private static void quickSortInternally(int[] a, int p, int r) {
  10.     if (p >= r) return;
  12.     int q = partition(a, p, r); // 获取分区点
  13.     quickSortInternally(a, p, q-1);
  14.     quickSortInternally(a, q+1, r);
  15.   }
  17.   private static int partition(int[] a, int p, int r) {
  18.     int pivot = a[r];
  19.     int i = p;
  20.     for(int j = p; j < r; ++j) {
  21.       if (a[j] < pivot) {
  22.         if (i == j) {
  23.           ++i;
  24.         } else {
  25.           int tmp = a[i];
  26.           a[i++] = a[j];
  27.           a[j] = tmp;
  28.         }
  29.       }
  30.     }
  32.     int tmp = a[i];
  33.     a[i] = a[r];
  34.     a[r] = tmp;
  36.     System.out.println("i=" + i);
  37.     return i;
  38.   }
  39. }