排序算法-----快速排序

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，比另一部分的关键字大，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

时间复杂度：O(nlog2n)空间复杂度：O（1）稳定性：不稳定

单路快速排序

package 排序算法; import java.util.Arrays; import java.util.Random; //单路快速 public class QuickSort01 { public static void main(String[] args) { int []arr=new int[20]; Random random=new Random(); for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(50); } quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void quickSort(int[] arr, int l, int r) { //1.优化 if(r-l<=10){ ShellSort.shellSort(arr,l,r); return; } int p=partition(arr,l,r); quickSort(arr,l,p-1); quickSort(arr,p+1,r); } private static int partition(int[] arr, int l, int r) { int v=arr[l]; int j=l; for (int i=l+1;i<=r;i++){ if(arr[i]<v){ swap(arr,j+1,i); j++; } } swap(arr,l,j); return j; } private static void swap(int[] arr, int i, int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }

执行结果

[3, 4, 4, 6, 10, 16, 20, 21, 21, 22, 24, 24, 26, 29, 30, 38, 44, 45, 46, 48]

双路快速排序

package 排序算法; import java.util.Arrays; import java.util.Random; //双路快排 public class QuickSort02 { public static void main(String[] args) { int []arr=new int[20]; Random random=new Random(); for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(50); } quickSort02(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void quickSort02(int[] arr, int l, int r) { if (l>=r){ return; } int p=partion(arr,l,r); quickSort02(arr,l,p-1); quickSort02(arr,p+1,r); } private static int partion(int[] arr, int l, int r) { swap(arr,l,(int)(Math.random()*(r-l+1)+l)); int v=arr[l]; int i=l+1; int j=r; while(true){ while(i<=r&&arr[i]<v){ i++; } while(j>=l+1&&arr[j]>v){ j--; } if (i>j){ break; } swap(arr,i,j); i++; j--; } swap(arr,l,j); return j; } private static void swap(int[] arr, int i, int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }

执行结果

[2, 5, 6, 7, 8, 12, 18, 20, 24, 24, 28, 29, 31, 32, 37, 40, 44, 46, 48, 49]

三路快速排序

package 排序算法; import java.util.Arrays; import java.util.Random; //三路快排 public class QuickSort03 { public static void main(String[] args) { int []arr=new int[20]; Random random=new Random(); for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(50); } quickSort03(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void quickSort03(int[] arr, int l, int r) { if(l>=r){ return; } swap(arr,l,(int)(Math.random()*(r-l+1)+l)); int v=arr[l]; int lt=l; int gt=r+1; int i=l+1; while (i<gt){ if (arr[i]<v){ swap(arr,lt+1,i); lt++; i++; }else if (arr[i]>v){ swap(arr,i,gt-1); gt--; }else { i++; } } swap(arr,l,lt); quickSort03(arr,l,lt); quickSort03(arr,gt,r); } private static void swap(int[] arr, int i, int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }

执行结果

[0, 2, 3, 7, 10, 10, 12, 12, 14, 18, 21, 25, 29, 32, 32, 33, 40, 43, 45, 47]

测试

package 排序算法; import java.util.Arrays; import java.util.Random; public class TestSort { /* 数据分布情况 1.完全随机 2.大致有序 3.方差小 */ public static int[] getTotalRandom(){ Random random=new Random(); int [] arr=new int[40000]; for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(10000); } return arr; } public static void main(String[] args) { int [] arr1=getTotalRandom(); int [] arr2= Arrays.copyOf(arr1, arr1.length); int [] arr3= Arrays.copyOf(arr1, arr1.length); int [] arr4= Arrays.copyOf(arr1, arr1.length); int [] arr5= Arrays.copyOf(arr1, arr1.length); int [] arr6= Arrays.copyOf(arr1, arr1.length); int [] arr7= Arrays.copyOf(arr1, arr1.length); int [] arr8= Arrays.copyOf(arr1, arr1.length); int [] arr9= Arrays.copyOf(arr1, arr1.length); /* testSelectionSort(arr1); testBubbleSort(arr2); testInsertSort(arr3); testShellSort(arr4); testMergSort(arr5); testHeapSort(arr6);*/ testQuickSort01(arr7); testQuickSort02(arr8); testQuickSort09(arr9); } private static void testQuickSort09(int[] arr9) { long startTime=System.currentTimeMillis(); QuickSort03.quickSort03(arr9,0,arr9.length-1); long endTime=System.currentTimeMillis(); System.out.println("三路快排"+(endTime-startTime)); } private static void testQuickSort02(int[] arr8) { long startTime=System.currentTimeMillis(); QuickSort02.quickSort02(arr8,0,arr8.length-1); long endTime=System.currentTimeMillis(); System.out.println("双路快排"+(endTime-startTime)); } private static void testQuickSort01(int[] arr7) { long startTime=System.currentTimeMillis(); QuickSort01.quickSort(arr7,0,arr7.length-1); long endTime=System.currentTimeMillis(); System.out.println("单路快排"+(endTime-startTime)); } private static void testHeapSort(int[] arr6) { long startTime=System.currentTimeMillis(); HeapSort.heapSort(arr6); long endTime=System.currentTimeMillis(); System.out.println("堆排序"+(endTime-startTime)); } private static void testInsertSort(int[] arr3) { long startTime=System.currentTimeMillis(); BubbleSort.bubbleSort(arr3); long endTime=System.currentTimeMillis(); System.out.println("冒泡排序"+(endTime-startTime)); } private static void testBubbleSort(int[] arr2) { long startTime=System.currentTimeMillis(); insertionSort.lnsertionSortUpper(arr2); long endTime=System.currentTimeMillis(); System.out.println("插入排序"+(endTime-startTime)); } private static void testSelectionSort(int[] arr) { long startTime=System.currentTimeMillis(); SelectionSort.selectionSort(arr); long endTime=System.currentTimeMillis(); System.out.println("选择排序"+(endTime-startTime)); } private static void testShellSort(int[] arr) { long startTime=System.currentTimeMillis(); ShellSort.shellSort(arr); long endTime=System.currentTimeMillis(); System.out.println("希尔排序"+(endTime-startTime)); } private static void testMergSort(int[] arr) { long startTime=System.currentTimeMillis(); MergSort.mergSort(arr,0,arr.length-1); long endTime=System.currentTimeMillis(); System.out.println("归并排序"+(endTime-startTime)); } }

执行结果

单路快排7 双路快排9 三路快排8

大致有序和方差小三路会快一点