(一) 基本思想
快速排序（quicksort）是交换排序的另一种，实际上它是冒泡排序的另一种改进。快速排序的基本思想是：在待排序的n个记录中任取一个记录（例如就取第一个记录），以该记录的键值为标准，将所有记录分为两组（一般都是无序的），使得第一组中各记录的键值均小于或等于该键值，第二组中各记录的键值均大于该键值。然后把该记录就排在这两组的中间（这也是该记录最终的位置）。此称为一趟分割，对所分成的两组再分别重复上述方法，直到所有记录都排在适当位置为止。
(二) 分割算法
一趟快速排序的具体做法是：设两个指针i和j，它们的初值分别为0、n-1，且把a[0]送入工作单元x中保存（选第一个记录为标准），然后比较a[j]和x，若a[j]>x，则j减1后继续与x比较，直至r[j]＜=x，然后，将a[j]移至a<i>的位置，令i加1，接着进行a<i>和x的比较，若a<i><x，则令x加1，然后继续比较，直至满足a<i>＞=x，此时，将a<i>移至r[j]的位置，令j减1，之后，重复上述过程，直至i==j。此时i便是记录x所应在的位置。至此，一趟分割完成。
long SortPartition (in a[], long p1, long p2);
{//对a[p1]—a[p2]进行分割，返回分割点
long i, j;
int x;
i =p1;
j =p2;
x =a<i>;
while (i<j)
{
while ( a[j]>x && i<j ) j--
if (i<j) {a[j]=a[j]; i++;}
while (a<i><=x && i<j ) i++;
if (i<j) {a[j] =a<i>; j--;}
}
a<i>=x;
return i;
}
初始关键字 70 73 69 23 93 18 11 68
一次交换之后 68 73 69 23 93 18 11 70
二次交换之后 68 70 69 23 93 18 11 73
三次交换之后 68 11 69 23 93 18 70 73
68 11 69 23 93 18 70 73
68 11 69 23 93 18 70 73
四次交换之后 68 11 69 23 70 18 93 73
五次交换之后 68 11 69 23 18 70 93 73
(三) 快速排序递归程序
long SortQuick(ing a[], long p1, long p2)
{
long p;
if (p1<p2)
{
p = SortPartition(a, p1,p2);
SortQuick(a, p1, p-1);
SortQuick(a, p+1, p2);
return p2-p1+1;
}
return 0;
}
(四) 快速排序非递归算法
要把上述递归算法改写成非递归算法，可引进一个栈，这个栈的大小取决于递归调用的深度，最多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n，也就是说快速排序需要的附加存储开销为O（log2n）。
long QuickSort2(int a[], long p1, long p2)
{
long *s; top
long i, j;
s=new long[p2-p1+1];
if (s==NULL) return -1;
top=0;
top++; s[top]=p1;
top++; s[top]=p2;
while (top!=0)
{
j = s[top]; top--;
i = s[top]; top--;
while (i<j)
{
p = SortPartition(a, i, j);
if (p-i<j-p)
{//先分割前部,后部进栈
top++; s[top] = p+1;
top++; s[top] = j;
j = p-1;
}
else
{//先分割后部,前部进栈
top++; s[top] = i;
top++; s[top] = p-1;
i = p+1;
}
}// while (i<j)
}// while (top!=0)
return p2-p1+1;
}
下面给出利用快速排序程序进行排序的过程。图中方括号表示无序区。
初始关键字 [70 73 69 23 93 18 11 68]
第一趟排序之后 [68 11 69 23 18] 70 [93 73]
第二趟排序之后 [18 11 23] 68 [69] 70 [93 73]
第三趟排序之后 11 18 23 68 69 70 [93 73]
第四趟排序之后 11 18 23 68 69 70 73 93
可以证明，快速排序平均比较次数是O（nlg2n）快速排序的记录移动次数小平等于比较次数，因此快速排序总执行时间为O（nlog2n）.
快速排序是不稳定的，请读者自己举出一例说明。
从平均时间性能而言，快速排序最佳，其时间复杂性为O（nlog2n）。但在最坏情况下，即对几乎是排序好的输入序列，该算法的效率很低，近似于O（n2）。对于较小的n值，该算法效果不明显；反之，对较大的n值，效果较好。
void QSort(int a[], int left, int right)
{
int pivot, l, r, temp;
l=left;
r=right;
pivot=a[(right+left)/2];
while(l<r)
{
while(a[l]< pivot) ++l;
while(a[r]> pivot) --r;
if(l>=r) break;
temp= a[l];
a[l]= a[r];
a[r]= temp;
if(a[l]!=pivot) --r;
if(a[r]!=pivot) ++l;
}
if(l==r) l++;//
if(left<r) QSort(a,left,l-1);
if(l<right) QSort(a,r+1,right);
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
base是需要sort的数组，num是base的大小，width是每个元素的大小，以byte为单位，compare是一个比较大小的函数的指针，当然是你自己写的了，因为qsort也不知道你要排序的是什么东西啊，你就告诉它是elem1大呢还是elem2大就行了，返回值看看下面的详细文档啦。
The qsort function implements a quick-sort algorithm to sort an array of num elements, each of width bytes. The argument base is a pointer to the base of the array to be sorted. qsort overwrites this array with the sorted elements. The argument compare is a pointer to a user-supplied routine that compares two array elements and returns a value specifying their relationship. qsort calls the compare routine one or more times during the sort, passing pointers to two array elements on each call:
compare( (void *) elem1, (void *) elem2 );
The routine must compare the elements, then return one of the following values:
Return Value Description
< 0 elem1 less than elem2
0 elem1 equivalent to elem2
> 0 elem1 greater than elem2
The array is sorted in increasing order, as defined by the comparison function. To sort an array in decreasing order, reverse the sense of “greater than” and “less than” in the comparison function.
Example
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int compare( const void *arg1, const void *arg2 );
void main( int argc, char **argv )
{
int i;
argv++;
argc--;
qsort( (void *)argv, (size_t)argc, sizeof( char * ), compare );
for( i = 0; i < argc; ++i )
printf( &quot;%s &quot;, argv<i> );
printf( &quot;\n&quot; );
}
int compare( const void *arg1, const void *arg2 )
{
return _stricmp( * ( char** ) arg1, * ( char** ) arg2 );
}
Output
[C:\code]qsort every good boy deserves favor
boy deserves every favor good
七种qsort排序方法
<本文中排序都是采用的从小到大排序>
一、对int类型数组排序
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、对char类型数组排序（同int类型）
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、对double类型数组排序（特别要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；
四、对结构体一级排序
struct In
{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *b)
{
return (*(In *)a)->data > (*(In *)b)->data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、对结构体二级排序
struct In
{
int x;
int y;
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
六、对字符串进行排序
struct In
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
七、计算几何中求凸包的cmp
int cmp(const void *a,const void *b) //重点cmp函数，把除了1点外的所有点，旋转角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一条直线上，则把远的放在前面
return 1;
else return -1;
}
PS:
其中的qsort函数包含在<stdlib.h>的头文件里，strcmp包含在<string.h>的头文件里 |
|
楼主
标题置顶
标题高亮
