排序--插入排序、希尔排序、快速排序、桶排序（代码）

//时间复杂度：O(n^2);//空间复杂度：O(1);//稳定#include <iostream>#include <algorithm>using namespace std;int n;int Array[10010];void insertsort(){   //初始有序序列的长度为1，故而从第二个元素开始进行插入排序    for(int j=1; j<n; j++)    {        if(Array[j]<Array[j-1])        {            int temp = Array[j];//保存待插元素的值            int index = j-1;            while(index>=0&&Array[index]>temp)            {//直到找到第一个不大于temp的值                Array[index+1] = Array[index];                index-=1;            }            Array[index+1] = temp;        }    }   }int main(){    while(cin>>n)    {       //Input        for(int i=0; i<n; i++)            cin>>Array[i];               //Sort        insertsort();       //Output        for(int i=0; i<n; i++)            cout<<Array[i]<<" ";        cout<<endl;    }    return 0;}
希尔排序
Source Code
//时间复杂度：平均【O（nlogn）】//空间复杂度：O（1）//不稳定#include <iostream>#include <algorithm>using namespace std;int n;int Array[10010];void shellsort(){    for(int gap=n/2;gap>=1;gap/=2)    {        for(int i=0;i<gap;i++)        {           //插入排序            for(int j=i+gap;j<n;j+=gap)            {                if(Array[j]<Array[j-gap])                {                                         int temp = Array[j];                    int index = j-gap;                    while(index>=0&&Array[index]>temp)                    {                        Array[index+gap] = Array[index];                        index -= gap;                    }Array[index+gap] = temp;                }            }        }           }}int main(){    while(cin>>n)    {       //Input        for(int i=0;i<n;i++)            cin>>Array[i];       //Sort        shellsort();       //Output        for(int i=0; i<n; i++)       cout<<Array[i]<<" ";        cout<<endl;           }    return 0;}
快速排序
Source Code
#include <iostream>#include <algorithm>#include <cstring>using namespace std;int n;int Array[10010];void quicksort(int l, int r){    if(l>=r)        return;    int i=l;    int j=r;    int key = Array[l];//以当前区间的第一个元素作为关键值                             //相当于在此处挖了个坑    while(i<j)    {        while(i<j&&Array[j]>=key)//从右边倒着找到第一个小于key的元素            j--;        Array[i] = Array[j];//在【j】处挖坑，填上原来的坑        while(i<j&&Array[i]<key)//从左边向后遍历找到第一个不小于key的元素            i++;        Array[j] = Array[i];//在【i】处挖坑，填上原来的坑    }Array[i] = key;//在最后一个坑里，填上key   //至此，Array[i]左边全部都是小于它的数    //Array[i]右边全部都是大于它的数    quicksort(l,i-1);//对左边排序    quicksort(i+1,r);//对右边排序}int main(){    while(cin>>n)    {       //Input        for(int i=0; i<n; i++)            cin>>Array[i];               //Sort        quicksort(0,n-1);         //Output        for(int i=0;i<n;i++)            cout<<Array[i]<<" ";        cout<<endl;    }    return 0;}
桶排序
Source Code
#include <iostream>#include <algorithm>#include <cstring>using namespace std;int n;int Array[10010];int Bucket[10010];int Min;int Max;void Bucketsort(){    memset(Bucket,0,sizeof(Bucket));//将桶清空    Min=Array[0];    Max=Array[0];    for(int i=0;i<n;i++)    {        Bucket[Array[i]]++;//编号为Array[i]的桶元素+1        Min = min(Min,Array[i]);//下边界        Max = max(Max,Array[i]);//上边界    }}int main(){    while(cin>>n)    {       //Input        for(int i=0; i<n; i++)            cin>>Array[i];        //Sort        Bucketsort();         //Output         for(int i=Min;i<=Max;i++)            if(Bucket[i]!=0)//桶不为空               cout<<i<<" ";         cout<<endl;    }    return 0;}