算法:快速排序以及第k小元素的线性选择算法

简要介绍下快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。时间复杂度为O(nlogn)

一.《data structure and algorithm analysis in c》中的实现,测试过,觉得该说明的已经注释

#include<stdio.h>
#define LEN 15
#define CUTOFF 3
//用c++则可以写成引用
void swap(int *const p1, int *const p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
//插入排序
void insertion_sort(int a[], int n)
{
    int i, j;
    int tmp;
    for (i = 1; i < n; i++)
    {
        tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

// return median of left, center, and right
// order these and hide the pivot
int median3(int a[], int left, int right)
{
    int center = (left + right) / 2;
    if (a[left] > a[center])
        swap(&a[left], &a[center]);
    if (a[left] > a[right])
        swap(&a[left], &a[right]);
    if (a[center] > a[right])
        swap(&a[center], &a[right]);
    //  invariant: a[left] <= a[center] <= a[right]
    swap(&a[center], &a[right - 1]);   //将中位数作为pivot且放置在right-1处
    return a[right - 1];                        //返回pivot
}

void qsort(int a[], int left, int right)
{
    int i, j, pivot;
    if (left + CUTOFF <= right)
    {
        //因为要递归调用,如果不截断判断则会导致数组访问越界进而出现段错误
        // left, left+1, ..., right-2, right-1, right 最极限的情况就是保证
        // left与right中间至少有一个值,即CUTOFF最小要等于2,否则出现段错误
        // CUTOFF=2保证可以取中位数
        // 当CUTOFF=1时不出现段错误,但运行结果是错误的
        pivot = median3(a, left, right);
        i = left;
        j = right - 1;
        for (; ;)
        {
            while (a[++i] < pivot) {} //median函数已经比较了left和right,pivot当前位置为right-1
            while (a[--j] > pivot) {} //故从left+1和right-2开始比较
            if (i < j)
                swap(&a[i], &a[j]);
            else
                break;
        }
        swap(&a[i], &a[right - 1]); //now i is the pivot index in the array
        qsort(a, left, i - 1);
        qsort(a, i + 1, right);
    }
    else   // do an insertion sort on the subarray
        insertion_sort(a + left, right - left + 1);
}

int main(void)
{
    int i;
    int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
                    32, 28, 432, 641, 4365, 345, 624
                   };
    qsort(arr, 0, LEN - 1);
    for (i = 0; i < LEN; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

二.不对pivot进行中位数取值的简易版本

#include<stdio.h>
#define LEN 15

void swap(int *const p1, int *const p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void qsort(int a[], int left, int right)
{
    int i, j, pivot;
    pivot = a[right];   //the last item as pivot
    i = left;
    j = right - 1;
    if (left < right)
    {
        for (; ;)
        {
            for (; a[i] < pivot; i++);
            for (; a[j] > pivot; j--);
            if (i < j)
                swap(&a[i], &a[j]);
            else
                break;
        }
        swap(&a[i], &a[right]);   //now i is the pivot index in the array
        qsort(a, left, i - 1);
        qsort(a, i + 1, right);
    }
}

int main(void)
{
    int i;
    int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
                    32, 28, 432, 641, 4365, 345, 624
                   };
    qsort(arr, 0, LEN - 1);
    for (i = 0; i < LEN; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

三.根据简易快速排序得出的第k小选择算法

#include<stdio.h>
#define LEN 15
#define K 6


void swap(int *const p1, int *const p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

int  qsort(int k, int a[], int left, int right)
{
    int i, j, pivot;
    pivot = a[right];
    i = left;
    j = right - 1;
    for (; ;)
    {
        for (; a[i] < pivot; i++);
        for (; a[j] > pivot; j--);
        if (i < j)
            swap(&a[i], &a[j]);
        else
            break;
    }
    swap(&a[i], &a[right]);  //now i is the pivot index in the array
    //i.e. a[i] is the (i+1)th smallest item
    if (k == i - left + 1)
        return a[i];
    else if (k < i - left + 1)
        return qsort(k, a, left, i - 1); //target before pivot
    else                                           //target after  pivot
        return qsort((k - (i - left + 1)), a, i + 1, right);
}

int main(void)
{
    int arr[LEN] = {43, 423, 13, 6, 34, 64, 24, 69,
                    32, 28, 432, 641, 4365, 345, 624
                   };
    printf("%d\n", qsort(K, arr, 0, LEN - 1));
    return 0;
}

四.中位数之第k小的线性选择算法

实现该算法的步骤如下:

    1.如果n是一个比较小的数,比如n<6,那么只需要对此无序数组进行排序后,即可很容易的得到第K小元素。

此时约束时间T=7。

    2.如果n>5,那么我们将这个无序数组分成五组。此时约束时间T=n/5。

    3.找出每组的中位数,构成集合M。此时的约束时间T=7n/5.

    4.递归的调用selection(M,|M|/2)算法查找上一步中所有中位数的中位数,设为m。此时的约束时间

T=T(n/5)。

    5.用m来分割此时的数组,比较m与其他的(n-1)个数,小于m的数置于左集合L,大于m的数置于右集合R。当

然,中位数m的下标r=|L|+1(|L|是左集合L的个数)。此时的约束时间T=T(n)。

    如果r=k,那么返回m。

    如果r<k,那么在小于m的左集合L中递归查找第K小数。

    如果r>k,那么在大于m的右集合R中递归查找第K小数。

-----------------------------------------------------------------------------------------------------------------------------------------

参考:http://bbs.chinaunix.net/thread-116218-1-1.html

          http://blog.csdn.net/fengchaokobe/article/details/6784721

          http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=82

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏汪毅雄的专栏

Android 7.0 中 Service bind 流程详解

我们知道,Android 启动 Service 有两种方式,startService 和 bindService。本文主要讲述Service bind 过程的最...

1.1K1
来自专栏Java成神之路

hbase_异常_03_java.io.EOFException: Premature EOF: no length prefix available

更改了hadoop的配置文件:core-site.xml  和   mapred-site.xml  之后,重启hadoop 和 hbase 之后,发现hbas...

1033
来自专栏成长道路

SparkStreaming小例子

1.安装nc才可以打开端口 rpm -ivh /media/CentOS_6.7_Final/Packages/nmap-5.51-4.el6.x86_64....

2030
来自专栏生信技能树

GATK4的gvcf流程

得到了它们的bam文件,也是走的GATK流程,这里就不多说了。本教程首发于生信技能树VIP论坛:https://vip.biotrainee.com/d/423...

1663
来自专栏Golang语言社区

【Go 语言社区算法课程 第一季 第3节 hash算法实现

package main import ( "fmt" ) // 主函数 func main() { fmt.Pri...

3477
来自专栏全栈之路

android 多渠道打包

783
来自专栏乐沙弥的世界

Percona XtraDB Cluster添加仲裁节点

Galera Arbitrator是Percona XtraDB集群的成员,用于投票,以防您拥有少量服务器(通常为两个)并且不希望添加更多资源。Galera仲裁...

1152
来自专栏别先生

一脸懵逼加从入门到绝望学习hadoop之 org.apache.hadoop.ipc.RemoteException(org.apache.hadoop.security.AccessControlE

1:初学hadoop遇到各种错误,这里贴一下,方便以后脑补吧,报错如下: 主要是在window环境下面搞hadoop,而hadoop部署在linux操作系统上面...

23010
来自专栏乐沙弥的世界

MHA 在线切换过程

    MySQL MHA 在线切换是MHA除了自动监控切换换提供的另外一种方式,多用于诸如硬件升级,MySQL数据库迁移等等。该方式提供快速切换和优雅的阻塞写...

1401
来自专栏xcywt

一个简单的双向链表(C++实现)

直接上代码,亲测有用。 #ifndef __DLINK_H__ #define __DLINK_H__ /* [phead] -> [index0] -...

19410

扫码关注云+社区