快排模板 归并模板 及其应用

 快速排序：

int partition(int arr[],int low,int high)
{
    int pivot = arr[high];
    int i = (low - 1);
    for(int j = low;j <= high - 1; ++j)
    {
        if(arr[j] <= pivot)//若从大到小排，改成>=即可
        {
          i++;
          swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[high]);
    return (i+1);
}
void quickSort(int arr[],int low,int high)
{
    if(low<high)
    {
        int pi = partition(arr,low,high);
        quickSort(arr,low,pi-1);
        quickSort(arr,pi+1,high);
    }
}

 

快排应用————查找第k大数    O(n) 

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int f[1005];
int partition(int arr[],int low,int high)
{
    int pivot = arr[high];
    int i = (low - 1);
    for(int j = low;j <= high - 1; ++j)
    {
        if(arr[j] >= pivot)//查找第k小反过来就行，<=
        {
          i++;
          swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[high]);
    return (i+1);
}
void quickSort(int arr[],int low,int high,int idx)
{
    if(low<high)
    {
        int pi = partition(arr,low,high);
        if(pi>=idx)  quickSort(arr,low,pi-1,idx);
        else if(pi<idx) quickSort(arr,pi+1,high,idx);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i =1;i<=n;++i)
    {
      cin>>f[i];
    }
    int idx = 5;
    quickSort(f,1,n,idx);
    cout<<f[idx];
}

 

归并模板

void merge_sort(int a[],int i,int j)//主调函数
{
    int k;
    if(i<j)
    {
        k=(i+j)/2;
        merge_sort(a,i,k);
        merge_sort(a,k+1,j);
        merge(a,i,k,k+1,j);
    }
}
void merge(int a[],int p,int q,int s,int t)
{//将有序段a[p..q]和有序段a[s..t]合并到b[p..t]
      int i,j,k,b[10]; //b为合并场地(与源数组大小相同）
      i=p;j=s;k=p;  //三个指针i,j,k
      while((i<=q)&&(j<=t))//两个有序段都不空
      if(a[i]<a[j]) b[k++]=a[i++];
      else b[k++]=a[j++];
      while(i<=q) b[k++]=a[i++];//处理有序段1的剩余元素
      while(j<=t) b[k++]=a[j++];//处理有序段2的剩余元素
      for(i=p;i<=t;i++)
      a[i]=b[i];//将合并后的有序段移回源数组a
}

 

归并应用————逆序对 

void merge(int l,int mid,int r){//求逆序对
    //合并a[l~mid] 与 a[mid+1~r]
   //a是待排数组，b是临时数组，cnt是逆序对个数
   int i = l, j = mid +1;
   for(int k = l;k <= r;++k)
   {
       if(j>r||i <= mid && a[i] < a[j]) b[k] = a[i++];
       else b[k] = a[j++],cnt += mid - i +1;
   }
   for(int k = l;k <= r;++k) a[k] = b[k];
}

转载自 https://blog.csdn.net/qq_43408238