数据结构与算法(c++)--排序算法-蒲公英云

数据结构与算法(c++)–排序算法

这篇文章主要简单记录下数据结构与算法中的排序算法技术

书签

插入排序
- 直接插入排序
- 希尔排序
交换排序
- 起泡排序
- 快速排序
选择排序
- 简单选择排序
- 堆排序
归并排序
- 二路归并排序
分配排序
- 桶式排序
各排序的时空性能

插入排序

直接插入排序

基本思想：依次将待排序序列中的每一个记录插入到已排好序的序列中，直到全部记录都安排好序。

在这里插入图片描述

直接插入排序代码：

void Insertsort(int data[],int length){
    //直接插入排序
    int i,j,temp;
    for (i=1;i<length;i++){
     //排序进行length-1次
        temp=data[i];   //获取待插元素
        for(j=i-1;j>=0&&temp<data[j];j--){
     //寻找插入位置
            data[j+1]=data[j];
        }
        data[j+1]=temp;
    }
}

希尔排序

基本思想：先将整个待排序记录序列分割成若干个子序列，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

希尔排序代码：

void Shellsort(int data[],int length){
    //希尔排序
    int d,i,j,temp;
    for (d=length/2;d>=1;d=d/2){
    //获取增量d，然后再进行这届插入排序
        for (i=d;i<length;i++){
            temp=data[i];   //获取待插元素
            for(j=i-d;j>=0&&temp<data[j];j=j-d)
                data[j+d]=data[j];
            data[j+d]=temp;
        }
    }
}

交换排序

起泡排序

基本思想：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止

在这里插入图片描述

起泡排序代码：

void Bubblesort(int data[],int length){
    //起泡排序
    int j,exchange,bound,temp;
    exchange=length-1;//第一趟起泡排序的区间是[0~length-1]
    while(exchange!=0){
        bound=exchange;
        exchange=0;
        for(j=0;j<bound;j++){
            if(data[j]>data[j+1]){
                temp=data[j];
                data[j]=data[j+1];
                data[j+1]=temp;
                exchange=j;
            }
        }
    }
}

快速排序

基本思想：首先选定一个轴值，将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

在这里插入图片描述

快速排序代码：

int Partition(int data[],int first,int last){
    //快速排序1
    int i=first,j=last,temp;
    while(i<j){
        while(i<j&&data[i]<=data[j])
            j--;
        if(i<j){
            temp=data[i];
            data[i]=data[j];
            data[j]=temp;
            i++;
        }
        while(i<j&&data[i]<=data[j])
            i++;
        if(i<j){
            temp=data[i];
            data[i]=data[j];
            data[j]=temp;
            j--;
        }
    }
    return i;
}
void Quicksort(int data[],int first,int last){
    //快速排序2
    if(first<last){
        int pivot = Partition(data,first,last);  //一次划分
        Quicksort(data,first,pivot-1);  //对左侧子序列进行快速排序
        Quicksort(data,pivot+1,last);   //对右侧子序列进行快速排序
    }
}

选择排序

简单选择排序

基本思想：第i趟排序在待排序列中 ri ~ rn(1 ≤ i ≤ n-1)中选取最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。

在这里插入图片描述

简单选择排序代码

void Selectsort(int data[],int length){
    //简单选择排序
    int i,j,index,temp;
    for(i=0;i<length-1;i++){
        index=i;
        for(j=i+1;j<length;j++)//在无序区获取最小的序列
            if(data[j]<data[index]) index=j;
        if(index!=i){
            temp=data[i];
            data[i]=data[index];
            data[index]=temp;
        }
    }
}

堆排序

基本思想：首先将待排序序列调整成一个堆，此时，选出了堆中所有记录的最大者即堆顶元素，然后将堆顶记录移走，并将剩余记录再调整成堆，这样又找出次大记录，以此类推，直到堆中只有一个记录。

在这里插入图片描述

堆排序代码

void Sift(int data[],int k,int last){
    //堆排序1
    int i=k;
    int j=2*i+1;
    int temp;
    while(j<=last){
        if(j<last && data[j]<data[j+1]) j++;
        if(data[i]>data[j]) break;
        else{
            temp=data[i];
            data[i]=data[j];
            data[j]=temp;
            i=j;
            j=2*i+1;
        }
    }
}
void Heapsort(int data[],int length){
    //堆排序2
    int i,temp;
    for(i=ceil(length/2)-1;i>=0;i--){
        Sift(data,i,length-1);
    }
    for(i=1;i<length;i++){
        temp=data[0];
        data[0]=data[length-i];
        data[length-i]=temp;
        Sift(data,0,length-i-1); //重建堆
    }
}

归并排序

二路归并排序

基本思想：将待排序序列{r1, r2, …,rn}划分为两个长度相等的子序列{r1, r2, …,rn/2}和{rn/2+1, rn/2+2, …,rn}，分别对这两个子序列进行排序，得到两个有序子序列，再将这两个有效子序列合并成一个有效子序列。

二路归并排序代码

void Merge(int data[],int first1,int last1,int last2,int length){
    //二路归并排序1
    int *temp=new int [length+1];//申请辅助空间
    int i=first1;
    int j=last1+1;
    int k=first1;
    while(i<=last1&&j<=last2){
        if(data[i]<=data[j]) temp[k++]=data[i++];
        else temp[k++]=data[j++];
    }
    while(i<=last1) temp[k++]=data[i++];
    while(j<=last2) temp[k++]=data[j++];
    for(i=first1;i<=last2;i++) data[i]=temp[i];//辅助空间数据传回数组
    delete[] temp;
}
void Mergesort(int data[],int first,int last,int length){
    //二路归并排序2
    if(first==last) return;//子序列中只有一个记录
    else{
        int mid=(first+last)/2;
        Mergesort(data,first,mid,length);//归并排序左半子序列
        Mergesort(data,mid+1,last,length);//归并排序右半子序列
        Merge(data,first,mid,last,length);//合并已排序的子序列
    }
}

分配排序

桶式排序

基本思想：获取待排序序列中的最大值m，设置m+1个桶，将数值为i的记录分配到第i个桶中，其余无数值的桶为空桶，然后再将各个桶中的记录（忽略空桶）依次取出。

桶式排序代码

int Findmax(int data[],int length){
    //桶式排序1
    int i,max;
    max=data[0];
    for(i=1;i<length;i++){
        if(data[i]>max)
            max=data[i];
    }
    return max; //获取最大值来创建桶数组
}
void Bucketsort(int data[],int length){
    //桶式排序2
    int i,m;
    m=Findmax(data,length);
    int *count=new int[m+1];    //创建桶数组
    for(i=0;i<=m;i++)           //桶数组全部数值赋予0
        count[i]=0;
    for(i=0;i<length;i++)       //待排序列的数值对应的桶数组下标，并其数值赋予1
        count[data[i]]++;
    for(i=0;i<=m;i++){
              //取出
        while(count[i]>0){
            cout<<i<<" , ";
            count[i]--;
        }
    }
}