Chinaunix首页 | 论坛 | 博客
  • 博客访问: 324609
  • 博文数量: 113
  • 博客积分: 446
  • 博客等级: 下士
  • 技术积分: 1229
  • 用 户 组: 普通用户
  • 注册时间: 2012-12-09 16:01
个人简介

Let's go!!!!!

文章分类

全部博文(113)

文章存档

2019年(5)

2018年(4)

2017年(9)

2016年(5)

2015年(39)

2014年(6)

2013年(28)

2012年(17)

分类: LINUX

2014-12-10 22:33:44

//qksort.h
#ifndef __QKSORT_H
#define __QKSORT_H

int qksort(int *data,int i,int j);

#endif

//qksort.c
#include
#include
#include
#include

static int pvalue(int *data,int i,int j)
{
   int r[3]={0};
   int temp = 0;

   srand(time(NULL));
   r[0] = (rand()%(j-i+1)) + i;
   r[1] = (rand()%(j-i+1)) + i;
   r[2] = (rand()%(j-i+1)) + i;
   
   if(data[r[0]] > data[r[1]])
   {
       temp = data[r[0]];
       data[r[0]] = data[r[1]];
       data[r[1]] = temp;
   }
                               
   if(data[r[2]] > data[r[1]])
       return data[r[1]];
   else if(data[r[2]] > data[r[0]])
       return data[r[2]];
   else
       return data[r[0]];
}

static int partion(int *data,int i,int j)
{
   int temp = 0;
   int pval = pvalue(data,i,j);  

   i--;
   j++;
   while(1)
   {
       do{
           j--;  
       }
       while(data[j] > pval && i < j);
   
       do{
           i++;
       }
       while(data[i] < pval && i < j);

       if(i >= j)
       {
           break;
       }
       else
       {
           temp = data[i];
           data[i] = data[j];
           data[j] = temp;
       }
   }
   return j;
}

int qksort(int *data,int i,int j)
{
   int k = 0;
   if(i < j)
   {
       if((k = partion(data,i,j))<0)
           return -1;
       if(qksort(data,i,k)<0)
           return -1;
       if(qksort(data,k+1,j)<0)
           return -1;
   }
   return 0;
}

//generate.h
#ifndef __GENERATE_H
#define __GENERATE_H

#define LOWER_LIMIT  0
#define UPPER_LIMIT  500
#define NUM          50

void generate(int *data,int size);

#endif

//generate.c
#include
#include
#include
#include
#include "generate.h"

void generate(int *data,int size)
{
   int i = 0;
   int j = 0;
   int number = 0;
   srand(time(NULL));    
   for(i = 0;i < NUM;i++)
   {
       number = rand()%UPPER_LIMIT;
       data[i] = number;
   }
}



//主函数
#include
#include "generate.h"
#include "qksort.h"

int main()
{
   int array[NUM] ={0};
   int i = 0;

   generate(array,NUM);
   
   printf("Before sort:\n");
   for(i=0;i        printf("%d ",array[i]);
   printf("\n");

   qksort(array,0,NUM-1);
   
   printf("After sort:\n");
   for(i=0;i        printf("%d ",array[i]);
   printf("\n");
}

//Makfile
main:main.o generate.o qksort.o
cc -o main main.o generate.o qksort.o

main.o:main.c generate.h qksort.h
cc -c main.c
generate.o:generate.c generate.h
cc -c generate.c
qksort.o:qksort.c qksort.h
cc -c qksort.c

clean:
rm *.o -rf
clear:
rm *.o main -rf
阅读(553) | 评论(0) | 转发(0) |
0

上一篇:插入排序

下一篇:计数排序

给主人留下些什么吧!~~