快速排序中的分割算法的解析与应用-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

快速排序中的分割算法的解析与应用

简介:

一,分割(partition)算法介绍

所谓分割算法,先选定一个枢轴元素,然后 将数组中的元素分成两部分:比枢轴元素小的部分都位于枢轴元素左边;比枢轴元素大的部分都位于枢轴元素右边

此时,枢轴元素在数组中的位置就被“永久地确定”下来了---将整个数组排序,该枢轴元素的位置不会变化。

另外,枢轴元素的选取对分割算法至关重要。一般而言,终极追求的是:将数组平分。因此,尽可能地让枢轴元素的选取随机化和靠近中位数。

这里采用“三数取中”法选取枢轴元素。

关于快速排序排序算法,可参考:http://www.cnblogs.com/hapjin/p/5518922.html

 

二,分割算法的实现

复制代码
 1 //分割数组,将数组分成两部分. 一部分比pivot(枢轴元素)大,另一部分比pivot小
 2     private static int parition(int[] arr, int left, int right){
 3         
 4         int pivot = media3(arr, left, right);
 5         int i = left;
 6         int j = right - 1;//注意 ,在 media3()中 arr[right-1]就是 pivot
 7         
 8         for(;;)
 9         {
10             while(arr[++i] < pivot){}
11             while(arr[--j] > pivot){}
12             if(i < j)
13                 swap(arr, i, j);
14             else
15                 break;
16         }
17         
18         swap(arr, i, right-1);//restore pivot, 将枢轴元素放置到合适位置:arr左边元素都比pivot小,右边都比pivot大
19         return i;// 返回 pivot的 索引
20     }
复制代码

①第4行,枢轴元素是通过“三数取中”法选择的。在“三数取中”时,还做了一些优化:将 枢轴元素 放到 数组末尾的倒数第二个位置处。具体参考 media3()
需要注意的是:当输入的数组中长度为1 或者 2 时, partition会出现向下越界(但对快排而言,当数组长度很小的,其实可以不用 partition,而是直接用插入排序)。因此,可加入以下的修改。

复制代码
 1 //分割数组,将数组分成两部分. 一部分比pivot(枢轴元素)大,另一部分比pivot小
 2     private static int parition(int[] arr, int left, int right){
 3         
 4         int pivot = media3(arr, left, right);
 5         int i = left;
 6         int j = right - 1;//注意 ,在 media3()中 arr[right-1]就是 pivot
 7         
 8         //应对特殊情况下的数组,比如数组长度 小于3
 9         if(i >= j)
10             return i;
11         
12         for(;;)
13         {
14             while(arr[++i] < pivot){}
15             while(arr[--j] > pivot){}
16             if(i < j)
17                 swap(arr, i, j);
18             else
19                 break;
20         }
21         
22         swap(arr, i, right-1);//restore pivot 将枢轴元素放置到合适位置:arr左边元素都比pivot小,右边都比pivot大
23         return i;// 返回 pivot的 索引
24     }
复制代码

 

再来看看,三数取中算法,这里也有个特殊情况:当数组中元素个数都没有3个时....怎么办?

复制代码
 1     //三数取中,用在快排中随机选择枢轴元素时
 2     private static int media3(int[] arr, int left, int right){
 3         if(arr.length == 1)
 4             return arr[0];
 5         
 6         if(left == right)
 7             return arr[left];
 8         
 9         int center = (left + right) / 2;
10         
11         //找出三个数中的最小值放到 arr[left]
12         if(arr[center] < arr[left])
13             swap(arr, left, center);
14         if(arr[right] < arr[left])
15             swap(arr, left, right);
16         
17         //将 中间那个数放到 arr[media]
18         if(arr[center] > arr[right])
19             swap(arr, center, right);
20         
21         swap(arr, center, right-1);//尽量将大的元素放到右边--将privot放到右边, 可简化 分割操作(partition).
22         return arr[right-1];//返回中间大小的那个数
23     }
复制代码

其实,这里的“三数取中”的实现,与参考资料中提到的三数取中实现有一点不同。这是正常的,毕竟实现细节不同。如果有错误,需要自行调试。

