leetcode912 排序数组

给你一个整数数组 nums，请你将该数组升序排列。 

  1. //v1.0 未优化的快排
  2. class Solution {
  3.     public int[] sortArray(int[] nums) {
  4.         int low=0;
  5.         int high=nums.length-1;
  6.         QSort(nums,low,high);
  7.         return nums;
  9.     }
  10.     public void QSort(int[] nums, int low, int high){
  11.         int pivot;
  12.         if(low<high){
  13.             //将nums一分为二，算出枢轴值pivot
  14.             pivot=Partition(nums,low,high);
  15.             //对低子表递归排序
  16.             QSort(nums,low,pivot-1);
  17.             //对高子表递归排序
  18.             QSort(nums,pivot+1,high);
  19.         }
  20.     }
  21.     //交换顺序表中子表的记录，使枢轴记录到位，并返回其位置
  22.     //此时在它之前（后）的记录均不大于（小）于它
  23.     public int Partition(int[] nums,int low,int high){
  24.         int pivotKey;
  25.         pivotKey=nums[low];
  26.         while(low<high){
  27.             while(low<high&&nums[high]>=pivotKey) high--;
  28.             swap(nums,low,high);
  29.             while(low<high&&nums[low]<=pivotKey) low++;
  30.             swap(nums,low,high);
  31.         }
  32.         return low;
  33.     }
  34.     public void swap(int[] nums, int i, int j){
  35.         int temp=nums[j];
  36.         nums[j]=nums[i];
  37.         nums[i]=temp;
  39.     }
  40. }
  42. //v2.0 优化后的快排
  43. class Solution {
  44.     public int[] sortArray(int[] nums) {
  45.         int low=0;
  46.         int high=nums.length-1;
  47.         QSort(nums,low,high);
  48.         return nums;
  50.     }
  51.     public void QSort(int[] nums, int low, int high){
  52.         int pivot;
  53.         while(low<high){
  54.             //将nums一分为二，算出枢轴值pivot
  55.             pivot=Partition(nums,low,high);
  56.             //对低子表递归排序
  57.             QSort(nums,low,pivot-1);
  58.             //对高子表递归排序
  59.             low=pivot+1;
  60.         }
  61.     }
  62.     //交换顺序表中子表的记录，使枢轴记录到位，并返回其位置
  63.     //此时在它之前（后）的记录均不大于（小）于它
  64.     public int Partition(int[] nums,int low,int high){
  65.         int pivotKey;
  66.         //优化枢轴选取
  67.         int m=low+(high-low)/2;
  68.         if(nums[high]<nums[m]) swap(nums,high,m);
  69.         if(nums[high]<nums[low]) swap(nums,high,low);
  70.         if(nums[low]<nums[m]) swap(nums,low,m);
  71.         pivotKey=nums[low];
  72.         while(low<high){
  73.             while(low<high&&nums[high]>=pivotKey) high--;
  74.             nums[low]=nums[high];
  75.             while(low<high&&nums[low]<=pivotKey) low++;
  76.             nums[high]=nums[low];
  77.         }
  78.         nums[low] = pivotKey;
  79.         return low;
  80.     }
  81.     public void swap(int[] nums, int i, int j){
  82.         int temp=nums[j];
  83.         nums[j]=nums[i];
  84.         nums[i]=temp;
  86.     }
  87. }
  88. class Solution {
  89.     public int[] sortArray(int[] nums) {
  90.         //堆排序
  91.         int i;
  92.         for (i = nums.length / 2 - 1; i >= 0; i--) {
  93.             HeapAdjust(nums, i, nums.length);
  94.         }
  95.         for (i = nums.length - 1; i >= 1; i--) {
  96.             int temp = nums[i];
  97.             nums[i] = nums[0];
  98.             nums[0] = temp;
  99.             HeapAdjust(nums, 0, i);
  100.         }
  101.         return nums;
  102.     }
  104.     public void HeapAdjust(int[] nums, int parent, int length) {
  105.         int temp = nums[parent];
  106.         int lChild = 2 * parent + 1;
  107.         while (lChild < length) {
  108.             if (lChild + 1 < length && nums[lChild + 1] > nums[lChild]) lChild++;
  109.             if (temp > nums[lChild]) break;
  110.             nums[parent] = nums[lChild];
  111.             parent = lChild;
  112.             lChild = 2 * lChild + 1;
  114.         }
  115.         nums[parent] = temp;
  116.     }
  117. }

