堆排序

  1. class Solution {
  3.     public int[] sortArray(int[] nums) {
  4.         dumpSort(nums);
  5.         return nums;
  6.     }
  8.     void dumpSort(int[] arr){
  9.         for (int i = arr.length/2-1; i >= 0; i--) {
  10.             adjust(arr,i,arr.length);
  11.         }
  12.         for (int i = arr.length-1; i >= 0 ; i--) {
  13.             swap(0,i,arr);
  14.             adjust(arr,0,i);
  15.         }
  16.     }
  18.     void adjust(int[] arr,int l,int len){
  19.         int temp = arr[l];
  20.         for (int i = l*2+1; i < len; i = i*2+1) {
  21.             if (i+1 < len && arr[i] < arr[i+1]) i++;
  22.             if (arr[i] > temp){
  23.                 arr[l] = arr[i];
  24.                 l = i;
  25.             }
  26.         }
  27.         arr[l] = temp;
  28.     }
  30.     void swap(int a,int b,int[] arr){
  31.         int temp = arr[a];
  32.         arr[a] = arr[b];
  33.         arr[b] = temp;
  34.     }
  35. }

快排

  1. class Solution {
  3.     Random rand = new Random();
  4.     public int[] sortArray(int[] nums) {
  5.         quicklySort(0,nums.length-1,nums);
  6.         return nums;
  7.     }
  9.      public  void quicklySort(int l,int r,int[] arr){
  10.         if (l > r) return;
  11.         int privot =  l + rand.nextInt(r-l+1);
  12.         swap(privot,r,arr);
  13.         int idx = l-1;
  14.         for (int i = l; i < r; i++) {
  15.             if (arr[i] < arr[r]){
  16.                 swap(++idx,i,arr);
  17.             }
  18.         }
  19.         swap(++idx,r,arr);
  20.         quicklySort(idx+1,r,arr);
  21.         quicklySort(l,idx-1,arr);
  22.     }
  24.     void swap(int i,int j, int[] arr){
  25.         int temp = arr[i];
  26.         arr[i] = arr[j];
  27.         arr[j] = temp;
  28.     }
  29. }

最小k个数【快排变体】

  1. class Solution {
  2.     Random rand = new Random();
  3.     public int[] smallestK(int[] arr, int k) {
  4.          if(arr.length <= k) return arr;
  5.          quicklySort(0,arr.length-1,arr,k);
  6.          return Arrays.copyOf(arr,k);
  7.     }
  8.      public void quicklySort(int l,int r,int[] arr,int k){
  9.         int privot = l + rand.nextInt(r-l+1);
  10.         swap(privot,r,arr);
  11.         int idx = l - 1;
  12.         for (int i = l; i < r; i++) {
  13.             if (arr[i] < arr[r]){
  14.                 swap(++idx,i,arr);
  15.             }
  16.         }
  17.         swap(++idx,r,arr);
  18.         if(idx < k) quicklySort(idx+1, r, arr, k);
  19.         else if(idx > k) quicklySort(l, idx-1, arr, k);
  20.     }
  22.     void swap(int i,int j, int[] arr){
  23.         int temp = arr[i];
  24.         arr[i] = arr[j];
  25.         arr[j] = temp;
  26.     }
  27. }

归并排序

  1. class Solution {
  2.     public int[] sortArray(int[] nums) {
  3.         mergeSort(0,nums.length-1,nums);
  4.         return nums;
  5.     }
  6.     void mergeSort(int l,int r,int[] arr){
  7.         if (l >= r) return;
  8.         int mid = l + ((r - l)>>1);
  9.         mergeSort(l,mid,arr);
  10.         mergeSort(mid+1,r,arr);
  11.         if(arr[mid] <= arr[mid+1]) return;
  12.         merge(arr,l,mid+1,r,mid);
  13.     }
  14.     void merge(int[] arr,int l1,int l2,int r,int mid){
  15.         int[] temp = new int[r-l1+1];
  16.         int idx = 0;
  17.         int begin = l1;
  18.         while (l1 <= mid && l2 <= r){
  19.             temp[idx] = Math.min(arr[l1],arr[l2]);
  20.             if (temp[idx] == arr[l1])l1++;
  21.             else l2++;
  22.             idx++;
  23.         }
  24.         System.arraycopy(arr,l1,temp,idx,mid-l1+1); // l1剩余 复制到temp后面
  25.         System.arraycopy(arr,l2,temp,idx,r-l2+1);// l2剩余 复制到temp后面
  26.         System.arraycopy(temp,0,arr,begin,r-begin+1); // temp 替换 arr 
  27.     }
  28. }