leetcode 912. 排序数组

这道题就是纯粹的数组排序问题，救助这道题复习一下各种排序算法。

选择排序 这种排序方式应该是很简单的，容易理解，对于长度为n的数组，遍历n-1次，每次在无序的数组段中选择最小的一个元素和无序数组第一个元素交换位置。或者反过来，找最大的和最后一个交换，也是一样的。在交换过程中，相同元素的位置不会变化，因此是稳定的。不过判断的方式不同，导致的稳定性也不同。比如如果我写成nums[j]<=nums[min]，那就变成不稳定的了。 时间复杂度是O(n^2) //选择排序 public void selectSort(int[] nums){ for(int i=0;i<nums.length;i++){ int min=i; for(int j=i;j<nums.length;j++){ if(nums[j]<nums[min]){ min=j; } } swap(nums,i, min); } } 冒泡排序 这种排序方式是对一个数组遍历n-1次，每次通过交换相邻两个元素位置，使得局部相对大小满足要求，每次的结果是将最大值交换到了最后位置，就像泡泡冒到最高一样。 时间复杂度是O(n^2)，稳定的。 public void bubbleSort(int[] nums){ boolean changed=false; for(int i=0;i<nums.length-1;i++){ changed=false;//做简单的优化 for(int j=0;j<nums.length-1-i;j++){ if(nums[j]>nums[j+1]){ swap(nums,j+1, j); changed=true; } } if(!changed){ break; } } } 插入排序 模拟一个插入元素的过程，在插入的过程中要找到插入的位置，使得插入之后新的数组段是有序的。在查找位置的时候，也要从后往前去遍历，因此时间复杂度也是比较高，O(n^2)，稳定的。 public static void insertSort(int[] nums){ for(int i=1;i<nums.length;i++){ int j=i-1; int target=nums[i]; while(j>=0&&nums[j]>target){ nums[j+1]=nums[j]; //将数组右移 j--; } nums[j+1]=target; //插入合适的位置 } } 希尔排序 希尔排序是插入排序的优化，将插入排序的比较间隔扩大，不再是相邻元素比较大小，比插入排序优化了一些，时间复杂度O(n^1.3-2)，因为交换的时候是跳跃式的交换，无法保证稳定，不稳定的。 public void shellSort(int[] nums) { for (int gap = nums.length/2; gap > 0; gap /= 2) { for (int i = gap; i < nums.length; ++i) { for (int j = i; j - gap >= 0 && nums[j-gap]>nums[j]; j -= gap) { swap(nums,j-gap, j); } } } } 快速排序 快速排序有多种实现方式，这里主要给出两种比较常用的，分别适合于不同的应用场景。时间复杂度O(nlogn)，因为交换元素无法保证顺序，是不稳定的。 第一种实现，左右双指针，交换逆序元素。 先选择一个标杆元素（通常是用第一个元素）。执行： 从右向左遍历找到第一个小于标杆的值，从左向右遍历找到第一个大于标杆的值，这两个位置的值是不满足顺序要求的，交换他们的值。 然后重复上面的过程。知道左右指针位置相同，将标杆元素和指针交换，此时数组分为两部分，然后递归进行排序。

注意：在一些情况下，不需要我们进行完全的排序，只需要将数组分为两部分相对有序，如查找中位数，就是将数组分为长度相同的但是大小分开的两个子数组，此时我们不需要完全排序，只需要执行上面的过程，能够降低时间复杂度。

