原 初学算法-快速排序与线性时间选择(De

    快速排序算法其实只做了两件事:寻找分割点(pivot)和交换数据。

    所谓寻找分割点,既找到一个预计会在中间位置附近的点,当然尽量越接近中点越好。

    所谓交换数据,就是把比这个分割点小的数据,最终都放在分割点左边,比它大的都放在右边。

    设要排序的数组是A[left]……A[right],首先任意选取一个数据(一般算法:使用随机数选取一个区间内的数。 文艺算法:取A[left]、A[right]和A[rand()]的中值。 二笔算法:选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

快速排序的具体算法是:

1)设置两个变量i、j,排序开始的时候:i=left,j=left+1;

2)取关键数据和A[left]交换,赋值给key,即key=A[left];

3)从j开始向后搜索,即由前开始向后搜索(j++),找到第一个小于key的A[j],将A[++i]和A[j]互换。

4)重复第3步,直到 j>right,此时循环结束

5)此时令 int q=i;在A[left]...A[q-1]和A[q+1]...A[right]上重复1-4过程直到递归结束。

    这样,我们就可以将它兑现为代码:

/**
 * The Quick Sort Algorithm by C++
 * Average Time Cost: nlogn
 * Author: Zheng Chen / Arc001
 * Copyright 2015 Xi'an University of Posts & Telecommunications
 */
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <fstream>
using namespace std;
long long ans = 0;

void swap(int &a, int &b)
{
    int c = a;
    a = b;
    b = c;
}

int partition(int A[],int l,int r)
{
    int t = rand()%(r-l);
	int x = A[l+t];
	int i = l;
	int j = l+1;

	swap(A[l+t],A[l]);

	for(;j<=r;j++){
		if(A[j]<=x){
			++i;
			swap(A[i],A[j]);
		}
	}

	swap(A[i],A[l]);
	return i;
}


void Quick_Sort(int A[],int l,int r)
{
    if(l<r){
        int q = partition(A,l,r);
        Quick_Sort(A,l,q-1);
        Quick_Sort(A,q+1,r);
    }
}

int main()
{
    /*int A[] = {7,6,5,4,3,2,1};
    Quick_Sort(A,0,6);
    for(int i=0;i<7;i++)
    	cout<<A[i]<<' ';
    */
    fstream in;
    in.open("QuickSort.txt");
    int *A = new int[10000];
    int i = 0;
    for(i=0;i<10000;i++)
        in>>A[i];
    Quick_Sort(A,0,9999);
    for(i=0;i<10;i++)
        cout<<A[i]<<' ';
    return 0;
}

    现在我们来看一个问题:如何找出数组A中的第 k 小的元素? (1<=k<=n)

    在笔者看来,至少有以下三种方法:

     比如我们可以分为两种情况:k>n/2时,问题化为找到第 n-k 大的元素。我们可以构造一个长度为 n-k 的数组,然后维持这个数组的单调性。这样每一个元素都可以进来数组“打擂”,找到合适的位置。到了最后我们取数组的首元素或者末元素(具体要看聪明的你选用递增还是递减),就是答案了。

    当k<=n/2时,也是同样的道理。

    很容易看到,这种算法的时间复杂度在O(n^2),实在无法令人满意。

    但是,Can we do better?

    是的,我们可以通过维持一个堆来加速,由于堆的优秀的特性,我们可以把时间复杂度降低到O(nlogn)

    我们还可以先将这些元素排序,再取出A[k-1]即可,时间复杂度也是O(nlogn)。

    还是那个问题,Can we do better?

    可以。

    还记得快速排序的算法吗?我们进行一次partition操作后,我们的分割点(pivot)元素一定“归位”了。我们再比较分割点元素和待查找元素的大小,就可以舍去左边或右边部分,只看剩下那部分。可以证明,这种算法的平均时间复杂度为Θ(n)。

    我们可以很容易的将其兑现为代码:

