排序.md

#sort函数的cmp函数编写 cmp函数如果返回真值，那么sort就不会对其做出改变 如果cmp返回假值，那么sort就会交换两个元素的位置。

cmp函数要求当a=a时，cmp返回假值。

#插入排序 插入排序原理为先对数组进行遍历，当遇到顺序与要求不符的部分时，将数字依次向前移动，直到遇到了相应的部分，然后交换数字。

# include<bits/stdc++.h>
# include<algorithm>
typedef long long ll;
using namespace std;
void insert_sort(int arr[],int n)
{
	int j;
	int temp;
	for(int i=1;i<n;i++)
	{
		if(arr[i]<arr[i-1])
		temp=arr[i];
		for( j=i-1;j>=0&&arr[j]>temp;j--)    //这里容易误写成j=i注意
		{
			arr[j+1]=arr[j];
		}
		arr[j+1]=temp;
	}
}
int main (void)
{
	int arr[10];
	for(int i=0;i<10;i++)
	arr[i]=rand()%(114514-i+1)+1;
	 
	insert_sort(arr,10);
	for(int i=0;i<10;i++)
	cout<<arr[i]<<" ";
	return 0;
	
}

#快速排序 这部分不做赘述，竞赛时通常只用stl，数据结构应付一下考试即可

# include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void quick_sort(int arr[],int l,int r)
{
	if(l>=r)    //注意这里的大小关系非常容易弄混
	return;
	int i=l-1;
	int j=r+1;
	int x=arr[(l+r)/2];
	while(i<j)
	{
		do i++;while(arr[i]<x);
		do j--;while(arr[j]>x);
		if(i<j)
		swap(arr[j],arr[i]);
	}
	quick_sort(arr,l,j);
	quick_sort(arr,j+1,r);
	
}
int main (void)
{
	int arr[1155];
	for(int i=0;i<15;i++)
	arr[i]=rand()%(114514-i+1)+1;
	for(int i=0;i<15;i++)
	cout<<arr[i]<<" ";
	cout<<endl;
	 
	quick_sort(arr,0,14);
	for(int i=0;i<15;i++)
	cout<<arr[i]<<" ";
	return 0;
	
}

#归并排序

# include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
ll temp[114514];
void merge_sort(ll arr[],ll l,ll r)
{
	if(l>=r)
	return;
	ll mid=l+r>>1;
	merge_sort(arr,l,mid);
	merge_sort(arr,mid+1,r);
	ll k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r)
	{
		if(arr[i]<arr[j]) temp[k++]=arr[i++];
		else temp[k++]=arr[j++];
	}
	while(i<=mid)  temp[k++]=arr[i++];
	while(j<=r) temp[k++]=arr[j++];
	for(int i=l,j=0;i<=r;i++,j++)
	arr[i]=temp[j];
}
int main (void)
{
	ll arr[114514];
	for(int i=0;i<=17;i++)
	arr[i]=rand()%(114514-i+1)+1;
	merge_sort(arr,0,17);
	for(int i=0;i<=17;i++)
	cout<<arr[i]<<endl;
	
}

#堆排序

这里的堆不是stl里面的堆，而是手写模拟的堆。 （1）堆排序需要满足几种要求： 1.求集合当中最小值/最大值 2.插入数据 3.删除最小值/最大值 4.删除任何一个元素 5.修改任何一个元素 堆是一颗完全二叉树，除了最后一层节点之外所有节点的叶子节点都是满的。 主要有小根堆和大根堆两种，下面主要介绍小跟堆。 小根堆意为任何一个节点的值都比他的叶子结点小，因此该树的根节点对应的值是最小值。

（2）堆的存储：（优先队列） 以数组存储，任何节点i的左儿子为2* i ;右儿子是2* i+1； 手动堆所要满足的操作主要有两个： up与down up操作：对堆中的所有元素，查看是否小于其父节点，如果是，则交换位置； down: 对堆中的所有元素，查看是否小于其叶子节点，如果是，则交换位置； 如此我们可以得到之前提到的操作的实现方法。

	1.求集合当中最小值/最大值   heap[1]
	2.插入数据                 heap[++size]=x;up(size);
	3.删除最小值/最大值         heap[1]=heap[size];size--;down(1);
	4.删除任何一个元素          与上述操作相同，heap[k]=heap[size];size--;up(k);down(k);
	5.修改任何一个元素

==注意下标的起点是1，因为一旦起点是0那么左儿子和右儿子的标签值将会一样

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    cnt = n;

    for (int i = n / 2; i; i -- ) down(i);

    while (m -- )
    {
        printf("%d ", h[1]);
        h[1] = h[cnt -- ];
        down(1);
    }

    puts("");

    return 0;
}

#基数排序

复杂度：o（k*(n+m)）（k是提取的关键字个数，n是待排序的数字个数，M是关键字的个数）

例如对九个三位数进行排序，那么k就是三（个十百），N就是9，M是10

空间复杂度为o(n+m).因此在排序时如果允许按照关键字进行查找，基数排序的速度非常快。如果元素的关键字取值范围不一定那么用不了基数排序。

			排序名称              最好时间复杂度   最坏情况    -平均情况    空间复杂度   稳定性

![[Pasted image 20230530193713.png]]