文档章节

经典快排

{
 {会飞的猪}
发布于 2014/09/02 20:31
字数 247
阅读 6
收藏 0
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20

void myqsort(int *a, int l, int r);
int partition(int *a, int l, int r);
void swap(int *x, int *y);
void printArray(int *a, int len);
void init(int *a, int len);

int main()
{
    int a[N] ;//= {8033, 1139, 4735, 14470};

    while(getchar() != EOF){
        init(a, N);
        printArray(a, N);
        srand((unsigned)time(NULL));
        printf("\n");
        myqsort(a, 0, N-1);
        printf("\n");
        printArray(a, N);
    }
    return 0;
}
void init(int *a, int len)
{
    int i = 0;
    srand((unsigned)(time(NULL)));
    while(i < len){
        a[i] = rand();
        i++;
    }
}
void myqsort(int *a, int l, int r)
{
    if(a == NULL || l <0 || l >= r){
        //printf("end\n");
        return;
    }
    int p = partition(a, l, r);
    myqsort(a, l, p);
    myqsort(a, p+1 , r);
}

int partition(int *a, int l, int r)
{

    int point = l + rand()%(r-l+1);
    int key = a[point];
    int i = l, j = r;
    while(i < j){
        while(a[j] > key) j--;
        while(a[i] < key) i++;
        if(i < j){
            swap(a+i, a+j);
            //i++;
            //j--;
        }
    }
    //printArray(a, N);
    //printf("point=%d\ti=%d\tl=%d\tr=%d\n", point, i, l, r);
    return i;
}

void swap(int *x, int *y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void printArray(int *a, int len)
{
    int i = 0;
    while(i < len){
        printf("%d\t", *(a+i));
        i++;
    }
    printf("\n");
}


© 著作权归作者所有

共有 人打赏支持
{
粉丝 0
博文 14
码字总数 3806
作品 0
西安
私信 提问
经典排序之 快速排序

Author: bakari Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为快排。 快排是一个非常重要的算法,在各个领域...

chambai
2012/08/11
0
0
VC库中快排函数的详解

Author: bakari Date: 2012.8.9 以前都是自己手动写这个算法,觉得也不是一件很麻烦的事,但现在写的程序基本上都用得着快排,重新去写这个算法很没有必要。直接使用VC库中提供的qsort方便了...

chambai
2012/08/11
0
0
被忽视的 partition 算法

如果你学习过算法,那么肯定听说过快速排序的大名,但是对于快速排序中用到的 partition 算法,你了解的够多吗?或许是快速排序太过于光芒四射,使得我们往往会忽视掉同样重要的 partition ...

selfboot
2016/08/31
0
0
俩头查找的快排优化

对于 5743 经典快排过程: 5473 5437 会造成多次替换,所以写出优化算法: 去第一位为基准值 从左向右扫 发现大值 从右向左扫 发现小值 替换 将基准值和最后一个小值替换 function quick(arr...

苗威
2015/09/14
115
0
算法系列15天速成——第一天 七大经典排序【上】

今天是开篇,得要吹一下算法,算法就好比程序开发中的利剑,所到之处,刀起头落。 针对现实中的排序问题,算法有七把利剑可以助你马道成功。 首先排序分为四种: 交换排序: 包括冒泡排序,快...

BobbyLou
2015/08/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring学习记录

Java类定义配置 @Configuration //标记为配置类@ComponentScan //标记为扫描当前包及子包所有标记为@Component的类@ComponentScan(basePackageClasses = {接口.class,...}) //标记为扫描当...

CHONGCHEN
31分钟前
1
0
如何开发一款以太坊(安卓)钱包系列2 - 导入账号及账号管理

这是如何开发一款以太坊(安卓)钱包系列第2篇,如何导入账号。有时用户可能已经有一个账号,这篇文章接来介绍下,如何实现导入用户已经存在的账号。 导入账号预备知识 从用户需求上来讲,导...

Tiny熊
今天
3
0
intellJ IDEA搭建java+selenium自动化环境(maven,selenium,testng)

1.安装jdk1.8; 2.安装intellJ; 3.安装maven; 3.1 如果是单前用户,配置用户环境变量即可,如果是多用户,则需配置系统环境变量,变量名为MAVEN_HOME,赋值D:\Application\maven,往path中...

不最醉不龟归
今天
4
0
聊聊ShenandoahGC的Brooks Pointers

序 本文主要研究一下ShenandoahGC的Brooks Pointers Shenandoah Shenandoah面向low-pause-time的垃圾收集器,它的GC cycle主要有 Snapshot-at-the-beginning concurrent mark包括Init Mark(P......

go4it
昨天
4
0
Makefile通用编写规则

#简单实用的Makefile模板: objs := a.o b.o test:$(objs) gcc -o test $^ # .a.o.d .b.o.d dep_files := $(foreach f,$(objs),.$(f).d) dep_files := $(wildcard $(dep_files)) ifneq ($(d......

shzwork
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部