/**
 * Find out the n th smallest number in an array.
 * Coursera : Algorithms: Design and Analysis, Part 1 by Tim Roughgarden
 * Average Time Cost : θ(n)
 * Worst Time Cost: O(n^2) when every time the smallest number was chosen.
 *
 * Author: Zheng Chen / Arclabs001
 * Copyright 2015 Xi'an University of Posts & Telecommunications
 */
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

void swap(int &a, int &b)
{
    int c = a;
    a = b;
    b = c;
}

int partition(int A[],int l,int r)
{
    int t = rand()%(r-l);
    int x = A[l+t];
    int i = l;
    int j = l+1;

    swap(A[l+t],A[l]);

    for(;j<=r;j++){
	if(A[j]<=x){
	    ++i;
	    swap(A[i],A[j]);
	}
    }

    swap(A[i],A[l]);
    return i;
}

int Quick_Sort(int A[],int l,int r, int target)
{
    if(target > r)
        return -1;
    if(l<r){
        int q = partition(A,l,r);
        if(q==target)
        	return A[q];
        else if(q>target)
        	return Quick_Sort(A,l,q-1,target);
        else
        	return Quick_Sort(A,q+1,r,target);
    }
    else return A[l];
}
int main()
{
    int A[] = {3,4,6,1,5,9,2,8,7};
    int n;
    for(int i=0;i<9;i++)
        cout<<A[i]<<' ';
    cout<<endl;
    cin>>n;

    cout<<"The "<<n<<"th largest number in the array is: "<<Quick_Sort(A,0,8,n-1);
    return 0;
}

    进阶篇:

    但是,这种实现也有缺点:可能我们就是点背,每次选的元素,不是待排序元素的最小值、就是最大值。这样我们每次只能排除一个元素,而每次操作的代价都是O(n),因此算法的最坏时间复杂度可能达到O(n^2)。

    还是那个问题,Can we do better?

    Yes.

    我们如果能让分割点在在数组中至少为 2n/3 大,且不大于 n/3 个元素(就是排序后的位置应该在中间的1/3),这样每次我们至少可以排除 n/3 个元素。T(n) <= T(2n/3) + O(n),解得 T(n) = O(n)。

    那么,我们如何做到这点呢?

    这里有一个解法:

        1.我们准备 upper(n/5) 个长度为5的数组,把A中所有元素“装进去”。

        2.使用低级排序把它们分别排序,由于每次只有5个元素,因此低级排序更快。然后取每组第三个元素(中间元素)放到另一个数组Sub中。

        3.对长度为n/5的Sub数组,调用主算法查找第n/10大的数。

    可以证明,尽管可能看起来有些复杂,但是每次确实只需要O(n)的时间代价即可查找到适合的分割点、并至少能舍弃 n/3 个一定不符合条件的元素,达到我们对时间复杂度的需求。

    当然不能忘了代码实现:

/**
 * Deterministic Selection Algorithm in C++
 * Below is the pseudo-code
 * Coursera : Algorithms: Design and Analysis, Part 1 by Tim Roughgarden
 * Time cost: O(n)
 * Author: Zheng Chen / Arclabs001
 * Copyright 2015 Xi'an University of Posts & Telecommunications
 */
#include <iostream>

using namespace std;

int Quick_Sort(int A[],int l,int r, int target);

void swap(int &a, int &b)
{
    int c = a;
    a = b;
    b = c;
}

void insersion_sort(int A[] , int len)
{
	for(int j = 1; j<len; j++){
		int i = j -1;
		int key = A[j];
		while(i>0 && A[i] > key){
			A[i+1] = A[i];
			i--;
		}
		A[i+1] = key;
	}
}

int ChoosePivot(int A[], int l, int r)
{
	int size = r-l+1;
	int sub_num = size/5 ;
	int i, j, k=0;
	int tmp[sub_num][5];
	int Sub[sub_num];

	for(i=0; i<sub_num; i++){
		for(j=0; i<5; j++)
			tmp[i][j] = A[k++];
		Sub[i] = Quick_Sort(tmp[i], 0, 4, 2);
	}

	return Quick_Sort(Sub , 0, sub_num-1, sub_num/2);
}

