常考的 快速排序法

快速排序  时间复杂度 O(nlogn)

文件:	quickSort.tar.gz
大小:	1KB
下载:	下载

//quick sort algrithom

#include <stdio.h>

int partition(int arr[],int len)
{
    int i, j, temp;
  
    i =0;
    j = len-1;

    temp = arr[i];

   while(i<j)
    {
        while (i<j && arr[j]>=temp) --j;
        arr[i] = arr[j];
        
        
        while (i<j && arr[i]<=temp) ++i;
        arr[j] = arr[i];
    
    }    
    arr[i] = temp;
    
     return i;
}

    
void Qsort (int arr[],int len)
{
    if (len>1)
    {
        int k=partition(arr,len);
        
         Qsort(&arr[0],k+1);
        
        Qsort(&arr[k+1],len-k-1);     
    }
 
    
}

void print(int *a,int N)
{
        int i;
        for (i=0;i<N; i++)
               printf("%d, ",a[i]);
        printf("\n");
}

int main()
{
    const int N=10;
     int value[N] = {18,94,61,87,34,31,78,56,14,17};
     
     printf("before Qsort is \n ");
     
        print(value,N);
     
     Qsort(value,N);
    
     printf("\nafter Qsort is \n ");

     print(value,N);
     
     return 0;

}

//quick sort algrithom

#include <stdio.h>


int partition(int arr[],int low,int high)
{
    int i, j, temp;
  
    i =low;
    j = high;

    temp = arr[low];

   while(i<j)
    {
        while (i<j && arr[j]>=temp) --j;
        arr[i] = arr[j];
        
        
        while (i<j && arr[i]<=temp) ++i;
        arr[j] = arr[i];
    
    }    
    arr[i] = temp;
    
     return i;
}

    
void Qsort (int arr[],int low, int high)
{
    if (low<high)
    {
         int k=partition(arr,low,high);
        
         Qsort(arr,0,k-1);
        
        Qsort(arr,k+1,high);     
    }
    
}
void print(int *a,int N)
{
        int i;
        for (i=0;i<N; i++)
               printf("%d, ",a[i]);
        printf("\n");
}

int main()
{
    const int N=10;
     int value[N] = {18,94,61,87,34,31,78,56,14,17};
   
    
     
     printf("before Qsort is \n ");
     
       print(value,N);
     
     Qsort(value,0,N-1);
    
     printf("\nafter Qsort is \n ");

     print(value,N);
     
     return 0;

}