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

相关文章

来自专栏python读书笔记

《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

22160
来自专栏Golang语言社区

Golang语言社区--Go语言基础第二节变量

大家好,我是社区主编cserli(或者大家叫我彬哥也可以),Golang语言社区一直致力于Go语言相关技术干货的分享,希望初学者可以少走些弯路,我...

630270
来自专栏青青天空树

成绩大排队

其中姓名和学号均为不超过10个字符的字符串,成绩为0到100之间的一个整数,这里保证在一组测试用例中没有两个学生的成绩是相同的。

9120
来自专栏CDA数据分析师

技能 | 利用SAS进行数据清洗技术——缺失值查询

数据清洗技术是统计分析之前必做的一步,而且也是非常麻烦的一步,有时甚至花费的时间比统计分析都长。所以没有一定的技巧,这将是个非常烦人的工作。本篇文章介绍如何利用...

349100
来自专栏程序员叨叨叨

5.5 类型转换

Cg 中的类型转换和 C 语言中的类型转换很类似。C 语言中类型转换可以是强制类型转换,也可以是隐式转换,如果是后者,则数据类型从低精度向高精度转换。在 Cg ...

10020
来自专栏章鱼的慢慢技术路

C语言简明数据类型指南

20470
来自专栏专知

​关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array

关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array 题目 Given an array of ...

36360
来自专栏HTML5学堂

算法之旅 | 冒泡排序法

HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

42090
来自专栏算法channel

其他|二维指针,数组指针,指针数组

望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1c++ c/c++的重要性毋庸置疑,凡是对性能要求很高的系统和算法,其中核...

35650
来自专栏轮子工厂

设计模式(四) | 简历复印与原型模型不得不说的一些事

7930

扫码关注云+社区

领取腾讯云代金券