堆排序
堆排序主要由两个核心部分组成：构造堆(大顶堆或小顶堆)，对构造的堆进行排序。
核心思路:在构造的大/小顶堆中把最大/小的元素与堆中最后一个元素交换，取出最大/最小元素，然后再对剩余元素进行构造堆，交换元素的过程，直到排序结束。
49
/ \
38 65
/ \ / \
97 76 13 27
/
51
97
/ \
76 65
/ \ / \
38 49 13 27
/
51
void HeapAdjust(int a[],int s,int m)
{
int temp=a[s];
for(int i=2*s+1;i<=m;i=2*i+1){
if(a[i]<a[i+1]&&i<m)
i++;
if(temp>=a[i])
break;
a[s]=a[i];
s=i;
}
a[s]=temp;
}
void HeapSort(int a[],int n)
{
for(i=(n-1)/2;i>=0;i--)//注：数组下标从0开始
HeapAdjust(a,i,n-1);
for(i=n-1;i>0;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
HeapAdjust(a,0,i-1);
for(j=0;j<8;j++)
printf("%d ",a[j]);
}
}
归并排序
-
分：将数组分成两半，递归地对每一半进行排序
-
治：将两个已排序的子数组合并成一个有序数组
-
初始数组：
[49, 38, 65, 97, 76, 13, 27, 51]
MSort(a,b,0,7)
├─ MSort(a,TR2,0,3) (左半部分)
│ ├─ MSort(a,TR2,0,1)
│ │ ├─ MSort(a,TR2,0,0) → 直接返回49
│ │ └─ MSort(a,TR2,1,1) → 直接返回38
│ │ └─ Merge([49,38], [38,49], 0,0,1) → 输出38 49
│ └─ MSort(a,TR2,2,3)
│ ├─ MSort(a,TR2,2,2) → 直接返回65
│ └─ MSort(a,TR2,3,3) → 直接返回97
│ └─ Merge([65,97], [65,97], 2,2,3) → 输出65 97
│ └─ Merge([38,49,65,97], [38,49,65,97], 0,1,3) → 输出38 49 65 97
└─ MSort(a,TR2,4,7) (右半部分)
├─ MSort(a,TR2,4,5)
│ ├─ MSort(a,TR2,4,4) → 直接返回76
│ └─ MSort(a,TR2,5,5) → 直接返回13
│ └─ Merge([76,13], [13,76], 4,4,5) → 输出13 76
└─ MSort(a,TR2,6,7)
├─ MSort(a,TR2,6,6) → 直接返回27
└─ MSort(a,TR2,7,7) → 直接返回51
└─ Merge([27,51], [27,51], 6,6,7) → 输出27 51
└─ Merge([13,76,27,51], [13,27,51,76], 4,5,7) → 输出13 27 51 76
└─ Merge([38,49,65,97,13,27,51,76], [13,27,38,49,51,65,76,97], 0,3,7) → 最终排序结果
“`
void Merge(int SR[],int TR[],int i,int m,int n){
int k,j;
for( j=m+1,k=i;i<=m&&j<=n;++k){
if(SR[i]<=SR[j]){
TR[k]=SR[i++];
}
else
TR[k]=SR[j++];
}
if(i<=m)
for(int n1=i;n1<=m;n1++){
TR[k]=SR[n1];
k++;
}
if(j<=n)
for(int n1=j;n1<=n;n1++){
TR[k]=SR[n1];
k++;
}
}
void MSort(int SR[], int TR1[], int s, int t)
{
int TR2[8];
if(s == t)
TR1[s] = SR[s];
else
{
int m = (s+t)/2 ;
MSort(SR,TR2,s,m) ;
MSort(SR,TR2,m+1,t) ;
Merge(TR2,TR1,s,m,t) ;
int i;
for(i =0; i <=t ;i++)
printf(“%d “,TR1[i]);
printf(“\n”);
}
}
“`
## 结构体排序
利用sort()函数，传递数组起始地址和结束地址加一，另还需增设判断条件tmp，如果符合排序条件，则返回1，反之则返回0.
p1093奖学金
#include<bits/stdc++.h>
using namespace std;
struct score{
int c,m,e;
int id;
int sum;
}a[310];
bool temp(score a,score b){
if(a.sum>b.sum)
return 1;
else if(a.sum<b.sum)
return 0;
else{
if(a.c>b.c)
return 1;
else if(a.c<b.c)
return 0;
else{
if(a.id>b.id)
return 0;
else
return 1;
}
}
}
int main(){
int n,i,c=1;
cin>>n;
for(i=1;i<=n;++i){
a[i].id=i;
cin>>a[i].c>>a[i].m>>a[i].e;
a[i].sum=a[i].c+a[i].m+a[i].e;
}
sort(a+1,a+n+1,temp);
while(c<=5){
cout<<a[c].id<<" ";
cout<<a[c].sum<<endl;
c++;
}
return 0;
}
字典序
根据字符类型数据的优先顺序进行的排序
#include<bits/stdc++.h>
using namespace std;
string st[22];
int temp(string a,string b){
if(a+b>b+a)
return 1;
else
return 0;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>st[i];
sort(st+1,st+1+n,temp);
for(int i=1;i<=n;i++)
cout<<st[i];
return 0;
}
a+b>b+a表示在两个有a和b连接而成的字符串中,保留字典序大的排序方式。