快递排序Java

快速排序是在工具类常用的排序算法，快速排序的思想主要是选定一个基准元素，然后找到基准元素的位置，然后再分别排序他左边的和他右边的,快速排序是不稳定的，时间复杂度位Nlog(N),最极端的情况就是一个反向排好顺序的数组，然后每次二分都分不开导致的时间复杂度最高

@Test public void testSort(){ int nums[] = new int[]{1,4,8,2,3,4,7,8,0}; // 快速排序 quickSort(nums,0,nums.length-1); Arrays.stream(nums).forEach(System.out::println); } private void quickSort(int[] arr, int lo, int hi) { if(lo>=hi) return ; int partition=partition(arr,lo,hi); quickSort(arr,lo,partition-1); quickSort(arr,partition+1,hi); } private int partition(int[] arr, int lo, int hi) { //把最左边的元素当作基准值 int key=arr[lo]; int left=lo; int right=hi+1; while(true) { //左指针遇到>=key的值，才停下 while(arr[++left] < key) { if(left==hi) break; } //右指针遇到<=key的值，才停下 while(key < arr[--right]) { if(right==lo) break; } if(left>=right) { //扫描了所有元素，结束循环 break; }else { //交换左右指针 swap(arr,left,right); } } //right指向的值一定是小于或等于key值，所以交换key和右指针的值 swap(arr,lo,right); return right; } private static void swap(int[] arr, int i, int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } 总结

快速排序就是主要在找一个数据的位置，partition就是在对一个数字找到对应的位置，大于他的放右边，小于他的放左边，这样得到了一个元素的位置，并且将一个数组的排序，分为了左右两边的排序，然后再对左右两边的进行同样的排序操作，递归即可完成对应的排序