Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4710950
  • 博文数量: 930
  • 博客积分: 12070
  • 博客等级: 上将
  • 技术积分: 11448
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-15 16:57
文章分类

全部博文(930)

文章存档

2011年(60)

2010年(220)

2009年(371)

2008年(279)

分类: LINUX

2009-07-14 19:31:55

    先看的是数据结构与算法分析--c语言描述,看来半天硬是不知所云,大概只弄清了枢纽的选择,我们一般选取
A[0] or A[N-1]大概是不对的.那就random喽...不过这个是题外话.突然想起手中还有本算法导论.
    已看算法导论果然懂了,清晰易懂,人见人爱,强烈建议购买^_^
    A[N]如下
    2  8  7  1  3  5  6  4
    描述的时候就去A[N-1]为枢纽了啊,random的话就先 swap(A[rand()%N],A[N-1])一下
   
    2  8  7  1  3  5  6  4
    i j                       //i=-1,j=0,x=4
    此时A[j]
 
    2  8  7  1  3  5  6  4
    i  j                    //i=0,j=1,x=4
    A[1]=8>x=4
    2  8  7  1  3  5  6  4
    i     j                    //i=0,j=2,x=4
    A[1]=7>x=4
    2  8  7  1  3  5  6  4
    2  1  7  8  3  5  6  4
    i        j                    //i=0,j=3,x=4
    A[3]=1 < x=4  i++;swap(A[1],A[3])
    2  8  7  1  3  5  6  4
    2  1  3  8  7  5  6  4
    i           j                    //i=0,j=4,x=4
    A[4]=3 < x=4  i++;swap(A[2],A[3])
    最后 swap(A{i+1],A[r])
    2  1  3  4  7  5  6  8
 
  

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 20

void swap(int* a,int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int partition(int a[], int start, int end)
{
  //int num = rand()%(end-start+1);

 // swap(a+num,a+end);

  
  int x = a[end];
  int i = start-1;
  int j = start;
  for(;j<end;j++) //注意这里是j
  {
    if(a[j]<=x)
     {
       i++;
       swap(a+i, a+j);
      }
   }
   swap(a+i+1,a+end);
   
   return i+1;
}

void quick_sort(int a[],int start,int end)
{
  int q;
  if(start<end)
   {
       q = partition(a, start, end);
       quick_sort(a, start, q-1);
       quick_sort(a, q+1, end);
     }
}

void print_array(int* a)
{
  int i = 0;
  for(;i<MAX;i++)
   {
      if((i+1)%20==0)
       printf("%d\n",a[i]);
      else
       printf("%d\t",a[i]);
    }
}

int main(int argc, char *argv[])
{
  int i = 0;
  int a[MAX];
  srand((unsigned)time(NULL));
  for(;i<MAX;i++)
     a[i] = rand()%50;
  printf("before quick sort\n");
  print_array(a);
  quick_sort(a, 0, MAX-1);
  printf("after quick sort\n");
  print_array(a);
   
  system("PAUSE");    
  return 0;
}

阅读(1522) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~