sort 與Qsort 排序

 排序:

    過去學過的各種排序相對于今天貼的快排來說，都比較慢，以前的幾乎都是用對比的方式來實作！

    sort 和 Qsort 利用指針進行排序！

    相對來說快的多！！

   所需元素：

    1.數組的首位址；

    2.數組的長度；

    3.compare調用；

 sort中幾種常見的cmp函數：

   一、對int類型數組排序 

  代碼可以直接測試運作：  

   從大到小進行排序！

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int cmp(int a, int b){//compare調用
	return a > b;
}
int main ()
{
	int n;
	int a[10];
	scanf("%d",&n);
	for(int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	sort(a , a + n,cmp);//（首位址，長度，cmp調用）
	for(int i = 0; i < n; ++i)
		printf("%d ", a[i]);
	
	return 0;
}
           

    二、對char類型數組排序（同int類型） 

    從大到小進行排序！

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int cmp(char a, char b)//cmp調用
{
	return a > b;
}
int main ()
{
	char a[10];
	scanf("%s", a);
	sort(a, a + 3,cmp);//（首位址，長度，cmp調用）
	printf("%s\n", a);
	return 0;
}
           

    三、對double類型數組排序

     從小到大！sort(a,a+3);//直接sort（首位址，長度）  即可！下面就拿double型進行示範：

   代碼：

<span style="color:#800080;">#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main ()
{
	int n;
	double a[10];
	scanf("%d",&n);
	for(int i = 0; i < n; ++i)
		scanf("%lf", &a[i]);
	</span><span style="color:#ff0000;">sort(a , a + n);//《sort（首位址，長度）》</span><span style="color:#800080;">
	for(int i = 0; i < n; ++i)
		printf("%lf ", a[i]);
	return 0;
}</span>
           

  四、對結構體一級排序 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
	char a[20];
};
char str[100][1010];
int cmp(char a,char b)
{
	return strcmp(a,b);
}
int main ()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%s",str[i]);
	sort(str, str + n, cmp);
	for(int i = 0; i < n; ++i)
		printf("%s ",str[i]);
	return 0;
}
           

       //這裡排的是字元串型，Int ，double都一樣

int型：(char ，double型類似)
 struct node
 {
 	int a; 
 } 
 int cmp(int a,int b)
 {
 	return a<b;
 }
           

     五、對結構體二級排序 

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node 
{
	int a;
	int b;
}num[10];
int cmp(node x,node y)//如果結構體中a相等，則按b排序，否則按a排序 
{
	if(x.a ==y.a )
	return x.b<y.b ;
	return x.a<y.a ;
}
int main()
{
	int i,j;
	for(i=0;i<10;i++)
	  {
	  	scanf("%d%d",&num[i].a ,&num[i].b );
	  }
	  sort(num,num+10,cmp);
	  for(i=0;i<10;i++)
	   {
	   	printf("%d%d",num[i].a ,num[i].b );
	   }
	   return 0;
}
           

  下面是Qsort：

 一、對int類型數組排序 

    代碼可以直接測試運作：

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)<span style="font-family: verdana, arial, helvetica, sans-serif;">//按照這種模式寫即可</span>
{
	return *(int *)b-*(int *)a;//按照這種模式寫即可
}
int main()
{
	int n;
	int a[1010];
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	qsort(a,n,sizeof(a[0]),cmp);//（首位址，長度，sizeof（a[0]）,cmp）
	for(i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
	return 0;
}
           

</pre><p></p><p><span style="color: rgb(128, 0, 128); font-family: verdana, arial, helvetica, sans-serif; font-size: 13px; line-height: 19.5px;">二、對double類型數組排序（特别要注意符号反方向）</span></p><p><span style="color: rgb(128, 0, 128); font-family: verdana, arial, helvetica, sans-serif; font-size: 13px; line-height: 19.5px;"> </span><pre name="code" class="cpp">#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
	return *(double *)a>*(double *)b;//與sort的大于小于号，相反 
}
int main()
{
	double a[1010];
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lf",&a[i]);
	}
	qsort(a,n,sizeof(a[0]),cmp);
	for(i=0;i<n;i++)
	{
		printf("%lf ",a[i]);
	}
	printf("\n");
}
           

  三 、對char類型數組排序（同double類型）

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
	return *(char  *)a>*(char  *)b;//與sort的大于小于号，相反 
}
int main()
{
	double a[1010];
	int n,i;
	scanf("%d",&n);
	getchar();
	for(i=0;i<n;i++)
	{
		scanf("%c",&a[i]);
			getchar();
	}
	qsort(a,n,sizeof(a[0]),cmp);

	for(i=0;i<n;i++)
	{
		printf("%c ",a[i]);
	}
	printf("\n");
}
           

  四、對結構體一級排序  （把一級排序去掉，注釋去掉，就是二級排序）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
	int u,w;
	double v;
	char str[1010];
}b[1010];
int cmp(const void *a,const void *b)
{
	return strcmp((*(node *)a).str,(*(node *)b).str);
//	if((*(node *)a).u==(*(node *)b).u)
//		return (*(node *)b).w-(*(node *)a).w;
//	return (*(node *)a).u-(*(node *)b).u;
}
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d %d",&b[i].u,&b[i].w);
	}
	qsort(b,n,sizeof(b[0]),cmp);
	for(i=0;i<n;i++)
	{
		printf("%d %d\n",b[i].u ,b[i].w);
	}
}
           

  最後，Qsort與sort不同的是：Qsort能排字元串！！

  排字元：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char str[100][1010];
int cmp(const void *a,const void *b)
{
	return strcmp((char *)b,(char *)a);
}
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%s",str[i]);
	}
	qsort(str,n,sizeof(str[0]),cmp);
	for(i=0;i<n;i++)
	{
		printf("%s\n",str[i]);
	}
	return 0;
}
           

2.sort和qsoort比較：

1．cmp函數和qsort中cmp函數的不同

2.sort函數是c++中标準模闆庫的的函數，在qsort()上已經進行了優化，根據情況的不同可以采用不同的算法，是以較快。在同樣的元素較多和同樣的比較條件下，sort()的執行速度都比qsort()要快。另外，sort()是類屬函數，可以用于比較任何容器，任何元素，任何條件。使用時需調用<algorithm>

sort(begin(),end(),cmp),