1. 先比较下各种排序的优劣

转载网上的文章

image.png

2. 快速排序思想

2.1分治法

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

2.2 主要思路

以一个数字为锚点，例如初始时取第一个数字。设两个指针分别指向数组的头和尾，然后依次移动指针，至两指针重合时，退出本次循环。

 public static void main(String[] args) {
            int[] arr = {22,6,22,3,9,34,27,18,28,87,12,33};
            qsort(arr, 0, arr.length-1);
            for (int i = 0; i < arr.length; i++) {
                System.out.println(arr[i]);
            }
        }

     public static int[] qsort(int arr[],int start,int end) {        
            int pivot = arr[start];        
            int i = start;        
            int j = end;        
            while (i < j) {            
                while ( (i<j) && (arr[j] > pivot)) {                
                    j--;            
                }            
                while ( (i<j) && (arr[i] < pivot)) {                
                    i++;            
                }            
                
                if ((arr[i] == arr[j]) && (i<j)) {                
                    i++;            
                } else {                
                    int temp = arr[i];                  
                    arr[i] = arr[j];                
                    arr[j] = temp;            
                }        
            }        
            if ( i - 1 > start) arr = qsort(arr, start, i-1);        
            if (j + 1 < end) arr = qsort(arr, j+1, end);        
            return (arr);    
        }    

3 示意图

快速排序.png