剑指offer中Partition函数讲解

算法 数据结构 快速排序

讲解初衷

      之所以要探究剑指offer上的2.4.1处快速排序的Partition函数，是因为这与我在一般数据结构书上学的不一样，下面贴出两种代码：

// 剑指offer书上的
int Partition(int[] data, int start, int end) throws Exception {
        if(data==null||data.length<=0||start<0||end>=data.length)
            throw new Exception("Invalid Parameters");
        int index=RandomInRange(start,end);  // 随机取一个标准元素
        Swap(data,index,end);  // 交换元素
        int small=start-1;
        for(int i=start;i<end;++i) {
            if(data[i]<data[end]) {
                ++small;
                if(small!=i)
                    Swap(data,i,small);  
            }
        }
        ++small;
        Swap(data,small,end);
        return small;
    }

// 一般数据结构书上的
int Partition(int[] data, int start, int end) throws Exception {
        if(data==null||data.length<=0||start<0||end>=data.length)
            throw new Exception("Invalid Parameters");
        int index=RandomInRange(start,end);  // 随机取一个标准元素
        Swap(data,index,start);  // 交换元素
        int temp=data[start];  // 保存标准元素
        int i=start,j=end;
        while(i<j){
            while(i<j&&data[i]<=temp) j--;
            if(i<j){
                data[j]=data[i];
                i++;
            }
            while(i<j&&temp<=data[j]) i++;
            if(i<j){
                data[i]=data[j];
                j--;
            }
        }
        data[i]=temp;
        return i;
    }

      很明显，这两种代码的思想不一样。下面我将谈谈这两种代码的区别。

其中区别

      使用测试数据：1,3,0,2,5。在第一个代码中，index假设取3，start=0,end=4。那么运行过程中参数变化如下表所示：

      第二种代码,也取index=3：

      可以看出，这两种思想导致的运行过程是不同的，前者是用small指代小于标准元素的最右位置，在遍历过程中进行交换操作来保证small左边都是小于标准元素的元素，而后者是用两个指针i,j分别表示大于和小于标准元素的集合边界位置，所以后者更浅显易懂。

领悟体会

      虽然这两种思想实现的算法的时间复杂度一样，但是剑指offer上的算法实现对我来说是一种新思路，值得学习，开拓眼界。