归并排序和高效排序的衍生难点,火速排序中的

作者: 网络工程  发布:2019-09-06
取数组中第n大的元素

取数组中第n大的元素这个问题,相信大家在学习数据结构这门课中都遇到过。通常我们会使用某一排序算法先将数组排序,然后在来找数组中第n大的元素。此时,数组中第n大的元素其在数组中的位置也为第n个。

利用这一思想,我们可以使用快速排序算法来将该求解算法的时间复杂度变为O。为什么呢?在快速排序算法中,每一趟快速排序都会确定一个元素的位置,例如:假设现在基准为5,经过一趟快速排序后,我们知道在第五个元素之前的元素都小于5,在第五个元素之后的元素都大于5,这时我们不就确定了元素为5在数组中的位置吗?

我们先使用第一种方法来求解数组中第n大的元素,即先排序再找第n大的元素,其基本代码如下:

// 3-路快速排序算法void __quickSort(int arr[], int l, int r) { if (l >= r) return; swap(arr[l], arr[rand() % (r - l + 1) + l]); int v = arr[l]; // arr[l+1...lt] < v int lt = l; // arr[gt...r] > v int gt = r + 1; // arr[lt+1...i) == v int i = l + 1; while (i < gt) { if (arr[i] < v) { swap(arr[i], arr[lt + 1]); lt++; i++; } else if (arr[i] > v) { swap(arr[i], arr[gt - 1]); gt--; } else { i++; } } swap(arr[l], arr[lt]); __quickSort(arr, l, lt - 1); __quickSort(arr, gt, r);}int __selection(int arr[], int n, int k) { srand(time; __quickSort(arr, 0, n - 1); return arr[k];}// 寻找arr数组中第k大的元素int selection(int arr[], int n, int k) { // 如果k >= 0 && k < n不成立,则终止程序执行 assert(k >= 0 && k < n); return __selection(arr, n, k);}

现在,我们来修改一下代码,使其成为第二种方法,其代码如下:

int __partition(int arr[], int l, int r) { swap(arr[l], arr[rand() % (r - l + 1) + l]); int v = arr[l]; // arr[l+1...lt] < v int lt = l; // arr[gt...r] > v int gt = r + 1; // arr[lt+1...i) == v int i = l + 1; while (i < gt) { if (arr[i] < v) { swap(arr[i], arr[lt + 1]); lt++; i++; } else if (arr[i] > v) { swap(arr[i], arr[gt - 1]); gt--; } else { i++; } } swap(arr[l], arr[lt]); return lt;}int __selection(int arr[], int l, int r, int k) { if  return arr[l]; int p = __partition(arr, l, r); if  return arr[p]; else if  return __selection(arr, l, p - 1, k); else return __selection(arr, p + 1, r, k);}// 寻找arr数组中第k大的元素int selection(int arr[], int n, int k) { // 如果k >= 0 && k < n不成立,则终止程序执行 assert(k >= 0 && k < n); srand(time; return __selection(arr, 0, n - 1, k);}

这样,我们就解决了求取数组中第n个大元素的问题。

注:在main()中的代码如下:

int main() { // 生成一个大小为n, 包含0...n-1这n个元素的随机数组arr int n = 10000; int *arr = TestHelper::generateOrderedArray; TestHelper::shuffleArray; // 验证selection算法, 对arr数组求第i小元素, 应该为i for (int i = 0; i < n; i++) { assert(selection(arr, n, i) == i); cout << "test " << i << " complete." << endl; } cout << "Test selection completed." << endl; delete[] arr; return 0;}

由于测试方法为遍历输出,故不贴出程序运行结果。

一,分割(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         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);
    }
}

 

本文由今晚买四不像发布于网络工程,转载请注明出处:归并排序和高效排序的衍生难点,火速排序中的

关键词:

上一篇:没有了
下一篇:没有了