算法:快速排序以及第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 条评论
登录 后参与评论

相关文章

来自专栏算法channel

算法优化|说说哨兵(sentinel value)

01 哨兵 先看下维基百科对其定义: In computer programming, a sentinel value (also referred to ...

3138
来自专栏算法channel

常用排序算法代码兑现

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

33811
来自专栏技术翻译

与机器学习算法相关的数据结构

我不认为机器学习中使用的数据结构与在软件开发的其他领域中使用的数据结构有很大的不同。然而,由于许多问题的规模和难度,掌握基本知识是必不可少的。

953
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

552
来自专栏我的博客

经典笔试题目[算法篇]

php /** * 两个已经按照从大到小排序的数组,元素个数不确定 * 仅使用一次循环,找出其中相等元素并输出(使用空格分开) */ $a = array...

26312
来自专栏python读书笔记

《算法图解》NOTE 3 递归1.定义2递归结构2.适用场合3.应用案例

1424
来自专栏aCloudDeveloper

算法导论第四章分治策略实例解析(一)

一、第三章简单回顾   中间略过了第三章, 第三章主要是介绍如何从数学层面上科学地定义算法复杂度,以致于能够以一套公有的标准来分析算法。其中,我认为只要记住三...

1859
来自专栏King_3的技术专栏

leetcode-67- Add Binary

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

洛谷P1138 第k小整数

题目描述 现有n个正整数,n≤10000,要求出这n个正整数中的第k个最小整数(相同大小的整数只计算一次),k≤1000,正整数均小于30000。 输入输出格式...

3116
来自专栏行者常至

golang string、int、int64 float 互相转换

923

扫码关注云+社区