随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0

导航

<2008年5月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

公告

关注我的新浪微博

我的著作









常用链接

留言簿(126)

我参与的团队

随笔分类(818)

随笔档案(310)

文章分类(1)

文章档案(8)

相册

ADSL、3G查询

CSDN

eclipse

ibm

Java EE

Linux

Web

云服务

代理网站

关注的网站

协议

喜欢的Blog

国内广告平台

图书出版

在线培训

开发工具

微博客户端

手机铃声

操作系统

  • ReactOS
  • 一个与windowXP/2003兼容的操作系统

数学

文件格式

源码资源

移动(Mobile)

编程语言

英语学习

最新随笔

搜索

  •  

积分与排名

  • 积分 - 1969837
  • 排名 - 6

最新评论

阅读排行榜

评论排行榜

快速排序(quicksort)算法实现

    快速排序(quicksort)是分治法的典型例子,它的主要思想是将一个待排序的数组以数组的某一个元素X为轴,使这个轴的左侧元素都比X大,而右侧元 素都比X小(从大到小排序)。然后以这个X在变换后数组的位置i分为左右两个子数组,再分别进行快速排序,直到子数组中只有一个元素为止。

快速排序算法如下
void quicksort(int A[], int p, int r)
{
    
int i;
    
if(p < r)
    {
        i 
= partition(A, p, r);
        quicksort(A, 
0, i - 1);
        quicksort(A, i 
+ 1, r);
    }   
}

    其中partition函数将得到X所在的位置i(在这里总以数组的最后一个元素为轴)。
int partition(int A[], int p, int r)
{
    
int i = p - 1, j;
    
for(j = p; j < r; j++)
    {
        
if(A[j] >= A[r])
        {
            i
++;
            swap(
&A[i], &A[j]);
        }
    }
    swap(
&A[i + 1], &A[r]);
    
return i + 1;
}

    由于总是选择数组的最后一个元素做为轴,因此可能出现X的左边为n - 1或接近n - 1个元素,而右边没有元素,或元素很少的情况,即X最大或比较大。这样使quicksort将出现最坏的情况,也就是时间复杂度为O(n^2)。因此partition可以采用随机方式得到轴X的位置i。 这样它的平均情况是非常好的(时间复杂度为O(nlogn)),也就是说,最坏情况很难出现。
int new_random(int min, int max)
{
    
return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}

int randomize_partition(int A[], int p, int r)
{
    
int i = new_random(p, r);
    swap(
&A[i], &A[r]);
    
return partition(A, p, r);
}

完整的代码如下
#include <stdio.h>
#include 
<stdlib.h>

void out_int_array(int data[], int n)
{
    
int i;
    
for(i = 0; i < n; i++)
    {
        printf(
"%d ", data[i]);
    }
    printf(
"\n");
}
void swap(int *a, int *b)
{
    
int x;
    x 
= *a;
    
*= *b;
    
*= x;
}

int new_random(int min, int max)
{
    
return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}
int partition(int A[], int p, int r)
{
    
int i = p - 1, j;
    
for(j = p; j < r; j++)
    {
        
if(A[j] >= A[r])
        {
            i
++;
            swap(
&A[i], &A[j]);
        }
    }
    swap(
&A[i + 1], &A[r]);
    
return i + 1;
}

void quicksort(int A[], int p, int r)
{
    
int i;
    
if(p < r)
    {
        i 
= partition(A, p, r);
        quicksort(A, 
0, i - 1);
        quicksort(A, i 
+ 1, r);
    }   
}

int randomize_partition(int A[], int p, int r)
{
    
int i = new_random(p, r);
    swap(
&A[i], &A[r]);
    
return partition(A, p, r);
}

void randomize_quicksort(int A[], int p, int r)
{
    
int i;
    
if(p < r)
    {
        i 
= randomize_partition(A, p, r);
        quicksort(A, 
0, i - 1);
        quicksort(A, i 
+ 1, r);
    }   
}

int main()
{
    
int A[] = {4144-12512530};
    
int B[] = {4144-12512530};
    out_int_array(A, 
7);
    quicksort(A, 
06);
    out_int_array(A, 
7);
    printf(
"--------------------------randomize-----------------------------\n");   
    srand((unsigned)time( NULL ));
    randomize_quicksort(B, 
06);
    out_int_array(B, 
7);
    
return 0;
}




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2008-05-14 20:14 银河使者 阅读(6573) 评论(1)  编辑  收藏 所属分类: algorithmC/C++

评论

# re: 快速排序(quicksort)算法实现  回复  更多评论   

主函数里用了time()函数,要加个头文件吧,include<time.h>。小问题,谢谢共享
2014-10-09 23:12 | 志在四方

只有注册用户登录后才能发表评论。


网站导航: