您的位置: 首页  >  文章  >  归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

分类: 文章 • 2024-01-06 21:54:16

1，计数排序

计数排序是特殊的排序，这种排序不需要进行元素比较，对于计数排序而言，该排序算法是利用数组下标来确定元素的位置的。

  • 让我们来看一个例子

假设数组中有20个随机整数，取值范围是0-10，要求利用最快速度把20个数进行从小到大排序。

如何给这些无序的数组排序呢？

考虑到这些数只能够在1，2，3，4，5，6，7，8，9，10这11个数中取值，可以根据此，建立一个长度为11的数组。数组的下标从0到10，元素初始值全部是0。

0 0 0 0 0 0 0 0 0 0

      假设20个随机数如下所示

9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9，7，9

下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加一操作

例第一个数是9，那么数组下标为9的元素加1

0 0 0 0 0 0 0 0 0 1

第二个数是3，则数组下标是3的元素加一

0 0 0 0 1 0 0 0 0 1

继续遍历数列并修改数组。。。。进行完之后状态如下：

1 2 1 3 2 2 1 2 1 4

有了统计结果之后，排序就是直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。

代码如下所示：

void count_Sort(int *a,int length){
  int max=a[0];
  //找出其中最大的数，为了设定统计数组的大小
  for(int i=1;i<length;i++){
    if(max<a[i]){
      max=a[i];
    }
  }
  //进行统计计数
  int counta[max+1]={0};
  int counta_length=sizeof(counta)/sizeof(int);
  for(int i=0;i<length;i++){
    counta[a[i]]++;
  }
  //进行输出
  int index=0;
  for(int i=0;i<counta_length;i++){
    for(int j=0;j<counta[i];j++){
      a[index++]=i;
    }
  }
}

2，计数排序的优化

下面来说说如何对计数排序进行优化。

比如说有几个人的成绩分别是：小红：90，小橙：99，小黄：95，小绿：94，小青：95。将这些学生的成绩按照从低到高的顺序进行排序，如果成绩相同按照原来的先后顺序。

首先，还是建立统计数组countArray如下所示：

归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

但是两个95分的学生的成绩不知道顺序如何排列，为了解决这个问题我们队统计数组进行变形，得到如下数组

归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

具体的变化过程是：从统计数组的第二个元素开始，每一个元素的值都是本元素的值加上前面的所有的元素值之和。这样做的目的是把整数放到最终排序的位置上去，比如9对应的元素是5，则99最终应该排在第五位。

下面我们对照成绩表把统计数组中的元素遍历出来，并排序，注意：每遍历一个，就在统计数组中将其值减1，从后往前遍历成绩表，第一个是小青：95，对应的值为4，则表示小青95分应该排在第四位，同时统计数组中下标5对应的值应减1变为3，接着小绿94分，应该排在第二位，同时修改统计数组对应的值为1，下面是小黄95，对应的值为3，应该排在第三位修改下标为2(实际上已经用不到了)，下面是小橙99分，对应的值为5，应该排在第五位，修改下标值为4(实际上已经用不到了)，最后是小红90分，对应的值为1，应该排在第一位，修改下标的值为0(实际上已经用不到了)。这样通过遍历得到一个新的排序：

归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

设原始数列规模是n,最大最小整数差是m，则时间复杂度为o(n+m)，空间复杂度为o(m)。计数排序的缺点是当最大值最小值差距过大时，不适用计数排序，当元素不是整数值，不适用计数排序。
代码展示：

//计数排序优化算法
void count_Sort1(int *a,int length){
  int max=a[0];//找到最大的做计数数组的长度
  int min=a[0];//找到最小的作为最小基准数
  for(int i=1;i<length;i++){
    if(min>a[i]){
      min=a[i];
    }
    if(max<a[i]){
      max=a[i];
    }
  }
  int d=max-min;
  int countarroy[d+1]={0};
  int countarroy_length=sizeof(countarroy)/sizeof(int);
  //在统计数组countarroy中存入每个数据（以个位值存入）
  for(int i=0;i<length;i++){
    countarroy[a[i]-min]++;
  }
  //统计数组做变形，后面的数组等于前面的元素之和。
  //作用：是让统计数组存储的元素值等于相应整数的最终排序位置的序号
  for(int i=1;i<countarroy_length;i++){
    countarroy[i]+=countarroy[i-1];
  }
  //倒序遍历原始数组，从统计数组中找到正确位置，输出结果数组
  int sortedarroy[length]={0};//结果数组
  for(int i=length-1;i>=0;i--){
    sortedarroy[countarroy[a[i]-min]-1]=a[i];
    countarroy[a[i]-min]--;
  }
  for(int i=0;i<length;i++){
    a[i]=sortedarroy[i];
  }
}

3，归并排序

归并排序是利用分治的思想，先分后治

归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

 归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

 详细“治”的步骤：
归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

 归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

 归并排序和计数排序以及计数排序的优化（小博学习算法第五天）

 代码实现：

