专栏首页开发与安全算法:快速排序以及第k小元素的线性选择算法

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

相关文章

  • 从零开始学C++之从C到C++(二):引用、数组引用与指针引用、内联函数inline、四种类型转换运算符

    一、引用 (1)、引用是给一个变量起别名 定义引用的一般格式:类型  &引用名 = 变量名; 例如:int a=1;  int  &b=a;// b是a的别...

    s1mba
  • 从零开始学C++之模板(二):类模板、Stack的类模板实现(自定义链栈方式,自定义数组方式)

    一、类模板 类模板:将类定义中的数据类型参数化 类模板实际上是函数模板的推广,可以用相同的类模板来组建任意类型的对象集合 (一)、类模板的定义 templ...

    s1mba
  • C++的引用与const指针的关系以及各种传递方式

    首先我们知道 const int *p 与 int const *p 是一样的,即 *p 是常量;而 int * const p 跟上面是不一样的,即 p 是常...

    s1mba
  • “快排”笔记

      关于排序,我想没有多少程序员会感觉陌生,信手拈来的可能就有不少:冒泡、选择或者归并等等;可在实际开发中,排序又让许多程序员感到很不熟悉,因为在大多数情况下,...

    用户2615200
  • 经典排序之 快速排序

    Author: bakari  Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

    CloudDeveloper
  • 漫画:滑动窗口系列 第二讲(无重复字符的最长子串)

    在上一节中,我们使用双端队列完成了滑动窗口的一道颇为困难的题目,以此展示了什么是滑动窗口。在本节中我们将继续深入分析,探索滑动窗口题型一些具有模式性的解法。

    程序员小浩
  • 你所能用到的数据结构(一)

         无损编码的霍夫曼编码以及其余的各种编码由于要使用比较复杂的数据结构,所以按照我昨天说的,我决定从数据结构开始写起。数据结构和算法很难完全的分开,好的数...

    一心一怿
  • Leetcode: Same Tree

    Given two binary trees, write a function to check if they are equal or not.

    卡尔曼和玻尔兹曼谁曼
  • 你所能用到的数据结构(五)

    七、骚年,这就是你的终极速度了吗? 在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算...

    一心一怿
  • 二分查找的延伸

    举个栗子:对数组序列{1,3,3,3,6}(下标从0开始)来说,若查询3,则得到L=1、R=4。 如果查询8,则得到L=R=5。 如果序列中没有x,那么L和...

    lollipop72

扫码关注云+社区

领取腾讯云代金券