int partition(int A[],int l,int r,int M)
{
	int x = A[M];
	int i = l;
	int j = l+1;

	swap(A[M],A[l]);

	for(;j<=r;j++){
		if(A[j]<=x){
			++i;
			swap(A[i],A[j]);
		}
	}

	swap(A[i],A[l]);
	return i;
}

int Quick_Sort(int A[],int l,int r, int target)
{
    if(target > r)
        return -1;
    if(l<r){
    	if( r-l+1 <10){
			int tmp[r-l+1];
			for(int i=l;i<r-l+1;i++)
				tmp[i] = A[i];
			insersion_sort( tmp , r-l+1 );
			return tmp[target];
		}

		int M = ChoosePivot(A,l,r);

        int q = partition(A,l,r,M);

        if(q==target)
        	return A[q];
        else if(q>target)
        	return Quick_Sort(A,l,q-1,target);
        else
        	return Quick_Sort(A,q+1,r,target);
    }
    else return A[l];
}

int main()
{
    int A[] = {3,4,6,1,5,9,2,8,7};
    int n;
    for(int i=0;i<9;i++)
        cout<<A[i]<<' ';
    cout<<endl;
    cin>>n;

    cout<<"The "<<n<<"th largest number in the array is: "<<Quick_Sort(A,0,8,n-1);
    return 0;
}
/**
 *  select(L,k)
    {
    if (L has 10 or fewer elements)
    {
        sort L
        return the element in the kth position
    }

    partition L into subsets S[i] of five elements each
        (there will be n/5 subsets total).

    for (i = 1 to n/5) do
        x[i] = select(S[i],3)

    M = select({x[i]}, n/10)

    partition L into L1<M, L2=M, L3>M
    if (k <= length(L1))
        return select(L1,k)
    else if (k > length(L1)+length(L2))
        return select(L3,k-length(L1)-length(L2))
    else return M
    }
 */

本文参考资料:

[1].Coursera : Algorithms: Design and Analysis, Part 1 by Tim Roughgarden   (斯坦福大学算法课)

         [2].《Introduction to Algorithms》 by  Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein. Chapter 7, Quick Sort and Chapter 9, Medians and Order Statics.

        [3].ICS 161 : Design and Analysis of Algorithms. Lecture notes for Jan 30th, 1996.  http://www.ics.uci.edu/~eppstein/161/960130.html

        如果您觉得本文对您有些许帮助,欢迎收藏和转发本文!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

36240
来自专栏程序员互动联盟

程序员必须要掌握的十大经典算法

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

435130
来自专栏潇涧技术专栏

Problem: Delete Number Problem

这题可以使用贪心策略,每次从高位向低位数,删除高位比低位数字小的那位上的数字,直到删除了k位之后,得到的数字肯定是最大值。

9320
来自专栏CSDN技术头条

程序员都应该知道的10大算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。

12610
来自专栏华章科技

程序员必须知道的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,...

11720
来自专栏osc同步分享-java技术分享站

算法基础

分治法的基本思想: 将一个规模为 n 的问题分解为 k 各规模较小的子问题, 这些子问题互相独立且与原问题是同类型问题。 递归地解这些子问题, 然后把各个子问题...

41190
来自专栏华章科技

程序员必须知道的十大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

9720
来自专栏数据结构与算法

2017.7.21夏令营清北学堂解题报告

预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票! T1: 题目描述 从前有一个?...

28760
来自专栏随笔小哥哥

程序员必须知道的10大基础实用算法及其讲解:排序、查找、搜索和分类等

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

7000
来自专栏数据小魔方

求和函数系列——sum函数家族

今天要跟大家分享的是一组求和函数系列——sum函数家族! excel中最长用到的求和函数就是sum函数系列了,sum函数系列一共有三组函数: sum sumif...

29240

扫码关注云+社区

领取腾讯云代金券