快排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实作出来。

 使用快速排序法对一列数字进行排序的过程

本文地址:http://www.cnblogs.com/archimedes/p/quick-sort-algorithm.html,转载请注明源地址。

算法原理

快速排序采用一种“分而治之、各个击破”的观念。

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤为:

1、从数列中挑出一个元素,称为 "基准"(pivot),

2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

算法实现

C代码如下:

// Completed on 2014.10.9 19:09
// Language: C99
//
// 版权所有(C)codingwu   (mail: oskernel@126.com)
// 博客地址:http://www.cnblogs.com/archimedes/
#include <stdio.h>
#include <stddef.h>
void swap(int * a, int * b)  //交换函数
{
    int tmp = * a;
    * a = * b;
    * b = tmp;
}
void printArray(int a[], int count)   //打印数组元素
{
    int i;
    for(i = 0; i < count; i++)
        printf("%d ",a[i]);
    printf("\n");
}
size_t partition(int * ary, size_t len, size_t pivot_i) //划分函数
{
    size_t i = 0;
    size_t small_len = 0;
    int pivot = ary[pivot_i];
    swap(&ary[pivot_i], &ary[len - 1]);
     for (; i < len; i++) {
          if (ary[i] < pivot) {
            swap(&ary[i], &ary[small_len]);
              small_len++;
        }
    }
    swap(&ary[len - 1], &ary[small_len]); //交换元素
    return small_len;
}
void quick_sort(int * ary, size_t len)
{
    if (len == 0 || len == 1) return;
    size_t small_len = partition(ary, len, 0);
    quick_sort(ary, small_len);
    quick_sort(&ary[small_len + 1], len - small_len - 1);
}
int main(void)
{
    int ary[] = {2, 4, 12, 25, 13, 5, 3, 1, 7, 6};
    size_t len = sizeof(ary) / sizeof(ary[0]);
    printArray(ary, len);
    quick_sort(ary, len);
    printArray(ary, len);
    return 0;
}

C89标准在stdlib.h中定义了抽象数据类型的快速排序函数qsort:

// Completed on 2014.10.9 19:20
// Language: C99
//
// 版权所有(C)codingwu   (mail: oskernel@126.com)
// 博客地址:http://www.cnblogs.com/archimedes/
#include <stdio.h>
#include <stdlib.h>
static int cmp(const void *a,  const void *b)
{
    return *(int *)a - *(int *)b;
}
void printArray(int a[], int count)   //打印数组元素
{
    int i;
    for(i = 0; i < count; i++)
        printf("%d ",a[i]);
    printf("\n");
}
int main()
{
    int arr[10] = {5, 3, 7, 4, 1, 9, 8, 6, 2};
    size_t len = sizeof(arr) / sizeof(arr[0]);
    printArray(arr, len);
    qsort(arr, 10, sizeof(int), cmp);
    printArray(arr, len);
    return 0;
}

有关qsort函数的其他用法可以参考:《C语言中qsort函数的应用

qsort函数实现

参考minix内核代码中qsort函数的实现:

整个qsort函数实现的是通用类型,也即是使用C模拟了泛型,使用了4个辅助函数,声明如下:

static    void qsort1(char *, char *, size_t);
static    int (*qcompar)(const char *, const char *);
static    void qexchange(char *, char *, size_t);
static    void q3exchange(char *, char *, char *, size_t);

在《C语言实现泛型编程》中有介绍,要实现泛型,对于简单的元素的交换问题,实现起来必须转换为字节块的交换,这里采用的是qexchange 函数来实现,代码如下:

static void
qexchange(register char *p, register char *q,
      register size_t n)
{
    register int c;

    while (n-- > 0) {
        c = *p;
        *p++ = *q;
        *q++ = c;
    }
}

代码中还有一个增强版的交换函数q3exchange,顾名思义实现的是三个字节区域块内容的交换,代码如下:

static void
q3exchange(register char *p, register char *q, register char *r,
       register size_t n)
{
    register int c;
    while (n-- > 0) {
        c = *p;
        *p++ = *r;
        *r++ = *q;
        *q++ = c;
    }
}

原理比较简单,我就不具体解释了。

核心函数是qsort1,代码结构较为复杂,下面详细剖析:

函数原型  static void qsort1(char *, char *, size_t);

第一个参数传递数组首地址,第二个参数传递最后一个元素的首地址

函数的划分元选取的是数组中间元素:

left = a1;
right = a2;
lefteq = righteq = a1 + width * (((a2-a1)+width)/(2*width));

lefteq和righteq分别指向左右两边区域的边界,对于左边区域,实行下面的代码:

