LeetCode：排序

快速排序

lass Solution {public int[] sortArray(int[] nums) {quckSort(nums,0,nums.length-1);return nums;}public void quckSort(int[] nums,int left,int right){if(left<right){int mid = partition(nums,left,right);quckSort(nums,left,mid-1);quckSort(nums,mid+1,right);}}public int partition(int[] nums,int left,int right){int pivot = nums[left];while(left<right){while(left<right&&nums[right]>pivot)right--;if(left<right)nums[left++]=nums[right];while(left<right&&nums[left]<pivot)left++;if(left<right)nums[right--] = nums[left];}nums[left] = pivot;return left;}
}

归并排序

class Solution {//暂存每次有序合并的结果，然后赋值到原来的nums数组使其有序int[] temp;public int[] sortArray(int[] nums) {temp = new int[nums.length];merge(nums,0,nums.length-1);return nums;}public void merge(int[] nums,int left,int right){if(left>=right)return;int mid = (left+right)/2;merge(nums,left,mid);merge(nums,mid+1,right);int i=left,j=mid+1,k=0;while(i<=mid&&j<=right){if(nums[i]<=nums[j])temp[k++]=nums[i++];elsetemp[k++]=nums[j++];}while(i<=mid)temp[k++]=nums[i++];           while(j<=right)temp[k++]=nums[j++];    for(i=0;i<k;i++){nums[left+i]=temp[i];}return;}}

堆排序

class Solution {public int[] sortArray(int[] nums) {int length = nums.length;heapify(nums);for(int i=length-1;i>=0;i--){swap(nums,0,i);adjustDown(nums,0,i-1);}return nums;}//将整个数组形成最大堆public void heapify(int[] nums){for(int i=nums.length/2;i>=0;i--){adjustDown(nums,i,nums.length-1);}}//将不符合条件的元素，下沉到合适位置public void adjustDown(int[] nums,int k,int n){//下标为k的元素，使其满足最大堆的要求 k的两个孩子下标 2*k+1,2*k+2while(2*k+1<=n){int child = 2*k+1;if(child+1<=n&&nums[child+1]>nums[child]){child++;}if(nums[child]>nums[k]){swap(nums,k,child);k = child;}else{break ;}}}public void swap(int[] nums,int i,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}

选出第K大元素

利用最小堆，初始化构建K个元素的最小堆，堆顶元素是最小的。新的元素去和堆顶元素比较，如果比他大则替换掉，这样最后留下了前K个最大的元素，而堆顶就是第K大的元素。

class Solution {public int findKthLargest(int[] nums, int k) {heapify(nums,k-1);for(int i=k;i<nums.length;i++){if(nums[i]>nums[0]){swap(nums,0,i);adjustDown(nums,0,k-1);}}return nums[0];}//将整个数组k下标前的元素，形成最小堆public void heapify(int[] nums,int k){for(int i=(k-1)/2;i>=0;i--){adjustDown(nums,i,k);}}//将不符合条件的元素，下沉到合适位置public void adjustDown(int[] nums,int k,int n){//下标为k的元素，使其满足最大堆的要求 k的两个孩子下标 2*k+1,2*k+2while(2*k+1<=n){int child = 2*k+1;if(child+1<=n&&nums[child+1]<nums[child]){child++;}if(nums[child]<nums[k]){swap(nums,k,child);k = child;}else{break ;}}}public void swap(int[] nums,int i,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

冒泡排序

public void bubbleSort(int[] nums){int length = nums.length;boolean flag = false;for(int i=1;i<length;i++){for(int j=0;j<length-i;j++){if(nums[j]>nums[j+1]){swap(nums,j,j+1);flag = true;}}if(!flag){break;}}
}
public void swap(int[] nums,int i,int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
}