Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4249312
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-05-01 11:21:42

一、数据结构
        约定排序均为升序排序,要排序的记录存储在线性表中,线性表由排序关键字和其它域组成,其定义如下:
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型,比如int,float或char等,在算法中,约定其为int类型。

二、算法思想
        快速排序是由冒泡排序改进而得的,它的基本思想是:在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入最终位置后,数据序列被此记录分割成两部分。所有关键字比该记录关键字小的放置在前一部分,所有比它大的放置在后一部分,并把该记录排在这两部分的中间,这个过程称作一趟快速排序。之后对所有的两部分分别重复上述过程,直至每部分内只有一个记录为止。简而言之,每趟使表的第一个元素入终位,将表一分为二,对子表按递归方式继续这种划分,直至划分的子表长为1。
        一趟快速排序采用从两头向中间扫描的办法,同时交换与基准记录逆序的记录。具体作法是:设两个指示器i和j,它们的初值分别为指向无序区中第一个和最后一个记录。假设无序区中记录为r[s], r[s+1], ..., r[t],则i的初值为s,j的初值为t,首先将r[s]移至变量r[0]中作为基准,令j自t起向左扫描直至r[j].key < r[0].key时,将r[j]移至i所指的位置上,然后令i自i+1起向右扫描直至r[i].key > r[0].key时,将r[i]移至j所指的位置上,依次重复直至i==j,此时所有r[k](k=s, s+1, ..., j-1)的关键字都小于r[0].key而所有r[k](k=j+1, j+2, ..., t)的关键字必大于r[0].key,则可将r[0]中的记录移至i所指位置r[i],它将无序中记录分割成r[s, j-1]和r[j+1, t],以便分别进行排序。

三、程序实现
        实现快速排序的函数如下:
        void fastsort(sqlist r, int s, int t)        // 把r[s]至r[t]的元素进行快速排序
        {
            int i=s, j=t;
            if (s < t)
            {
                r[0] = r[s];
                do
                {
                    while (j>i  && r[j].key>=r[0].key)   
                    {
                         j--;
                    }
                    if (i < j)
                    {
                         r[i] = r[j];
                         i++;
                    }
                    while (i                     {    
                         i++;
                    }
                    if (i < j)
                    {                               
                        r[j] = r[i];
                        j--;
                    }
                } while (i < j);
                r[i] = r[0];
                quicksort(r, s, j-1);
                quicksort(r, j+1, t);
            }
        }
        快速排序算法的时间复杂度是O(nlog2n),它是一种不稳定的排序方法。



阅读(1889) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

scq2099yt2013-05-01 11:21:52

文明上网,理性发言...

评论热议
请登录后评论。

登录 注册