快速排序(quicksort)算法实现-阿里云开发者社区

开发者社区> 技术小胖子> 正文

快速排序(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;
}



 本文转自 androidguy 51CTO博客,原文链接:http://blog.51cto.com/androidguy/215359,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
948 0
《排序算法》——快速排序(Java)
十大算法之快速排序: 方法其实很简单:分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。
686 0
python实现插入排序算法
插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。 python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实...
814 0
排序算法(七):快速排序
快速排序是通过分治的方式,根据选定元素将待排序集合拆分为两个值域的子集合,并对子集合递归拆分,当拆分后的每个子集合中元素个数为一时,自然就是有序状态。
697 0
【开源】QuickPager ASP.NET2.0分页控件V2.0.0.4 增加了几个分页算法
================================ 欢迎转载,但是请注明出处。本文出自博客园 。谢谢合作! ================================                最近忙一个项目,没有太多的时间来升级分页控件。
816 0
谷歌百度以图搜图 "感知哈希算法" C#简单实现
/// /// 感知哈希算法 /// public class ImageComparer { /// /// 获取图片的Hashcode /// /// /// public static string GetImageHashCode(string imageName) { int width = 8; int height = 8; // 第一步 // 将图片缩小到8x8的尺寸,总共64个像素。
1535 0
【算法导论】快速排序
快速排序         快速排序的最坏运行时间为O(n2),虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为O(nlogn),并且O(nlogn)中的隐含常数因子很小。
797 0
排序算法(十):基数排序
基数排序也可以称为多关键字排序,同计数排序类似,也是一种非比较性质的排序算法。将待排序集合中的每个元素拆分为多个总容量空间较小的对象,对每个对象执行桶排序后,则完成排序过程。
836 0
算法研究之快速排序
所谓的快速排序的思想就是,首先把数组的第一个数拿出来做为一个key,在前后分别设置一个i,j做为标识,然后拿这个key对这个数组从后面往前遍历,及j--,直到找到第一个小于这个key的那个数,然后交换这两个值,交换完成后,我们拿着这个key要从i往后遍历了,及i++;一直循环到i=j结束,当这里结束后,我们会发现大于这个key的值都会跑到这个key的后面,不是的话就可能你写错了,小于这个key的就会跑到这个值的前面;然后我们对这个分段的数组再时行递归调用就可以完成整个数组的排序。
453 0
13262
文章
0
问答
来源圈子
更多
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载