归并排序和非比较排序

归并排序还是比较难理解的，我们要掌握归并排序的递归和非递归的方式。

下面先了解一下归并排序到底是什么：

四个字----分而治之

 先从整体小的归并，然后到总的整体归并

 

 

 

完整代码：

void _MerGetSort(int* arr, int begin, int end, int* tmp)
{
    if (begin >= end)
    {
        return;
    }

    //划分区域
    int mid = (begin + end) / 2;
    //递归
    _MerGetSort(arr, begin, mid, tmp);
    _MerGetSort(arr, mid + 1, end, tmp);
    
    //归并比较
    int begin1 = begin;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = end;
    int i = begin1;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            tmp[i++] = arr[begin1++];
        }
        else
        {
            tmp[i++] = arr[begin2++];
        }
    }
    //肯定有一个已经走完了  将剩下的归并到tmp中
    while (begin1 <= end1)
    {
        tmp[i++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = arr[begin2++];
    }

    //归并完了，将tmp拷贝回arr数组
    memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MerGetSort(int* arr, int len)
{
    //开辟一个数组
    int* tmp = (int *)malloc(sizeof(int) * len);
    _MerGetSort(arr, 0, len - 1, tmp);
    free(tmp);
}
void PrintSort(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    int arr[] = { 3,1,2,4,9,5,6};
    int len = sizeof(arr) / sizeof(arr[0]);
    MerGetSort(arr, len);
    
    PrintSort(arr, len);
}
 

 

下面介绍非递归写法：

 

void MerGetSort(int* arr, int len)
{
	//开辟一个新的数组
	int* tmp = (int*)malloc(sizeof(int) * len);
	if (tmp == NULL)//判断一下
	{
		printf("malloc fail\n");
		exit(-1);
	}

	int gap = 1;//确定gap
	
	while (gap < len)
	{
		printf("%d->", gap);
		for (int i = 0; i < len; i += 2 * gap)
		{
			//[i, i + gap - 1] [gap + i, i + 2 * gap - 1] 划分区域
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = gap + i, end2 = i + 2 * gap - 1;
			printf("[%d][%d] [%d][%d]", begin1, end1, begin2, end2);
			//判断越界区域，然后修改
			//因为gap是多少begin1都会是最后一个，所以从end1开始修改
			if (end1 >= len)
			{
				end1 = len - 1;
				begin2 = len;  //此时[begin2,end2]----[len,len-1]不合理，就不会执行
				end2 = len - 1;
			}
			else if (begin2 >= len)//无效区域  修改
			{
				begin2 = len;
				end2 = len - 1;
			}
			else if (end2 >= len)
			{
				end2 = len - 1;
			}
			int i = begin1;
			//然后归并比较
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[i++] = arr[begin1++];
				}
				else
				{
					tmp[i++] = arr[begin2++];
				}
			}
			//走完之后，将剩下的数据放入tmp
			while (begin1 <= end1)
			{
				tmp[i++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[i++] = arr[begin2++];
			}
		}
		printf("\n");
		memcpy(arr, tmp, sizeof(int) * len);//拷贝
		gap = gap * 2;
	}
}
void PrintSort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,1,2,4,9,5,6};
	int len = sizeof(arr) / sizeof(arr[0]);
	MerGetSort(arr, len);
	
	PrintSort(arr, len);
}

至于无效区域是指：

如果你不想修改边界的话，也可以直接跳过，修改如下：
方法二：
 

 这么memcpy是一段一段拷贝的，不想方式一是全部一起拷贝，两种方式看个人喜好。

接下来要介绍的是非比较排序

我们接下来学的就是计数排序

了解一下计数排序

这种计数排序具有局限性：
1、如果是浮点数，字符串就不能玩了

2、如果数据范围很大，空间复杂度就会很高，也不能玩

3、一般这些数据都是相差的幅度比较小

当遇到100、1000以上这些数据，又相差不大的话，运用相对映射的话就非常实用了。

//计数排序
void CountSort(int* arr, int len)
{
    int min = arr[0], max = arr[0];//最小最大的都是第一位  往后面去找
    for (int i = 1; i < len; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
    //最大最小已经找好了 开辟空间
    int range = max - min + 1;
    int* count = (int *)malloc(sizeof(int) * range);
    if (count == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    memset(count, 0, sizeof(int) * range);//全部初始化成0

    //统计出现次数
    for (int i = 0; i < len; i++)
    {
        count[arr[i] - min]++;
    }

    //回写排序
    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (count[i]--)
        {
            arr[j++] = i + min;
        }
    }
}
void PrintSort(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    int arr[] = { 1003,1001,1002,1004,1009,1005,1006};
    int len = sizeof(arr) / sizeof(arr[0]);
    CountSort(arr, len);
    
    PrintSort(arr, len);
}

 

 

 

这里对前面几种排序作归类，和有缺点评估

 希望小伙伴们都能学会这些排序，你们的支持才是我前进的动力呀！

如有错误，多多指教！