算法半期考复习——十大排序算法之六

为了迎接算法设计课半期考，把几个比较简单的算法写了一写

#include
#include
#include

using namespace std;


void bubbleSort(vector &q){    //冒泡排序，时间复杂度O（N^2）
    for(int i=q.size()-1;i>0;i--)
    {
        bool flag=false;
        for(int j=0;j+1<=i;j++){
            if(q[j]>q[j+1]){
                swap(q[j],q[j+1]);
                flag=true;
            }
        }
        if(!flag)
        break;
    }
}


void selectSort(vector &q){  //选择排序,O(N^2)
   int min,len=q.size();
   for(int i=0;i &q){   //插入排序,O(N^2)
    for(int i=1;i=0;--j){  //无序区第一个元素前的都是有序区
            if(q[j]>tmp)
            {
                q[j+1]=q[j];
                q[j]=tmp;
            }
            else break;
        }
    }
}



void shellSort(vector &q){      //希尔排序
    int gap=q.size()/2;
    while(gap){
        for(int i=gap;i=0;j-=gap){
                if(q[j]>t)
                q[j+gap]=q[j];
                else
                break;
            }
            q[j+gap]=t;
        }
        gap/=2;
    }
}



void mergeSort(vector &q,int l,int r){     //归并排序O(nlogn)
    if(l>=r)
      return;
    int mid=l+r>>1;
    mergeSort(q,l,mid);
    mergeSort(q,mid+1,r);
    static vector w;
    w.clear();
    int i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]>q[j])
        w.push_back(q[j++]);
        else
        w.push_back(q[i++]);
    }
    while (i<=mid)
        w.push_back(q[i++]);
    while(j<=mid)
        w.push_back(q[j++]);
    for(int i:w)
        q[l++]=i;
}

void quickSort(vector &q,int l,int r){   //快排，yyds，O(nlogn)
    if(l>=r)
    return;
    int i=l-1,j=r+1,x=q[l+rand()%(r-l+1)];//哨兵
    while(ix);//找小于x的
        do i++;
        while(q[i] q;
    cin>>n;
    for(int i=0;i>t;
        q.push_back(t);
    } 
    
    for(int i=0;i