【C++】几个常见的简单排序算法

1.冒泡排序
2.直接插入排序
3.堆排序
4.快速排序
5.归并排序

#include<iostream>
#include<memory>
#include<vector>

using namespace std;

const int N = 10;
int *arr;
int count = 0;//计数器
int swap(int&,int&);
int print(int*);
int adjust(int*,int,int);
int init(int);
int Partition(int*,int,int);
int mergeArr(int*,int,int,int);

int bubbleSort(int*);
int insertSort(int*);
int heapSort(int*);
int quickSort(int*,int,int);
int mergeSort(int*,int,int);

int init(int model){//初始化数组
    count=0;
    switch(model){
        case 1: arr=new int[N]{12,14,29,44,45,45,66,75,76,77};break;//正序
        case 2: arr=new int[N]{77,76,75,66,45,45,44,29,14,12};break;//逆序
        default: arr=new int[N]{29,45,66,76,45,12,14,75,77,44};     //乱序
    }
    return 0;
}
int swap(int &a,int &b){//交换
    int tmp = a;
    a = b;
    b = tmp;
    return 0;
}
int print(int *arr){//打印  
    cout<<*arr;
    for(int i=1;i<N;++i){
        cout<<" "<<*(arr+i);
    }
    cout<<", count = "<<count<<endl;
    return 0;
}

int bubbleSort(int *arr){//冒泡排序
    for(int i=0;i<N;++i){
        int flag = 0;
        for(int j=0;j<N-i-1;++j){
            ++count;
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]);
                flag=1;
            }
        }
        if(flag==0) break;
    }
}
int insertSort(int *arr){//直接插入排序
    int i,j;
    for(i=0;i<N;++i){
        int tmp=arr[i];
        for(j=i-1;j>=0;--j){
            if(arr[j]>tmp){
                arr[j+1]=arr[j];++count;
            }
            else break;
        }
        arr[j+1]=tmp;
    }
    return 0;
}

int adjust(int *arr,int loc,int n){//大根堆调整
   
    int left=loc*2+1;
    int right=(loc+1)*2;
    if(left<n&&arr[loc]<arr[left]){
        swap(arr[loc],arr[left]);++count;
        if((left+1)*2<=n) adjust(arr,left,n);
    }
    if(right<n&&arr[loc]<arr[right]){
        swap(arr[loc],arr[right]);++count;
        if((right+1)*2<=n) adjust(arr,right,n);
    }
   
    return 0;
}
int heapSort(int *arr){//堆排序
    for(int i=N/2-1;i>=0;--i){
        adjust(arr,i,N);
    }
    for(int i=N-1;i>0;--i){
        swap(arr[i],arr[0]);
        adjust(arr,0,i);
    }
    return 0;
}

int Partition(int *arr,int low, int high)//部分交换
{
    int pivotkey = arr[low];
    while(low<high){
        while(low<high&&arr[high]>=pivotkey) --high;
        arr[low]=arr[high];++count;
        while(low<high&&arr[low]<=pivotkey) ++low;
        arr[high]=arr[low];++count;
    }
    arr[low]=pivotkey;++count;
    return low;
}
int quickSort(int *arr,int low,int high){//快速排序
   
    if(low<high){
        int pivotloc = Partition(arr,low,high);
        quickSort(arr,low,pivotloc-1);
        quickSort(arr,pivotloc+1,high);
    }
   
    return 0;
}

int mergeArr(int *arr,int left,int mid,int right){//合并两个有序分组
    int tmpLeft = left;
    int tmpMid = mid+1;
    shared_ptr<vector<int>> p(new vector<int>());
    while(tmpLeft<=mid&&tmpMid<=right){
        if(arr[tmpLeft]<=arr[tmpMid]) p->push_back(arr[tmpLeft++]);
        else p->push_back(arr[tmpMid++]);
    }
    while(tmpLeft<=mid) p->push_back(arr[tmpLeft++]);
    while(tmpMid<=right) p->push_back(arr[tmpMid++]);
    for(auto iter = p->begin();iter!=p->end();++iter,++left){
        arr[left]=*iter;
        ++count;
    }
    return 0;
}
int mergeSort(int *arr,int left,int right){//归并排序
    if(left<right){
        int mid = (left+right)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        mergeArr(arr,left,mid,right);
    }
    return 0;
}
int main(int argc,char **argv){
   
    int model = 0;// 1:正序 2:倒序 其他:乱序
    init(model);print(arr);
   
    bubbleSort(arr);cout<<"bubble:";print(arr);init(model);
    insertSort(arr);cout<<"insertSort:";print(arr);init(model);
    heapSort(arr);cout<<"heapSort:";print(arr);init(model);
    quickSort(arr,0,N-1);cout<<"quickSort:";print(arr);init(model);
    mergeSort(arr,0,N-1);cout<<"mergeSort:";print(arr);init(model);
    return 0;
}

发布者

VC-Robot

游戏爱好者,动漫迷,C++修炼中,编程菜鸟,随性

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.