所有的排序算法中,快速排序一定要会写,因为这个最实用。完全可以用在工程实践之中。
下面的实现没有采用随机化的策略,每次partition,都把最右边的元素作为主元或者衡量的坐标,把比主元小的放在左边,比主元大的放在右边,主元的位置作为interval返回。
本文提供的算法存在一定的弊端,就是选的主元有可能不能将数组分成均等的两份,极端情况下,比如输入是逆序的情况下,选的主元没有起到任何分而治之的目的,导致算法复杂度变为O(N^2)。
解决的办法有:
1 随机化策略,partition不是选择最右边的元素,而是在【left,right】之间随机选择一个元素,作为主元。(选中后,和最右边的元素交换即可。其他不变)。这种方法也有缺点,就是每次选择主元,都需要个随机化得函数,代价稍微有点高。
2 三者取中的办法,将最左端 最右端,和中间三个元素进行比较,选择三者中间那个元素作为主元。代价较低。能起到不错的效果。当然这种方法在某些情景下也可能退化。
- #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();
-
}
阅读(942) | 评论(0) | 转发(0) |