这里提下第3-7行的两个if语句:当需要 “取中”的目标数组长度为1时,或者说 对数组中某些范围内[left, right]的元素进行“取中”时,若left=right,则根本就没有3个数,违背了“三数取中”的本意(随机地选取枢轴元素),故直接 return。

当数组中元素只有一个时,第18行会越界。为了防止这种情况,在第3-4行就先对数组长度进行判断。当数组中只有两个元素,其实就相当于 center=left,因此,程序也没问题。

 

三,分割算法的应用

给定一个数组,数组中某个元素出现的次数超过了数组大小的一半,找出这个元素。

比如输入:[2,5,4,4,5,5,5,6,5] ,输出 5

这个问题,其实可以转化成求解中位数问题。因为,当数组有序时,出现次数超过一半的那个元素一定位于数组的中间。

所谓中位数,就是 假设 数组是有序的情况下,中间那个元素。即 arr[arr.length/2]

而要求解中位数,当然可以先对数组进行排序,但排序的时间复杂度为O(NlogN),那有没有更快的算法?

当然是有的。就是借助partition分割算法 来 实现。

复制代码
 1 //找出 arr 中 第  n/2  大的那个元素
 2     public static int media_number(int[] arr){
 3         int left = 0;
 4         int right = arr.length - 1;
 5         int center = (left + right) / 2;
 6         
 7         int pivot_index = parition(arr, left, right);//枢轴元素的索引
 8         
 9         while(pivot_index != center)
10         {
11             if(pivot_index > center){
12                 right = pivot_index - 1;
13                 pivot_index = parition(arr, left, right);
14             }
15             else{
16                 left = pivot_index + 1;
17                 pivot_index = parition(arr, left, right);
18             }
19         }
20         return arr[center];
21     }
复制代码

上面算法不仅可以求解“找出超过一半的数字”,也可以求解任何一个数组的中位数。

这里递归表达式 T(N)=T(N/2)+O(N),O(N)表示将数组 分成两部分所花的代价。

故时间复杂度为O(N)

 

四,参考资料

排序算法总结之快速排序

 整个完整代码

复制代码
public class Middle_Large {
    
    //找出 arr 中 第  n/2  大的那个元素
    public static int media_number(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        int center = (left + right) / 2;
        
        int pivot_index = parition(arr, left, right);
        
        while(pivot_index != center)
        {
            if(pivot_index > center){
                right = pivot_index - 1;
                pivot_index = parition(arr, left, right);
            }
            else{
                left = pivot_index + 1;
                pivot_index = parition(arr, left, right);
            }
        }
        return arr[center];
    }
    
    //分割数组,将数组分成两部分. 一部分比pivot(枢轴元素)大,另一部分比pivot小
    private static int parition(int[] arr, int left, int right){
        
        int pivot = media3(arr, left, right);
        int i = left;
        int j = right - 1;//注意 ,在 media3()中 arr[right-1]就是 pivot
        
        //应对特殊情况下的数组,比如数组长度 小于3
        if(i >= j)
            return i;
        
        for(;;)
        {
            while(arr[++i] < pivot){}
            while(arr[--j] > pivot){}
            if(i < j)
                swap(arr, i, j);
            else
                break;
        }
        
        swap(arr, i, right-1);//restore pivot 将枢轴元素放置到合适位置:arr左边元素都比pivot小,右边都比pivot大
        return i;// 返回 pivot的 索引
    }
    
    
    //三数取中,用在快排中随机选择枢轴元素时
    private static int media3(int[] arr, int left, int right){
        if(arr.length == 1)
            return arr[0];
        
if(left == right)
return arr[left];
int center = (left + right) / 2; //找出三个数中的最小值放到 arr[left] if(arr[center] < arr[left]) swap(arr, left, center); if(arr[right] < arr[left]) swap(arr, left, right); //将 中间那个数放到 arr[media] if(arr[center] > arr[right]) swap(arr, center, right); swap(arr, center, right-1);//尽量将大的元素放到右边--将privot放到右边, 可简化 分割操作(partition). return arr[right-1];//返回中间大小的那个数 } private static void swap(int[] arr, int left, int right){ int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; } public static void main(String[] args) { int[] arr = {5,6,8,4,1,5,5,5,5}; int result = media_number(arr); System.out.println(result); } }
复制代码本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/p/5587014.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: