Android-快速排序

迈不过友情╰ 2022-04-12 02:46 102阅读 0赞

## **算法思想：**        ##

基于分治的思想，是冒泡排序的改进型。

首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫描，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDc4MzMxNQ_size_16_color_FFFFFF_t_70][]

## ** 算法实现：** ##

public static int partition(int []array,int lo,int hi){
            //固定的切分方式
            int key=array[lo];
            while(lo<hi){
                while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                    hi--;
                }
                array[lo]=array[hi];
                while(array[lo]<=key&&hi>lo){从前半部分向后扫描
                    lo++;
                }
                array[hi]=array[lo];
            }
            array[hi]=key;
            return hi;
        }
        
        public static void sort(int[] array,int lo ,int hi){
            if(lo>=hi){
                return ;
            }
            int index=partition(array,lo,hi);
            sort(array,lo,index-1);
            sort(array,index+1,hi); 
        }

快速排序的时间复杂度为O(NlogN).

## **快速排序的优化** ##

对于基准位置的选取一般有三种方法：固定切分，随机切分和三取样切分。固定切分的效率并不是太好，随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N2).对于三数取中选择基准点是最理想的一种。

## **三数取中切分：** ##

public static int partition(int []array,int lo,int hi){
            //三数取中
            int mid=lo+(hi-lo)/2;
            if(array[mid]>array[hi]){
                swap(array[mid],array[hi]);
            }
            if(array[lo]>array[hi]){
                swap(array[lo],array[hi]);
            }
            if(array[mid]>array[lo]){
                swap(array[mid],array[lo]);
            }
            int key=array[lo];
            
            while(lo<hi){
                while(array[hi]>=key&&hi>lo){
                    hi--;
                }
                array[lo]=array[hi];
                while(array[lo]<=key&&hi>lo){
                    lo++;
                }
                array[hi]=array[lo];
            }
            array[hi]=key;
            return hi;
        }
        
        public static void swap(int a,int b){
            int temp=a;
            a=b;
            b=temp;
        }
        public static void sort(int[] array,int lo ,int hi){
            if(lo>=hi){
                return ;
            }
            int index=partition(array,lo,hi);
            sort(array,lo,index-1);
            sort(array,index+1,hi);
        }

快速排序在序列中元素很少时，效率将比较低，不然插入排序，因此一般在序列中元素很少时使用插入排序，这样可以提高整体效率。

public static void quick(int []array ,int lo,int hi){
            if(hi-lo+1<10){
                insertSort(array);
            }else{
                quickSort(array,lo,hi);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDc4MzMxNQ_size_16_color_FFFFFF_t_70]: /images/20220412/b3be9206d08548159162fdc089581c47.png