快速排序quicksort的Ｃ实现

快速排序quicksort的Ｃ实现 (2011-08-19 22:01) 转载

标签:  算法 排序 sort  分类： algorthm

所有的排序算法中，快速排序一定要会写，因为这个最实用。完全可以用在工程实践之中。

下面的实现没有采用随机化的策略，每次partition，都把最右边的元素作为主元或者衡量的坐标，

把比主元小的放在左边，比主元大的放在右边，主元的位置作为interval返回。

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

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


int partition(int array[],int l,int r)
{
    int pivot = 
array[r];
    int curpos = 
l;
    int j ;

    for( j = l;j<r;j++)
    {
        if(array[j] < 
pivot)
        {
            swap(&array[j],&array[curpos]);
            curpos++;
        }
    }

    swap(&array[r],&array[curpos]);
    return curpos;


}

void quicksort(int array[],int l,int r)
{
    int interval;
    if(l < r)
    {
        interval = partition(array,l,r);
        quicksort(array,l,interval-1);
        quicksort(array,interval+1,r);
    }

}


int test_quicksort()
{
    int number = 
12;
    int *array = 
malloc(number*sizeof(int));
  
  if（array == NULL）
  
  {
  
      printf("malloc failed\n");
        return 
-1;
  
  }
    int i;

    printf("----------------------------------------before quick 
sort--------------\n");
    srand(time(NULL));
    for(i = 0;i<number;i++)
    {
        array[i] = rand()%1000;
        printf("\tarray[%d] = 
%d\n",i,array[i]);
    }

    printf("----------------------------------------after quick 
sort-----------------\n");

    quicksort(array,0,number-1);
    for(i = 0;i<number;i++)
    {
        printf("\tarray[%d] = 
%d\n",i,array[i]);
    }
    return 0;
}
int main()
{
    test_quicksort();
}