【通俗易懂-动态图解析】归并排序、计数排序

编程TWO 编程小兔崽 今天

归并排序

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；

对这两个子序列分别采用归并排序；

将两个排序好的子序列合并成一个最终的排序序列。

代码：

代码：

#include<stdio.h>
#include<malloc.h>
void mergerSort(int *a1, int *a2, int **a3, 
int count1, int count2, int *count3);
void showArray(int *a3, int count);
void showArray(int *a3, int count)
{
    int i;

    for(i = 0; i < count; i++)
    {
        printf("%d ", a3[i]);
    }

    printf("\n");
 }
 void mergerSort(int *a1, int *a2, 
    int **a3, int count1, int count2, int *count3)
{
    int count;
    int i = 0;
    int j = 0;
    int n = 0;

    count = *count3 = count1 + count2;
    *a3 = (int *)malloc(sizeof(int) * count);
    //以下的都是<，因为传过来的是数组长度；
    while(i < count1 && j < count2)
    {
        if(a1[i] < a2[j])
        {
            (*a3)[n++] = a1[i];
            i++;
        }
        else if(a1[i] == a2[j])
        {
            (*a3)[n++] = a1[i];
            (*a3)[n++] = a2[j];
            i++;
            j++;
        }
        else
        {       //刚才写程序else(a1[i] > a2[j]),后发现else语句后面是没有条件的!!!
            (*a3)[n++] = a2[j];
            j++;
        }
    }

    while(i < count1)
    {
        (*a3)[n++] = a1[i];
        i++;
    }
    while(j < count2)
    {
        (*a3)[n++] = a2[j];
        j++;
    }
   }
/* 
归并排序核心算法就是：将已经排好序的2个数组进行最终的排序过程；
*/void main(void)
{
    int a1[] = {1, 3, 5, 7};
    int a2[] = {0, 2, 4, 6, 8, 9, 10};
    int count1 = sizeof(a1)/sizeof(int);
    int count2 = sizeof(a2)/sizeof(int);
    int *a3 = NULL;
    int count3 = 0;

    mergerSort(a1, a2, &a3, count1, count2, &count3);
    showArray(a3, count3);
    free(a3);
   }

算法分析

最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)

计数排序：

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

算法描述

找出待排序的数组中最大和最小的元素；

统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

代码：

#include<stdio.h>
void countSort(int *a, int count);
void showArray(int *a, int count);
void showArray(int *a, int count)
{
    int i;

    for(i = 0; i < count; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
 }
 void countSort(int *a, int count)
 {
    int b[10] = {0};
    int *c;
    int i;

    c = (int *)malloc(sizeof(int) * count);
    for(i = 0; i < count; i++)
    {
        b[a[i]]++;
    }
    for(i = 1; i < 10; i++)
    {
        b[i] += b[i-1];
    }

    for(i = count-1; i >= 0; i--)
    {
        c[b[a[i]]-1] = a[i];
        b[a[i]]--;
    }

    for(i = 0; i < count; i++)
    {
        a[i] = c[i];
    }

    free(c);
  }
  void main(void)
  {
    int a[] = {2, 4, 7, 2, 1, 0, 9};
    int count = sizeof(a)/sizeof(int);

    countSort(a, count);
    showArray(a, count);
   }

算法分析

当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

最佳情况：T(n) = O(n+k)  最差情况：T(n) = O(n+k)  平均情况：T(n) = O(n+k)

推荐阅读：

【通俗易懂-动态图解析】冒泡排序、选择排序

【通俗易懂-动态图解析】插入排序、快速排序

▼长按2秒识别二维码关注公众号

欢迎把我推荐给你的朋哟

每天进步一点点，如果有用给点个赞