排序算法二--快速排序

比眉伴天荒 2022-05-10 14:08 174阅读 0赞

### 快速排序(Quicksort) ###

1.  **基本思想：（分治）**
    
     *  先从数列中取出一个数作为key值；
     *  将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
     *  对左右两个小数列重复第二步，直至各区间只有1个数。
2.  **辅助理解：[挖坑填数][Link 1]**
    
     *  初始时 i = 0; j = 9; key=72  
        由于已经将a\[0\]中的数保存到key中，可以理解成在数组a\[0\]上挖了个坑，可以将其它数据填充到这来。  
        从j开始向前找一个比key小的数。当j=8，符合条件，**a\[0\] = a\[8\] ; i++ ;** 将a\[8\]挖出再填到上一个坑a\[0\]中。  
        这样一个坑a\[0\]就被搞定了，但又形成了一个新坑a\[8\]，这怎么办了？简单，再找数字来填a\[8\]这个坑。  
        这次从i开始向后找一个大于key的数，当i=3，符合条件，**a\[8\] = a\[3\] ; j-- ;** 将a\[3\]挖出再填到上一个坑中。
        
            数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
             0   1   2    3    4    5    6    7    8    9
     *  此时 i = 3; j = 7; key=72  
        再重复上面的步骤，先从后向前找，再从前向后找。  
        从j开始向前找，当j=5，符合条件，将a\[5\]挖出填到上一个坑中，**a\[3\] = a\[5\]; i++;**  
        从i开始向后找，当i=5时，由于i==j退出。  
        此时，i = j = 5，而a\[5\]刚好又是上次挖的坑，因此将key填入a\[5\]。
        
            数组：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
             0   1   2    3    4    5    6    7    8    9
     *  可以看出a\[5\]前面的数字都小于它，a\[5\]后面的数字都大于它。因此再对a\[0…4\]和a\[6…9\]这二个子区间重复上述步骤就可以了。
        
            <数组：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
             0   1   2    3    4    5    6    7    8    9
3.  **平均时间复杂度：**O(N\*logN)
4.  实现（java):

public static void sort(int[] a,int low,int high){
            int start = low;
            int end = high;
            int key = a[low];
            
            
            while(end>start){
                //从后往前比较
                while(end>start&&a[end]>=key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                    end--;
                if(a[end]<=key){
                    int temp = a[end];
                    a[end] = a[start];
                    a[start] = temp;
                }
                //从前往后比较
                while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                   start++;
                if(a[start]>=key){
                    int temp = a[start];
                    a[start] = a[end];
                    a[end] = temp;
                }
            //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
            }
            //递归
            if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
            if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
        }

key值的选取可以有多种形式，例如中间数或者随机数，分别会对算法的复杂度产生不同的影响。

[Link 1]: http://blog.csdn.net/morewindows/article/details/6684558