十大排序（二）

6.快速排序

每次用左边第一个元素的当中轴元素，然后从数组两头分别遍历，每次把左边大于中轴元素的与右边小于中轴元素的交换，最后把中轴元素归位。递归这个过程。

性质：

时间复杂度：O(nlogn)
空间复杂度：O(logn)
非稳定排序
原地排序

#include <iostream>
#include <algorithm>
using namespace std;
#define Maxn 120

int a[Maxn],n;
void quickSort(int left,int right){
    if(left>=right)
        return ;
    int i,j,base,temp;
    i=left;
    j=right;
    base=a[left];
    
    while(i<j){
        while(a[j]>=base&&i<j){
            j--;
        }
        while(a[i]<=base&&i<j){
            i++;
        }
        if(i<j){
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    a[left]=a[i];
    a[i]=base;
    quickSort(left,i-1);
    quickSort(i+1,right);
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    quickSort(0,n-1);
    
    cout<<a[0];
    for(int i=1;i<n;i++){
        cout<<" "<<a[i];    
    }
    
    return 0;
}

7.堆排序

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。
堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

性质：

时间复杂度：O(nlogn)
空间复杂度：O(1)
非稳定排序
原地排序

#include <bits/stdc++.h>
using namespace std;
#define Maxn 120
int a[Maxn];
int n;
void down(int parent,int size){
    int child=parent*2+1;
    while(child<size){
        if(a[child]<a[child+1]&&child+1<size){
            child++;
        }
        if(a[parent]<a[child]){
            int temp=a[parent];
            a[parent]=a[child];
            a[child]=temp;
            parent=child;
        }
        child=child*2+1;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    
    for(int i=n/2-1;i>=0;i--){    //初始化堆
        down(i,n); 
    } 
    
    for(int i=n-1;i>0;i--){
        int temp=a[0];
        a[0]=a[i];
        a[i]=temp;
        down(0,i);
        
    }
     cout<<a[0];
    for(int i=1;i<n;i++){
        cout<<" "<<a[i];
    }
    
    return 0;
}

8.计数排序

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。

基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

性质（k为临时数组的大小）：

时间复杂度：O(n+k)
空间复杂度：O(k)
稳定排序
非原地排序

#include<bits/stdc++.h>
using namespace std;

int minn=1000,maxn=-1,n;
int a[1000];
int main(){
    cin>>n;
    memset(a,0,sizeof(a));
    
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        a[x]++;
        if(x>maxn){
            maxn=x;
        }
        if(x<minn){
            minn=x;
        }
    }
    int flag=1;
    for(int i=minn;i<=maxn;i++){
        for(int j=1;j<=a[i];j++){
            if(flag){
                cout<<i;
            }else{
                cout<<" "<<i;
            }    
        }
    }
    
    return 0;
}

9.桶排序

桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。

之后每个桶里面的数据就是有序的了，我们在进行合并汇总。

假如我们搞很多桶，12就放到12的位置，多个12执行加一的操作，那不是就跟计数排序一样了嘛。我有点迷，看了几篇博客没有合适的。就不贴代码了。

性质

时间复杂度：O(n+k)
空间复杂度：O(n+k)
稳定排序
非原地排序

10.基数排序

先按个位数对数组进行排序，然后按十位数对数组进行排序，就这样，排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是用“桶”来排序的。

性质

时间复杂度：O(kn)
空间复杂度：O(n+k)
稳定排序
非原地排序

这个注解写的也太详细了，我不是想偷懒才搬代码的。

#include <iostream>
 
using namespace std;
/*********************************************************
Function:rxsort
Description:基数排序
Input:
    数组A[l,h]；
    数组中最大元素的位数d，例如最大数为999，则d为3；
    进制数k，如果是10进制数，k为10；
Output:排序好的数组；
Others：对数字1234来说，预定第0位为4，第1位为3，依次类推；
*********************************************************/
bool rxsort(int A[],int l,int h,int d,int k){
    if(NULL==A||l>h)
        return false;
    int size = h-l+1;
 
    int* counts = new int[k];//用于计数排序的辅助数据，详见计数排序
    int* temp = new int[size];//用于存储重新排序的数组
    int index;
    int pval=1;
    //依次处理不同的位
    for(int i=0;i<d;i++){
        //counts数组清零
        for(int j=0;j<k;j++)
            counts[j] = 0;
 
        for(int j=l;j<=h;j++){
            /*
            1.data[j]/pval：去掉数字data[j]的后i个数，例如：
            当data[j]=1234,i=2时，此时pval=100,data[j]/pval=12;
            2.(data[j]/pval)%k：取数字data[j]/pval的最后一位数
            3.(int)(data[j]/pval)%k:取数字data[j]的第i位数
            */
            index = (int)(A[j]/pval)%k;
            /*
            统计数组A中每个数字的第i位数中各个数字的频数,用于计数排序；
            */
            counts[index]++;
        }
        //计算累加频数，用户计数排序
        for(int j=1;j<k;j++)
            counts[j] = counts[j] + counts[j-1];
        //使用倒数第i+1位数对A进行排序
        for(int j=h;j>=l;j--){
            index = (int)(A[j]/pval)%k;
            temp[counts[index]-1] = A[j];
            counts[index]--;
        }
        //将按第i为数排序后的结果保存回数组A中
        for(int j=0;j<size;j++)
            A[j+l] = temp[j];
        //更新pval
        pval = pval*k;
    }
    delete[] counts;
    delete[] temp;
}
 
int main(){
    int A[] = {712,303,4,18,89,999,70,26};
    rxsort(A,0,7,3,10);
    for(int i=0;i<8;i++)
        cout<<A[i]<<" ";
}