public void quick(int[] nums, int begin, int end){ int left=begin; int right=end; if(begin>=end){ return; } int flag=nums[left];//选中一个标杆值 while(left<right){ while(left<right&&nums[right]>flag){ right--; } while(left<right&&nums[left]<=flag){ //这里加一个等于号，从最左边出发， // 不加的话，当数组个数为2时，可能会造成栈溢出 left++; } swap(nums,left,right); } swap(nums,begin, right); quick(nums,begin,left-1); quick(nums,left+1,end); }

第二种实现：两个伴随指针 在数组排序时，采用第一种实现是可以的，但是如果是对链表排序时，无法用指针随机访问每个位置，只能从链表头部从前往后遍历，此时可以采用第二种实现。 先确定一个标杆值，通常是第一个值。用两个指针，指针i和指针j，指针j用于遍历，指针i用于记录小于标杆值的边界，当j找到一个小于标杆的值时，将i和j交换，并将i向右移动，这样就能保证，遍历结束时，i左边都是小于标杆值的，右边都是大于的。

public static void quickSort(int[] nums,int begin, int end){ if(begin>end||begin==end){ return; } int i=begin+1; int j=begin+1; int target=nums[begin]; while(j<=end){ if(nums[j]<target){ swap(nums,i,j); i++; j++; }else{ j++; } } swap(nums,begin,--i); quickSort(nums,begin,i-1); quickSort(nums,i+1,end); } 归并排序 这种排序方式采用分治的思想，将原数组先拆分成小数组，分别排序之后，再将相邻的有序数组合并，还是比较好理解的。 一共拆分为logn层，每个层合并的过程O(n)，因此是O(nlogn)，可以保证稳定。 public static int[] mergeSort(int[] nums, int begin, int end){ if(begin>end){ return new int[0]; } if(begin==end){ return new int[]{nums[begin]}; } int m=begin+(end-begin)/2; int[] lres=mergeSort(nums,begin,m);//拆分为小数组，排序 int[] rres=mergeSort(nums,m+1,end); //下面来进行合并 int[] res=new int[lres.length+rres.length]; int i=0; int j=0; int index=0; while(i<lres.length&&j<rres.length){ if(lres[i]<=rres[j]){ res[index++]=lres[i++]; }else{ res[index++]=rres[j++]; } } while(i<lres.length){ res[index++]=lres[i++]; } while(j<rres.length){ res[index++]=rres[j++]; } return res; } 堆排序 堆排序写起来可能比较麻烦一些，基于数组的堆排序还是稍微简单的，如果是基于节点的就更麻烦了。 堆排序的主要操作包括建堆，调整等。 建堆是将原始数组建成一个大顶堆或者小顶堆，调整是在排序过程中，将最大值或最小值拿掉之后，剩下的元素进行调整。 建堆的时间复杂度是O(nlogn)，排序的时间复杂度是O(nlogn)，无法保证稳定性。 //堆排序 public static int[] heapSort(int[] nums) { buildHeap(nums);//建堆 int size=nums.length; for(int i=0;i<nums.length-1;i++){ swap(nums,0,size-1);//得到最大元素 size--; adjust(nums,0,size);//调整堆 } return nums; } //建一个大顶堆 public static void buildHeap(int[] arr){ for(int i=1;i<arr.length;i++){ insert(arr,i); } System.out.println(Arrays.toString(arr)); } //向堆中插入元素 public static void insert(int[] arr,int index){ int parent=0; while(index!=0){//根节点是没有父节点的 parent=(index-1)/2; if(arr[parent]<arr[index]){ swap(arr,parent,index); } index=parent; } } //从index开始调整大顶堆 public static void adjust(int[] arr, int index, int size){ int left=index*2+1; int right=index*2+2; int max=index; while(left<size){ if(arr[left]>arr[max]){ max=left; } if(right<size&&arr[right]>arr[max]){ max=right; } if(max!=index){ swap(arr,max,index); }else{ break; } index=max; left=index*2+1; right=index*2+2; } } 桶排序 桶排序的思想其实是用空间换时间，在重复元素比较多的时候用桶排序能够比较快，首先找到数组中元素的范围，在范围内设置不同的桶计数每个范围内数字的个数，然后基于桶来排序。 时间复杂度O(n)，通常的比较排序最优的时间复杂度不超过O(nlogn)，但是桶排序可以，计数排序也可以。无法保证稳定。 public int[] bucketSort(int[] nums){ if(nums==null||nums.length==0){ return nums; } int low= Integer.MAX_VALUE; int high=Integer.MIN_VALUE; for(int i=0;i<nums.length;i++){ low=Math.min(low,nums[i]); high=Math.max(high,nums[i]); } int n=high-low+1; int[] buckets=new int[n];//准备了最多数量的桶，每个值对应一个 for(int t:nums){ buckets[t-low]++; } int[] res=new int[nums.length]; int index=0; for(int i=0;i<n;i++){ for(int j=0;j<buckets[i];j++){ res[index++]=low+i; } } return res; }