while (left < lefteq && (cmp = (*qcompar)(left, lefteq)) <= 0) {
    if (cmp < 0) {
        left += width;
    } else {
        lefteq -= width;
        qexchange(left, lefteq, width);
    }
}        

对于右边区域,实行下面的代码:

while (right > righteq) {
    if ((cmp = (*qcompar)(right, righteq)) < 0) {
        if (left < lefteq) {
            qexchange(left, right, width);
            left += width;
            right -= width;
            goto again;
        }
        righteq += width;
        q3exchange(left, righteq, right, width);
        lefteq += width;
        left = lefteq;
    } else if (cmp == 0) {
        righteq += width;
        qexchange(right, righteq, width);
    } else right -= width;
}

goto语句跳转到左边区域代码,直到左边区域元素均小于lefteq指向的元素,也即是中间元。之后left==lefteq,此时当cmp<0,此时左边已经没有空位,righteq += width操作向右移动让出一个位置,q3exchange(left, righteq, right, width)操作轮换三个位置的元素。

完整代码如下:

/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */
/* $Header: qsort.c,v 1.3 90/08/28 14:03:24 eck Exp $ */

#include    <stdlib.h>

static    void qsort1(char *, char *, size_t);
static    int (*qcompar)(const char *, const char *);
static    void qexchange(char *, char *, size_t);
static    void q3exchange(char *, char *, char *, size_t);

void
qsort(void *base, size_t nel, size_t width,
      int (*compar)(const void *, const void *))
{
    /* when nel is 0, the expression '(nel - 1) * width' is wrong */
    if (!nel) return;
    qcompar = (int (*)(const char *, const char *)) compar;
    qsort1(base, (char *)base + (nel - 1) * width, width);
}

static void
qsort1(char *a1, char *a2, register size_t width)
{
    register char *left, *right;
    register char *lefteq, *righteq;
    int cmp;

    for (;;) {
        if (a2 <= a1) return;
        left = a1;
        right = a2;
        lefteq = righteq = a1 + width * (((a2-a1)+width)/(2*width));
        /*
           Pick an element in the middle of the array.
           We will collect the equals around it.
           "lefteq" and "righteq" indicate the left and right
           bounds of the equals respectively.
           Smaller elements end up left of it, larger elements end
           up right of it.
        */
again:
        while (left < lefteq && (cmp = (*qcompar)(left, lefteq)) <= 0) {
            if (cmp < 0) {
                /* leave it where it is */
                left += width;
            }
            else {
                /* equal, so exchange with the element to
                   the left of the "equal"-interval.
                */
                lefteq -= width;
                qexchange(left, lefteq, width);
            }
        }
        while (right > righteq) {
            if ((cmp = (*qcompar)(right, righteq)) < 0) {
                /* smaller, should go to left part
                */
                if (left < lefteq) {
                    /* yes, we had a larger one at the
                       left, so we can just exchange
                    */
                    qexchange(left, right, width);
                    left += width;
                    right -= width;
                    goto again;
                }
                /* no more room at the left part, so we
                   move the "equal-interval" one place to the
                   right, and the smaller element to the
                   left of it.
                   This is best expressed as a three-way
                   exchange.
                */
                righteq += width;
                q3exchange(left, righteq, right, width);
                lefteq += width;
                left = lefteq;
            }
            else if (cmp == 0) {
                /* equal, so exchange with the element to
                   the right of the "equal-interval"
                */
                righteq += width;
                qexchange(right, righteq, width);
            }
            else    /* just leave it */ right -= width;
        }
        if (left < lefteq) {
            /* larger element to the left, but no more room,
               so move the "equal-interval" one place to the
               left, and the larger element to the right
               of it.
            */
            lefteq -= width;
            q3exchange(right, lefteq, left, width);
            righteq -= width;
            right = righteq;
            goto again;
        }
        /* now sort the "smaller" part */
        qsort1(a1, lefteq - width, width);
        /* and now the larger, saving a subroutine call
           because of the for(;;)
        */
        a1 = righteq + width;
    }
    /*NOTREACHED*/
}

static void
qexchange(register char *p, register char *q,
      register size_t n)
{
    register int c;

    while (n-- > 0) {
        c = *p;
        *p++ = *q;
        *q++ = c;
    }
}

static void
q3exchange(register char *p, register char *q, register char *r,
       register size_t n)
{
    register int c;

    while (n-- > 0) {
        c = *p;
        *p++ = *r;
        *r++ = *q;
        *q++ = c;
    }
}
时间: 2024-12-23 18:57:00

