数据结构中九大排序算法的实现！ 🙈

目录

排序算法效率比较

选择排序

首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

void select_sort(vector<int>&v){
    for(int i=0;i<v.size();i++){
        int index=i;
        for(int j=i+1;j<v.size();j++){
            if(v[index]>v[j]){
                index=j;
            }
        }
        int temp=v[index];
        v[index]=v[i];
        v[i]=temp;
    }
}

直接插入排序

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

void insert_sort(vector<int>&v){
    int i,j,k;
    for(i=1;i<v.size();i++){
        for(j=i-1;j>=0;j--){
            if(v[j]<v[i])break;
        }
        if(j!=i-1){
            int temp=v[i];
            for(k=i-1;k>j;k--){
                v[k+1]=v[k];
            }
            v[k+1]=temp;
        }       
    }
}

冒泡排序

依次比较相邻的两个元素，若前面的元素比后面的元素大（如果要从大到小排序可以用‘<’）则交换，知道最后的元素为最大（最小）；再继续从头遍历执行相同的操作。像泡泡一样把最大（最小）的元素浮到水面。

void bubblesort(vector<int>&v){
    for(int i=v.size()-1;i>=0;i--){
        for(int j=1;j<=i;j++){
            if(v[j]<v[j-1]){
                int temp=v[j];
                v[j]=v[j-1];
                v[j-1]=temp;
            }
        }
    }
}

希尔排序

希尔排序的本原理是：将待排序的一组元素按一定间隔分为若干个序列，分别进行插入排序。开始时设置的“间隔”较大，在每一轮排序中将间隔逐步减小，直到“间隔”为1，也就是最后一步是进行简单插入排序。

void shell_sort(vector<int>&v){
    int i,j,gap;
    for(gap=v.size()/2;gap>0;gap/=2){   //间隔大小 
        for(i=0;i<gap;i++){ //gap个组 
            for(j=i+gap;j<v.size();j+=gap){
                if(v[j]<v[j-gap]){
                    int temp=v[j];
                    int k=j-gap;
                    while(k>=0&&v[k]>temp){
                        v[k+gap]=v[k];
                        k-=gap;
                    }
                    v[k+gap]=temp;
                }               
            }
        }
    }
}

堆排序

堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）；每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。

void maxheap_down(vector<int>&v,int start,int end){
    int c=start;
    int l=2*c+1;
    int temp=v[c];
    for(;l<=end;c=l,l=2*l+1){
        if(l<end&&v[l]<v[l+1]){
            l++;
        }
        if(temp>=v[l])break;
        else{
            v[c]=v[l];
            v[l]=temp;
        }
    }
}

void heap_sort(vector<int>&v){
    int i;
    for(i=v.size()/2-1;i>=0;i--){   //建堆
        maxheap_down(v,i,v.size()-1);
    }
    for(i=v.size()-1;i>0;i--){
        int temp=v[0];
        v[0]=v[i];
        v[i]=temp;
        maxheap_down(v,0,i-1);  //调整
    }
}

快速排序

（类似于选择排序的定位思想）选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成。

void quickSort(vector<int>&v,int begin,int end){
    if(begin>=end-1)return ;
    int L=begin,R=end-1;
    int index=v[L];

    while(L<R){
        while(L<R){
            if(v[R]<index){
                v[L++]=v[R];
                break;
            }
            --R;
        }
        while(L<R){
            if(v[L]>index){
                v[R--]=v[L];
                break;
            }
            ++L;
        }
    }
    v[L]=index;
    quickSort(v,begin,L);
    quickSort(v,R+1,end);
}

完整程序

#include<bits/stdc++.h>
using namespace std;
void bubblesort(vector<int>&v){
    for(int i=v.size()-1;i>=0;i--){
        for(int j=1;j<=i;j++){
            if(v[j]<v[j-1]){
                int temp=v[j];
                v[j]=v[j-1];
                v[j-1]=temp;
            }
        }
    }
}

void select_sort(vector<int>&v){
    for(int i=0;i<v.size();i++){
        int index=i;
        for(int j=i+1;j<v.size();j++){
            if(v[index]>v[j]){
                index=j;
            }
        }
        int temp=v[index];
        v[index]=v[i];
        v[i]=temp;
    }
}

void insert_sort(vector<int>&v){
    int i,j,k;
    for(i=1;i<v.size();i++){
        for(j=i-1;j>=0;j--){
            if(v[j]<v[i])break;
        }
        if(j!=i-1){
            int temp=v[i];
            for(k=i-1;k>j;k--){
                v[k+1]=v[k];
            }
            v[k+1]=temp;
        }       
    }

}

void shell_sort(vector<int>&v){
    int i,j,gap;
    for(gap=v.size()/2;gap>0;gap/=2){   //间隔大小 
        for(i=0;i<gap;i++){ //gap个组 
            for(j=i+gap;j<v.size();j+=gap){
                if(v[j]<v[j-gap]){
                    int temp=v[j];
                    int k=j-gap;
                    while(k>=0&&v[k]>temp){
                        v[k+gap]=v[k];
                        k-=gap;
                    }
                    v[k+gap]=temp;
                }               
            }
        }
    }
}

void maxheap_down(vector<int>&v,int start,int end){
    int c=start;
    int l=2*c+1;
    int temp=v[c];
    for(;l<=end;c=l,l=2*l+1){
        if(l<end&&v[l]<v[l+1]){
            l++;
        }
        if(temp>=v[l])break;
        else{
            v[c]=v[l];
            v[l]=temp;
        }
    }
}

void heap_sort(vector<int>&v){
    int i;
    for(i=v.size()/2-1;i>=0;i--){
        maxheap_down(v,i,v.size()-1);
    }
    for(i=v.size()-1;i>0;i--){
        int temp=v[0];
        v[0]=v[i];
        v[i]=temp;
        maxheap_down(v,0,i-1);
    }
}

void quickSort(vector<int>&v,int begin,int end){
    if(begin>=end-1)return ;
    int L=begin,R=end-1;
    int index=v[L];

    while(L<R){
        while(L<R){
            if(v[R]<index){
                v[L++]=v[R];
                break;
            }
            --R;
        }
        while(L<R){
            if(v[L]>index){
                v[R--]=v[L];
                break;
            }
            ++L;
        }
    }
    v[L]=index;
    quickSort(v,begin,L);
    quickSort(v,R+1,end);
}



int main(){
    int N,val;
    vector<int>v;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>val;
        v.push_back(val);
    }
//  bubblesort(v);  //冒泡排序
//  select_sort(v); //选择排序
//  insert_sort(v); //插入排序
//  shell_sort(v);  //希尔排序
//  quickSort(v,0,v.size());    //快速排序
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<' ';
    }
    return 0;
}