template<class RanIt>
void sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in
the range [first, last) to form a sequence order by operator<. Thus, the elements are sorted in ascending order.（升序排序）。
The function evaluates the ordering predicate X < Y at most ceil((last - first) * log(last - first)) times. 时间复杂度：n*log(n)。
The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).
其实，std::sort是一个改进版的qsort，我们通过分析std::sort，可以了解到qsort函数的优点和不足之处，方便我们更好地理解qsort函数的性质，从而深刻理解快速排序的算法思想。
std::sort函数优于qsort的一些特点：对大数组采取9项取样，更完全的三路划分算法，更细致的对不同数组大小采用不同方法排序。
#include <ctime>
#include <algorithm>
using namespace std;
int main()
{
int val[50];
srand(time(NULL));
for(int i=0; i<50; i++)
{
val[i] = rand()%100;
cout<<val[i]<<endl;
}
cout<<"排序后输出:"<<endl;
sort(val, val+50);
for(i=0; i<50; i++)
{
cout<<val[i]<<endl;
}
return 0;
};
2.qsort
快速排序是一个递归的过程，每次处理一个数列的时候，就从数列中选出一个数，作为划分值，然后在这个数列中，比划分值小的数移动到划分值的左边，比划分值大的数移动到划分值的右边。经过一次这样的处理之后，这个数在最终的已排序的数列的位置就确定了。然后
我们把比这个数小和比这个数大的数分别当成两个子数列调用下一次递归，最终获得一
个排好序的数列。上面介绍的是基本快速排序的方法，每次把数组分成两分和中间的一个划分值，而对于有多个重复值的数组来说，基本排序的效率较低。集成在C语言库函数里面的的qsort函数，使用三路划分的方法解决这个问题。所谓三路划分，是指把数组划分成小于划分值，等于划分值和大于划分值的三个部分。
关于快排函数的一些说明qsort,包含在stdlib.h头文件里,函数一共四个参数,没返回值.一个典型的qsort的写法如下:
qsort(s,n,sizeof(s[0]),cmp);其中第一个参数是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写&s[i]这样的表达式,这个问题下面有说明);
第二个参数是参与排序的元素个数;
第三个三数是单个元素的大小,推荐使用sizeof(s[0])这样的表达式,下面也有说明 :) 第四个参数就是很多人觉得非常困惑的比较函数啦,关于这个函数,还要说的比较麻烦...
我们来讨论cmp这个比较函数(写成cmp是我的个人喜好,你可以随便写成什么,比如qcmp什么的).典型的cmp的定义是:
int cmp(const void *a,const void *b);
返回值必须是int,两个参数的类型必须都是const void *,那个a,b是我随便写的,个人喜好.假设是对int排序的话,如果是升序,那么就是如果a比b大返回一个正值,小则负值,相等返回0,其他的依次类推,后面有例子来说明对不同的类型如何进行排序.在函数体内要对a,b进行强制类型转换后才能得到正确的返回值,不同的类型有不同的处理方法.
具体情况请参考后面的例子. 关于快排的一些小问题
1.快排是不稳定的,这个不稳定一个表现在其使用的时间是不确定的,最好情况(O(n))和最坏情况(O(n^2))差距太大,我们一般说的O(nlog(n))都是指的是其平均时间.
2.快排是不稳定的,这个不稳定表现在如果相同的比较元素,可能顺序不一样,假设我们有这样一个序列,3,3,3,但是这三个3是有区别的,我们标记为3a,3b,3c,快排后的结果不一定就是3a,3b,3c这样的排列,所以在某些特定场合我们要用结构体来使其稳定(No.6的例子就是说明这个问题的)
3.快排的比较函数的两个参数必须都是const void *的,这个要特别注意,写a和b只是我的个人喜好,写成cmp也只是我的个人喜好.推荐在cmp里面重新定义两个指针来强制类型转换,特别是在对结构体进行排序的时候
4.快排qsort的第三个参数,那个sizeof,推荐是使用sizeof(s[0])这样,特别是对结构体,往往自己定义2*sizeof(int)这样的会出问题,用sizeof(s[0)既方便又保险
5.如果要对数组进行部分排序,比如对一个s[n]的数组排列其从s[i]开始的m个元素,只需要在第一个和第二个参数上进行一些修改:qsort(&s[i],m,sizeof(s[i]),cmp);
No.1.手工实现QuickSort
#include <stdio.h>
int a[100],n,temp;
void QuickSort(int h,int t)
{
if(h>=t) return;
int mid=(h+t)/2,i=h,j=t,x;
x=a[mid];
while(1)
{
while(a[i]<x) i++;
while(a[j]>x) j--;
if(i>=j) break;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
a[mid]=a[j];
a[j]=x;
QuickSort(h,j-1);
QuickSort(j+1,t);
return;
}
int main()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d",&a[i]);
QuickSort(0,n-1);
for(i=0;i<n;i++) printf("%d ",a[i]); return(0);
}
No.2.最常见的,对int数组排序
#include <stdlib.h>
#include <ctime>
int cmp(const void *a, const void *b)
{
return( *(int*)a - *(int*)b );
// if(*(int*)a > *(int*)b)
// return 1;
// else if(*(int*)a == *(int*)b)
// return 0;
// else
// return -1;
}
int main()
{
int A[50];
srand(time(NULL));
for(int i=0; i<50; i++)
{
A[i] = rand()%100;
cout<<A[i]<<endl;
}
qsort(A, 50, sizeof(int), cmp);
cout<<"快速排序后输出:"<<endl;
for(int j=0; j<50; j++)
cout<<A[j]<<endl;
return 0;
}
No.3.对double型数组排序,原理同int这里做个注释,本来是因为要判断如果a==b返回0的,但是严格来说,两个double数是不可能相等的,只能说fabs(a-b)<1e-20之类的这样来判断,所以这里只返回了1和-1。
#include <stdio.h>
#include <stdlib.h>
double s[10];
int i,n;
int cmp(const void * a, const void * b)
{
return((*(double*)a-*(double*)b>0)?1:-1);
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf",&s[i]);
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%lf ",s[i]);
return(0);
}
No.4.对一个字符数组排序.原理同int
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char s[10000],i,n;
int cmp(const void *a,const void *b)
{
return(*(char *)a-*(char *)b);
}
int main()
{
scanf("%s",s);
n=strlen(s);
qsort(s,n,sizeof(s[0]),cmp);
printf("%s",s);
return(0);
}
No.5.对结构体排序注释一下.很多时候我们都会对结构体排序,比如校赛预选赛的那个樱花,一般这个时候都在cmp函数里面先强制转换了类型,不要在return里面转,我也说不清为什么,但是这样程序会更清晰,并且绝对是没错的. 这里同样请注意double返回0的问题
#include <stdio.h>
#include <stdlib.h>
struct node
{
double date1;
int no;
} s[100];
int i,n;
int cmp(const void *a,const void *b)
{
struct node *aa=(node *)a;
struct node *bb=(node *)b;
return(((aa->date1) > (bb->date1))? 1:-1);
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
s[i].no = i+1;
scanf("%lf",&s[i].date1);
}
qsort(s, n, sizeof(s[0]), cmp);
for(i=0;i<n;i++)
printf("%d %lf/n",s[i].no,s[i].date1);
return(0);
}
No.6.对结构体排序.加入no来使其稳定(即data值相等的情况下按原来的顺序排)
#include <stdio.h>
#include <stdlib.h>
struct node
{
double date1;
int no;
} s[100];
int i,n;
int cmp(const void *a,const void *b)
{
struct node *aa=(node *)a;
struct node *bb=(node *)b;
if(aa->date1!=bb->date1)
return(((aa->date1)>(bb->date1))?1:-1);
else
return((aa->no)-(bb->no));
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
s[i].no=i+1;
scanf("%lf",&s[i].date1);
}
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%d %lf/n",s[i].no,s[i].date1);
return(0);
}
No.7.对字符串数组的排序(char s[][]型)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char s[100][100];
int i,n;
int cmp(const void *a, const void *b)
{
return(strcmp((char*)a, (char*)b));
}
int main()
{
scanf("%d", &n);
for(i=0; i<n; i++)
scanf("%s", s[i]);
qsort(s, n, sizeof(s[0]), cmp);
for(i=0; i<n; i++)
printf("%s/n", s[i]);
return(0);
}
No.8.对字符串数组排序(char *s[]型)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *s[100];
int i,n;
int cmp(const void *a,const void *b)
{
return(strcmp(*(char**)a,*(char**)b));
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
s[i]=(char*)malloc(sizeof(char*));
scanf("%s",s[i]);
}
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++) printf("%s/n",s[i]);
return(0);
}
bsearch函数的使用：
bsearch @import url(MS-ITS:dsmsdn.chm::/html/msdn_ie4.css);
Performs a binary search of a sorted array.
void *bsearch( const void *key, const void *base, size_t num, size_t width, int ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
bsearch
@import url(MS-ITS:dsmsdn.chm::/html/msdn_ie4.css);
Return Value
bsearch returns a pointer to an occurrence of key in the array pointed to by base. If key is not found, the function returns NULL. If the array is not in ascending sort order or contains duplicate records with identical keys, the result is unpredictable.
Parameters
key
Object to search for
base
Pointer to base of search data
num
Number of elements
width
Width of elements
compare
Function that compares two elements: elem1 and elem2
elem1
Pointer to the key for the search
elem2
Pointer to the array element to be compared with the key
#include <stdlib.h>
#include <ctime>
#include <search.h>
int cmp(const void *a, const void *b)
{
return( *(int*)a - *(int*)b );
}
int main()
{
int A[50];
srand(time(NULL));
for(int i=0; i<50; i++)
{
A[i] = rand()%100;
cout<<A[i]<<endl;
}
qsort(A, 50, sizeof(int), cmp);
cout<<"快速排序后输出:"<<endl;
for(int j=0; j<50; j++)
cout<<A[j]<<endl;
int* loc = 0;
int a = 3;
loc = (int*) bsearch(&a, A, 50, sizeof(int), cmp);
cout<<"找到的数值地址为："<<endl;
cout<<loc<<endl;
return 0;
}