快排序算法的相关文章

桶排序算法:最快最简单的排序算法

在我们生活的这个世界中到处都是被排序过的.站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序--总之很多东西都需要排序,可以说排序是无处不在.现在我们举个具体的例子来介绍一下排序算法. 首先出场的我们的主人公小哼,上面这个可爱的娃就是啦.期末考试完了老师要将同学们的分数按照从高到低排序.小哼的班上只有5个同学,这5个同学分别考了5分.3分.5分.2分和8分,哎考的真是惨不忍睹(满分是10分).接下来将分数进行从大到小排序,排序后是8

九大排序算法总结

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 常见的内部排序算法有:插入排序.希尔排序.选择排序.冒泡排序.归并排序.快速排序.堆排序.基数排序等. 算法一:插入排序 插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入. 算法步骤 1)将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当

常见的五类排序算法图解和实现(多关键字排序:基数排序以及各个排序算法的总结)

基数排序思想 完全不同于以前的排序算法,可以说,基数排序也叫做多关键字排序,基数排序是一种借助"多关键字排序"的思想来实现"单关键字排序"的内部排序算法. 两种方式: 1.最高位优先,先按照最高位排成若干子序列,再对子序列按照次高位排序 2.最低位优先:不必分子序列,每次排序全体元素都参与,不比较,而是通过分配+收集的方式. 多关键字排序 例:将下表所示的学生成绩单按数学成绩的等级由高到低排序,数学成绩相同的学生再按英语成绩的高低等级排序.        第一个关键

JavaScript版几种常见排序算法分享

说明 ·  每个浏览器测试得出的数据会不一样.比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快. ·  不要用太大数据去测试冒泡排序(浏览器崩溃了我不管) 个人理解 ·  冒泡排序:最简单,也最慢,貌似长度小于7最优 ·  插入排序: 比冒泡快,比快速排序和希尔排序慢,较小数据有优势 ·  快速排序:这是一个非常快的排序方式,V8的sort方法就使用快速排序和插入排序的结合 ·  希尔排序:在非chrome下数组长度小于1000,希尔排序比快速更快 ·  系统

链表排序算法

包括冒泡.选择.插入.快排.归并.希尔和堆排序 以下排序算法的正确性都可以在LeetCode的链表排序这一题检测.本文用到的链表结构如下(排序算法都是传入链表头指针作为参数,返回排序后的头指针) struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 插入排序(算法中是直接交换节点,时间复杂度O(n^2),空间复杂度O(1)) class Solution { public: Li

[AS功能代码教程10] 数据结构排序算法

一.概论 对于数据的处理工作,排序是其最基本的运算之一.在当今的计算机系统中,花费在排序上的时间占系统CPU运行时间的很大比重.有资料表明,在一些商用计算机上,在排序上的CPU时间达到20%至60%.为了提高计算机的工作效率,人们提出了各种各样的排序方法和算法.这些算法有力地发展.并充分地展示了算法设计的某些重要原则和高超技巧.因此,对于计算专业人员来说掌握排序算法是十分重要的. 二.排序算法简介 本次课程中我们将介绍六种排序方法:插入排序,选择排序,冒泡排序,希尔排序,快速排序及二路归并. <

Javascript排序算法之计数排序的实例

 计数排序是一种高效的线性排序,它通过计算一个集合中元素楚翔的次数来确定集合如何排列,计数排序不需要进行数据的比较,所有他的运行效率前面介绍的都高 计数排序(Counting sort)是一种稳定的排序算法.计数排序使用一个额外的数组Count_arr,其中第i个元素是待排序数组Arr中值等于i的元素的个数.然后根据数组Count_arr来将Arr中的元素排到正确的位置. 分为四个步骤: 1.找出待排序的数组中最大和最小的元素 2.统计数组中每个值为i的元素出现的次数,存入数组Count_arr

深入排序算法的多语言实现

 1 排序的基本概念 排序: 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来.其确切定义如下: 输入:n个记录R1,R2,-,Rn,其相应的关键字分别为K1,K2,-,Kn. 输出:Ril,Ri2,-,Rin,使得Ki1≤Ki2≤-≤Kin.(或Ki1≥Ki2≥-≥Kin). 排序的稳定性:当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一.在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方

link能不能改变排序算法?link如何实现归并排序?

问题描述 link能不能改变排序算法?link如何实现归并排序? 听说归并排序比快速排序快,有没有办法使用归并排序代替快速排序? 解决方案 我说的是,在待排序数据本身有序的情况下,归并更快,我什么时候说"归并排序比快速排序快"了.