void merage(int *a,int low,int mid,int high){
  int i=low;
  int j=mid+1;
  //创建一个数组，用于存储排序后的数
  int temp[high-low+1]={0};int k=0;
  while(i<=mid&&j<=high){
    if(a[i]>a[j]){
      temp[k++]=a[j++];
    }
    else{
      temp[k++]=a[i++];
    }
  }
  //当前面数组没有进行完
  while(i<=mid){
    temp[k++]=a[i++];
  }
  //当后面数组没有进行完
  while(j<=high){
    temp[k++]=a[j++];
  }
  //将排序后的数组赋值给原数组
  for(int i=0;i<high-low+1;i++){
    a[low+i]=temp[i];
  }
}
void Merage_sort(int *a,int low,int high){
  int mid=(high+low)/2;
  //递归函数结束条件
  if(low<high){
    Merage_sort(a,low,mid);
    Merage_sort(a,mid+1,high);
    //左右合并
    merage(a,low,mid,high);
  }
}

完整代码展示：

//小博学习算法五天（归并排序，计数排序以及计数排序的优化）
#include<iostream>
#include<algorithm>
using namespace std;
void merage(int *a,int low,int mid,int high){
  int i=low;
  int j=mid+1;
  //创建一个数组，用于存储排序后的数
  int temp[high-low+1]={0};int k=0;
  while(i<=mid&&j<=high){
    if(a[i]>a[j]){
      temp[k++]=a[j++];
    }
    else{
      temp[k++]=a[i++];
    }
  }
  //当前面数组没有进行完
  while(i<=mid){
    temp[k++]=a[i++];
  }
  //当后面数组没有进行完
  while(j<=high){
    temp[k++]=a[j++];
  }
  //将排序后的数组赋值给原数组
  for(int i=0;i<high-low+1;i++){
    a[low+i]=temp[i];
  }
}
void Merage_sort(int *a,int low,int high){
  int mid=(high+low)/2;
  //递归函数结束条件
  if(low<high){
    Merage_sort(a,low,mid);
    Merage_sort(a,mid+1,high);
    //左右合并
    merage(a,low,mid,high);
  }
}
//计数排序
void count_Sort(int *a,int length){
  int max=a[0];
  //找出其中最大的数，为了设定统计数组的大小
  for(int i=1;i<length;i++){
    if(max<a[i]){
      max=a[i];
    }
  }
  //进行统计计数
  int counta[max+1]={0};
  int counta_length=sizeof(counta)/sizeof(int);
  for(int i=0;i<length;i++){
    counta[a[i]]++;
  }
  //进行输出
  int index=0;
  for(int i=0;i<counta_length;i++){
    for(int j=0;j<counta[i];j++){
      a[index++]=i;
    }
  }
}
//计数排序优化算法
void count_Sort1(int *a,int length){
  int max=a[0];//找到最大的做计数数组的长度
  int min=a[0];//找到最小的作为最小基准数
  for(int i=1;i<length;i++){
    if(min>a[i]){
      min=a[i];
    }
    if(max<a[i]){
      max=a[i];
    }
  }
  int d=max-min;
  int countarroy[d+1]={0};
  int countarroy_length=sizeof(countarroy)/sizeof(int);
  //在统计数组countarroy中存入每个数据（以个位值存入）
  for(int i=0;i<length;i++){
    countarroy[a[i]-min]++;
  }
  //统计数组做变形，后面的数组等于前面的元素之和。
  //作用：是让统计数组存储的元素值等于相应整数的最终排序位置的序号
  for(int i=1;i<countarroy_length;i++){
    countarroy[i]+=countarroy[i-1];
  }
  //倒序遍历原始数组，从统计数组中找到正确位置，输出结果数组
  int sortedarroy[length]={0};//结果数组
  for(int i=length-1;i>=0;i--){
    sortedarroy[countarroy[a[i]-min]-1]=a[i];
    countarroy[a[i]-min]--;
  }
  for(int i=0;i<length;i++){
    a[i]=sortedarroy[i];
  }
}
int main(int argc, char const *argv[]) {
  int a1[]={4,5,1,2,7,8,9,6};
  int a2[]={4,5,1,2,7,8,9,6};
  int a3[]={95,94,91,98,99,90,99,93,91,92};
  int length1=sizeof(a3)/sizeof(int);
  int length=sizeof(a1)/sizeof(int);
  int low=0;
  int high=length-1;
  Merage_sort(a1,low,high);
  for(int i=0;i<length;i++){
    cout<<a1[i]<<" ";
  }
  cout<<endl;
  cout<<"-------------------------------"<<endl;
  count_Sort(a2,length);
  for(int i=0;i<length;i++){
    cout<<a2[i]<<" ";
  }
  cout<<endl;
  cout<<"-------------------------------"<<endl;
  count_Sort1(a3,length1);
  for(int i=0;i<length1;i++){
    cout<<a3[i]<<" ";
  }
  cout<<endl;
  cout<<"--------------------------------"<<endl;
  return 0;
}

结果展示归并排序和计数排序以及计数排序的优化（小博学习算法第五天）：

 

相关推荐