排序——归并排序和计数排序

简介: 介绍归并排序和计数排序

归并排序

基本思想

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤

递归代码实现
void _MergeSort(int* a, int left, int right,int*tmp)
{
  if (left >= right)
    return;
  int mid = left + ((right - left) >>1);
  //进行分治
  _MergeSort(a, left, mid, tmp);
  _MergeSort(a, mid + 1, right, tmp);
  //进行归并
  int begin1 = left, end1 = mid;
  int begin2 = mid + 1, end2 = right;
  //归并的可不一定是0
  int index = left;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[index++] = a[begin1++];
    }
    else
    {
      tmp[index++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[index++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[index++] = a[begin2++];
  }
  //将数据拷贝回原数组
  for (int i = left; i <= right; i++)
  {
    a[i] = tmp[i];
  }
}
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}
void TestMergeSort()
{
  int a[] = { 105,5,8,2,50,7,-1,100,66 };
  int n = sizeof(a) / sizeof(a[0]);
  MergeSort(a,n);
  Print(a, n);
}
int main()
{
  TestMergeSort();
}

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定
非递归代码实现
void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (NULL == tmp)
  {
    perror("malloc fail");
    exit(-1);
  }
  else
  {
    //每组数组的个数
    int gap = 1;
    while (gap < n)
    {
      for (int i = 0; i < n; i += 2 * gap)
      {
        //[i,i+gap-1]  [i+gap,i+2*gap-1]
        int begin1 = i, end1 = i + gap - 1;
        int begin2 = i + gap, end2 = i + 2 * gap - 1;
        //进行边界修正
        if (begin2 >= n)
          break;
        if (end2 >= n)
        {
          end2 = n - 1;
        }
        int index = i;
        while (begin1 <= end1 && begin2 <= end2)
        {
          if (a[begin1] < a[begin2])
          {
            tmp[index++] = a[begin1++];
          }
          else
          {
            tmp[index++] = a[begin2++];
          }
        }
        while (begin1 <= end1)
        {
          tmp[index++] = a[begin1++];
        }
        while (begin2 <= end2)
        {
          tmp[index++] = a[begin2++];
        }
        //将数据拷贝回原数组
        for (int j = i; j <=end2; j++)
        {
          a[j] = tmp[j];
        }
      }
      gap *= 2;
    }
  }
}
void TestMergeSortNonR()
{
  int a[] = { 105,5,8,2,50,7,-1,100,66 };
  int n = sizeof(a) / sizeof(a[0]);
  MergeSortNonR(a, n);
  Print(a, n);
}
int main()
{
  TestMergeSortNonR();
}

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

非比较排序

思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用

操作步骤:

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

代码实现:

void CountSort(int* a, int n)
{
  int max = a[0], min = a[0];
  for (int i = 0; i < n; ++i)
  {
    if (a[i] > max)
    {
      max = a[i];
    }
    if (a[i] < min)
    {
      min = a[i];
    }
  }
  int range = max - min + 1;
  int* count = (int*)malloc(sizeof(int) * range);
  if (count == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  else
  {
    memset(count, 0, sizeof(int) * range);
    for (int i = 0; i < n; i++)
    {
      count[a[i]-min]++;
    }
    int j = 0;
    for (int i = 0; i < range; i++)
    {
      while (count[i]--)
      {
        a[j++] = i + min;
      }
    }
  }
  free(count);
}
void TestCountSort()
{
  int a[] = { 105,5,8,2,50,7,-1,100,66 };
  int n = sizeof(a) / sizeof(a[0]);
  CountSort(a, n);
  Print(a, n);
}
int main()
{
  TestCountSort();
}

计数排序的特性总结:

  1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
  2. 时间复杂度:O(MAX(N,范围))
  3. 空间复杂度:O(范围)

相关文章
|
存储 算法 搜索推荐
排序篇(四)----归并排序
排序篇(四)----归并排序
62 0
|
算法 搜索推荐 大数据
【算法】排序——归并排序和计数排序
上两篇文章讲解了插入排序、选择排序以及交换排序,每种类型的排序大类下都有一到两种排序,今天给大家带来的是归并排序,和前面几种排序一样都属于比较排序中的一种,是通过比较数组中的元素来实现排序的,还给大家带来一种非比较排序计数排序,让我们开始今天的排序之吧!!!
|
7月前
|
存储 搜索推荐 算法
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
|
7月前
|
存储 搜索推荐 Java
排序之计数排序
排序之计数排序
|
7月前
|
C语言
排序:计数排序
排序:计数排序
39 0
|
7月前
|
算法 搜索推荐
排序——归并排序
排序——归并排序
51 0
|
7月前
|
搜索推荐 算法
排序——计数排序
排序——计数排序
39 0
|
7月前
|
搜索推荐 算法 Shell
排序——插入排序
排序——插入排序
50 0
|
存储 搜索推荐 测试技术
排序篇(一)----插入排序
排序篇(一)----插入排序
51 0
|
存储 算法 搜索推荐
排序(4)——归并排序
今天给大家带来比较排序的最后一种,归并排序,这个排序,需要我们对递归,循环控制要有着较强的理解,我相信大家通过前面和小编的一起学习,这里肯定也是得心应手。
101 0