排序算法
归并排序
时间复杂度O(nlogn) 空间复杂度O(n)，稳定排序
就是给定两个有序数组，将两个数组合并在一起升序。
定义一个更大的数组，给定两个指针分别指向两个数组，每次取较小值放入新数组。
void mergeSort(int a[],int l,int r){
if(l>=r)return;
int mid=l+r>>1;
//分离数组
mergeSort(a,l,mid);
mergeSort(a,mid+1,r);
//合并l-r范围内的数组
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(a[i]<a[j])tmp[k++]=a[i++];
else tmp[k++]=a[j++];
}
//将剩余的数直接添加到序列的后面
while(i<=mid)tmp[k++]=a[i++];
while(j<=r)tmp[k++]=a[j++];
//拷贝到原数组
k=0;
for(int i=l;i<=r;i++){
a[i]=tmp[k++];
}
}
快速排序
快速排序的思想就是找到一个基准值，把序列分成两个部分，左半部分大于等于基准值，右半部分小于等于基准值。
然后对左右部分分别进行递归排序。
最差时间复杂度O(n^2) 和冒泡排序一样，平均时间复杂度 O(n*logn)不稳定排序
void quickSort(int a[],int l,int r){
if(l>=r)return;
int i=l-1,j=r+1;
//选取基准值
int std=a[l+r>>1];
while(i<j){
//为了考虑边界问题，边界问题有很多，直接找个正确的模板背过即可
while(a[--j]>std);
while(a[++i]<std);
if(i<j)swap(a[i],a[j]);
}
quickSort(a,l,j);//对左边排序
quickSort(a,j+1,r);//对右边排序
}
快速选择查找
快速选择查找就是基于快速排序，只对包含第k个值的区间排序，不需要排序整个数组
平均时间复杂度为O(n)，最坏时间复杂度为O(n^2)
//快速选择排序算法
void sort(int a[],int l,int r){
if(l>=r)return;
int i=l-1,j=r+1;
int std=a[l+r>>1];
while(i<j){
while(a[--j]>std);
while(a[++i]<std);
if(i<j)swap(a[i],a[j]);
}
if(j>=k-1)sort(a,l,j);
else sort(a,j+1,r);
}
桶排序
不基于比较的排序算法
通过统计值域内每个数据的个数，然后根据个数排序
int count[1002];//存放数的个数 这里数的值域是[0,1000]
void bucketSort(int n){
//统计每个数据的个数
for(int i=0;i<n;i++){
count[num[i]]++;
}
int cnt=0;
//值域为[0,1000]
for(int i=0;i<=1000;i++){
while(count[i]!=0){
num[cnt++]=i;//将数填回原数组
count[i]--;
}
}
}
堆排序(升序)
时间复杂度 O(nlogn)，不稳定排序
空间复杂度 O(1)
//对某个根节点调整为大根堆
//从上往下进行调整
void adjust_down(int *a,int n,int i){//i是需要调整的根节点的下标
int father=i;
int child=i*2+1;
while(child<n){
//比较孩子结点的大小，选出较大的那个
if((child+1)<=n-1&&a[child]<=a[child+1]) ++child;
//交换父节点和孩子结点，并顺着孩子结点向下继续调整
if(a[father]<a[child]){
int temp;
temp=a[child];
a[child]=a[father];
a[father]=temp;
father=child;
child=father*2+1;
}else{
//一旦不能继续调整就退出循环
break;
}
}
}
void heap_sort(int *a,int n){
//建立大根堆
//(n-1)/2为从后往前，第一个有孩子的结点
for(int i=(n-1)/2;i>=0;i--){
adjust_down(a,n,i);
}
//摘取大顶,与最后一个结点交换
for(int i=0;i<n-1;i++){
int temp=a[0];
a[0]=a[n-i-1];
a[n-i-1]=temp;
adjust_down(a,n-i-1,0);
}
}
堆模拟
以小根堆为例：
插入操作：插入到末尾，并向上调整。
删除第k个插入的元素：用末尾元素替代。并向上调整或向下调整（只会执行一个）
修改第k个插入的元素：修改后，向上调整或向下调整（只会执行一个）
下面展示调整代码：
/*
为了能够维护数组下标和插入顺序的映射关系，这里引入两个辅助数组
get_idx[u]用来获得数组下标为u的插入次序.
get_index[idx]用来获得第idx个插入的数组的下标（在数组中的位置）
这里的idx和链表、Trie数组中的idx作用类似。按道理，应该按照结构体的方式来实现这些数据结构的，但是做算法题一般用数组模拟，主要是因为比较快。原来这两个属性都是以结构体的方式联系在一起的，现在如果用数组模拟，就利用idx联系节点的属性(w、ne、e)
*/
//节点交换
void heap_swap(int a,int b){
//先维护序号和数组下标的数组
swap(get_index[get_idx[a]],get_index[get_idx[b]]);
swap(get_idx[a],get_idx[b]);
swap(num[a],num[b]);
}
//向上调整
void adjust_up(int i){
int child=i;
int fa=child/2;
while(fa && num[child]<num[fa]){
heap_swap(child,fa);
child=fa;
fa=child/2;
}
}
//向下调整
void adjust_down(int i){
int fa=i;
int child=2*i;
while(child<=siz){
if(child+1<=siz && num[child]>num[child+1])child++;
if(num[fa]>num[child]){
heap_swap(fa,child);
fa=child;
child=2*fa;
}else break;
}
}