剑指51 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 

  1. //利用归并算法（分治思想）
  2. class Solution {
  3.     private int count;
  4.     public int reversePairs(int[] nums) {
  5.         int len = nums.length;
  6.         merge(nums,0,len-1);
  7.         return count;
  8.     }
  9.     private void merge(int[] arr, int left, int right){
  10.         if(left<right){
  11.             int mid = left+((right-left)>>1);
  12.             merge(arr,left,mid);
  13.             merge(arr,mid+1,right);
  14.             mergeSort(arr,left,mid,right);
  15.         }
  16.     }
  17.     private void mergeSort(int[] arr,int left, int mid, int right){
  18.         int[] temp = new int[right-left+1];
  19.         int index=0;
  20.         int temp1 = left;
  21.         int temp2 = mid+1;
  22.         while(temp1<=mid&&temp2<=right){
  23.             if(arr[temp1]<=arr[temp2]){
  24.                 temp[index++]=arr[temp1++];
  25.             }else{
  26.                 count+=mid-temp1+1; //主要代码
  27.                 temp[index++]=arr[temp2++];
  28.             } 
  29.         }
  30.         if(temp2<=right) System.arraycopy(arr,temp2,temp,index,right-temp2+1);
  31.         if(temp1<=mid) System.arraycopy(arr,temp1,temp,index,mid-temp1+1);
  32.         System.arraycopy(temp,0,arr,left,right-left+1);
  34.     }
  35. }

leetcode493 翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 

  1. class Solution {
  2.     private int count;
  3.     public int reversePairs(int[] nums) {
  4.         int len = nums.length;
  5.         merge(nums,0,len-1);
  6.         return count;
  7.     }
  8.     private void merge(int[] arr, int left, int right){
  9.         if(left<right){
  10.             int mid = left+((right-left)>>1);
  11.             merge(arr,left,mid);
  12.             merge(arr,mid+1,right);
  13.             mergeSort(arr,left,mid,right);
  14.         }
  15.     }
  16.     private void mergeSort(int[] arr,int left, int mid, int right){
  17.         int[] temp = new int[right-left+1];
  18.         int index=0;
  19.         int temp1 = left;
  20.         int temp2 = mid+1;
  21.         //计算翻转对
  22.         while(temp1<=mid&&temp2<=right){
  23.             if(arr[temp1]>2*(long)arr[temp2]){
  24.                 count+=mid-temp1+1;
  25.                 temp2++;
  26.             }else{               
  27.                 temp1++;
  28.             } 
  29.         }
  30.         //将temp1和temp2复原
  31.         temp1=left;
  32.         temp2=mid+1;
  33.         while(temp1<=mid&&temp2<=right){
  34.             if(arr[temp1]<=arr[temp2]){
  35.                 temp[index++]=arr[temp1++];
  36.             }else{               
  37.                 temp[index++]=arr[temp2++];
  38.             } 
  39.         }
  40.         if(temp2<=right) System.arraycopy(arr,temp2,temp,index,right-temp2+1);
  41.         if(temp1<=mid) System.arraycopy(arr,temp1,temp,index,mid-temp1+1);
  42.         System.arraycopy(temp,0,arr,left,right-left+1);
  43.     }
  44. }

剑指40 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 

  1. class Solution {
  2.     private static int INSERTION_MAX_VALUE = 7;
  3.     private static int K = 0;
  4.     public int[] getLeastNumbers(int[] arr, int k) {
  5.         K = k;
  6.         int low = 0;
  7.         int hight = arr.length-1;
  8.         quickSort(arr,low,hight);
  9.         int[] res = Arrays.copyOfRange(arr,0,k);
  10.         return res;
  11.     }
  12.     public void quickSort(int[] arr, int low, int hight){
  13.         int right = hight;
  14.         int left = low;
  15.         if(right<=left) return;
  16.         if((right-left+1)<=7){
  17.             insertSort(arr,left,right);
  18.             return;
  19.         }
  20.         int pivot = arr[left];
  21.         int i = left+1;
  22.         while(i<=right){
  23.             if(arr[i]>pivot){
  24.                 swap(arr,i,right--);
  25.             }else if(arr[i]<pivot){
  26.                 swap(arr,i++,left++);
  27.             }else{
  28.                 i++;
  29.             }
  30.         }
  31.         if(left+1>=K){
  32.             quickSort(arr,low,left-1);
  33.         }else{
  34.             quickSort(arr,low,left-1);
  35.             quickSort(arr,left+1,hight);
  36.         }
  38.     }
  39.     public void insertSort(int[] arr, int low, int hight){
  40.         for(int m = low+1;m<=hight;m++){
  41.             int temp = arr[m];
  42.             int n=m-1;
  43.             for(;n>=0;n--){
  44.                 if(arr[n]>temp){
  45.                     arr[n+1]=arr[n];
  46.                     continue; 
  47.                 }
  48.                 break;
  49.             }
  50.             arr[n+1] = temp;       
  51.         }
  52.     }
  53.     public void swap(int[] arr,int i, int j){
  54.         int temp = arr[i];
  55.         arr[i] = arr[j];
  56.         arr[j] = temp;
  57.     }    
  58. }