随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

快速排序(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 银河使者 阅读(6393) 评论(1)  编辑  收藏 所属分类: algorithmC/C++

评论

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

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

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


网站导航: