哈希排序(HashSort)

简单来说就是桶排，装桶。前提是要给定数据大小范围，比如待排序数组k中每个数大小为[0,n]，这样就要开一个范围比[0,n]略大的数组如a[n+5]并清零，然后循环一遍，把待排序数组的每个数据k[i]所对应的a[k[i]]进行+1操作。最后再循环一边，如果a[i]>0,则输出a[i]个i。
未经优化情况下
·时间复杂度：O(n)
·空间复杂度：O(n)
代码如下

#include<bits/stdc++.h>
using namespace std;
 int main(){
     int n,l,r;  //n为待排序数据规模，[l,r]是每个数据大小范围  
     scanf("%d%d%d",&n,&l,&r);
     int a[r-l+1+5]; //开一个比数据范围略大的数组用于装桶，注意由于是从数组下标是0开始的，最后输出还要加上一个下界
     memset(a,0,sizeof(a));//初始化，不然程序可能会爆掉
     for(int i=1;i<=n;i++){
         int temp;  //开一个临时变量存数据
         scanf("%d",&temp);//在线算法，一边输入一边处理数据
         if(l>0)//考虑左边界大于0情况 
         a[temp+l]++; //下标为当前输入数据值的数组元素+1，表示这个桶被多装一次
         else //考虑左边界小于0的情况 
         a[temp-l]++; 
     }
     for(int i=0;i<=r-l+1;i++)
       if(a[i]>0) //如果a[i]不为0，即a[i]已经有出现过，输出a[i]个i
           for(int j=1;j<=a[i];j++)
               printf("%d ",i+l);//输出，这里注意左边界的加减 
   return 0;
 }
输入： 5 
      -5 7
      0 -3 2 7 -5
输出：-5 -3 0 2 7

快速排序(QuickSort)

事实上，c++的库中自带的排序就是经过优化后的快速排序。
快速排序被绝大多数人所使用，它的时间复杂度和空间复杂度均很优秀，在随即情况下排序速度表现最为优良，当然代码和原理也略为复杂。
如果你使用C++语言，那么排序算法在头文件algorithm被引入后就是很简单的一句话搞定:

sort(start,end,cmp)//start:数组起始 end:数组结束 cmp:排序类型，可省略

原理：
每一趟排序，实现找出小于某个数(基准数)的所有内容，放到这个数左边；并将所有大于基准数的内容放到右边。再对左右内容重复用这种方法排序，重复若干次后完成排序。
对于一串无序数组（例：5 1 3 4 2）
设定两个键i,j。令i=1,j=5；
设置一个基准值key为数组中任意一个数，为了方便，这里通常就选取第一个数。key=5
然后j向左找j–直到发现比key小的数，i向右找i++直到发现比key大的值，然后交换i,j

#include <bits/stdc++.h>
using namespace std;
const int M=10005;//随便设置一个大数
int a[M];
//选择用迭代的方法实现
int qs(int x,int y){
    int i=x,j=y,t;//i,j用于维护 
    int k=a[x];//基准值 
    if(i>=j) return 0;//递归边界
      while(i<j){ //注意要保证i<j
          while((i<j)&&a[j]>=k)//没找到，继续移动
              j--;
     swap(a[i],a[j]);
          while((i<j)&&a[i]<k)
              i++;
     swap(a[i],a[j]);
      }
      qs(x,i-1);//对左半边进行递归
      qs(i+1,y);//对右半边进行递归
      return 0;
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    qs(1,n);//快排
    for(int i=1;i<=n;i++) printf("%d ",a[i]);//正序输出为1……n,倒序输出只要反一下即可
    return 0;
}   

输入： 5
5 2 1 3 4
输出： 1 2 3 4 5

归并排序(MergeSort)

赏

hql