• 【数据结构】归并排序和计数排序(排序的总结)

    江河入海，知识涌动，这是我参与江海计划的第8篇。

    目录

    一，归并排序的递归

    二，归并排序的非递归

    三，计数排序

    四，排序算法的综合分析

    一，归并排序的递归

    基本思想：

            归并采用的是分治思想，是分治法的一个经典的运用。该算法先将原数据进行拆分，此步骤与二叉树的拆分思想一样（因此，运用递归比较简单），然后将最终拆分后的每一小部分排序，最后将已有序的子序列进行合并，得到完全有序的序列，其中关键为要使每个分割后的子序列有序，再使子序列段间有序，即合并有序序列。以上中将两个有序表合并成一个有序表称为二路归并。思想图如下（以升序为例）：

            上图中，先以中间数据为界，将一堆数据进行不断分解，当分解完全后，再进行合并，而在合并时其实就是边排序边合并。由于在排序中要改动原数据，因此，我们可再创建一个数组进行改动，然后将改动后的数据赋值给原数据块即可，代码和导图如下：

    代码运行导图

            导图中，先取中间值，以此下标为界限分开左右区间，然后再不断递归分割，最后一次分割为leftbegin == leftend，rightbegin == rightend，此时就要进行排序组合，组合完子序列后即可往原序列就行赋值，此为一趟遍历，然后递归就不断进行返回，即不断就行合并排序，最终全部元素有序。

    归并代码：

    void MergeFunction(int* a, int* nums, int n, int begin, int end) {
        //当分割区间为1个数据时就要停止分割，即此时begin == end
        if (begin == end) {
            return;
        }
        int middle = (begin + end) / 2;//中间数据，控制界限
        //在左区间[begin, middle]和右区间[middle + 1, end]进行不断分割
        MergeFunction(a, nums, n, begin, middle);
        MergeFunction(a, nums, n, middle + 1, end);
        //分割后，下面是进行左右区间的排序
        int leftbegin = begin, leftend = middle;
        int rightbegin = middle + 1, rightend = end;
        int insert = begin;
        //以下是进行分割后的排序
        while (leftbegin <= leftend && rightbegin <= rightend) {
            if (a[leftbegin] < a[rightbegin]) {
                nums[insert++] = a[leftbegin++];
            }
            else {
                nums[insert++] = a[rightbegin++];
            }
        }
        while (leftbegin <= leftend) {
            nums[insert++] = a[leftbegin++];
        }
        while (rightbegin <= rightend) {
            nums[insert++] = a[rightbegin++];
        }
        //拷贝数组
        memcpy(a + begin, nums + begin, sizeof(int) * (end - begin + 1));
    }
    void MergeSort(int* a, int n) {
        int* nums = (int*)malloc(sizeof(int) * n);//此数组用于临时放入数据
        if (!nums) {
            perror("nums malloc");
            exit(-1);
        }
        MergeFunction(a, nums, n, 0, n - 1);
        free(nums);
    }

    样例代码，将以下中数组a进行排序(升序)：

    1. #include 
    2. #include 
    3. #include 
    4. void MergeFunction(int* a, int* nums, int n, int begin, int end) {
    5. 	//当分割为1个时就要停止分割，即此时begin == end
    6. 	if (begin == end) {
    7. 		return;
    8. 	}
    9. 	int middle = (begin + end) / 2;//中间数据，控制界限
    10. 	//在左区间[begin, middle]和右区间[middle + 1, end]进行不断分割
    11. 	MergeFunction(a, nums, n, begin, middle);
    12. 	MergeFunction(a, nums, n, middle + 1, end);
    13. 	//分割后，下面是进行左右区间的排序
    14. 	int leftbegin = begin, leftend = middle;
    15. 	int rightbegin = middle + 1, rightend = end;
    16. 	int insert = begin;
    17. 	//以下是进行分割后的排序
    18. 	while (leftbegin <= leftend && rightbegin <= rightend) {
    19. 		if (a[leftbegin] < a[rightbegin]) {
    20. 			nums[insert++] = a[leftbegin++];
    21. 		}
    22. 		else {
    23. 			nums[insert++] = a[rightbegin++];
    24. 		}
    25. 	}
    26. 	while (leftbegin <= leftend) {
    27. 		nums[insert++] = a[leftbegin++];
    28. 	}
    29. 	while (rightbegin <= rightend) {
    30. 		nums[insert++] = a[rightbegin++];
    31. 	}
    32. 	//拷贝数组
    33. 	memcpy(a + begin, nums + begin, sizeof(int) * (end - begin + 1));
    34. }
    35. void MergeSort(int* a, int n) {
    36. 	int* nums = (int*)malloc(sizeof(int) * n);//此数组用于临时放入数据
    37. 	if (!nums) {
    38. 		perror("nums malloc");
    39. 		exit(-1);
    40. 	}
    41. 	MergeFunction(a, nums, n, 0, n - 1);
    42. 	free(nums);
    43. }
    44. int main() {
    45. 	int a[] = { 10,6,7,1,3,9,4,2 };
    46. 	MergeSort(a, sizeof(a) / sizeof(int));
    47. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
    48. 		fprintf(stdout, "%d ", a[i]);
    49. 	}
    50. 	puts("");
    51. 	return 0;
    52. }

    运行图：

    二，归并排序的非递归

            我们平常将递归改成非递归首先可能想起要运用栈结构，但是，我们先理一下归并的思路，当我们不断分割时确实可以用栈结构来控制区间，但是当回并时可能就比较麻烦，因此，本人不建议用栈结构，不是不可以，是有更好的方法。

            归并递归时是将数据不断进行二分，即分治思想，当用非递归时，我们可设置一个间隔gap，以次模仿递归时的二分思想，每次循环结束后将此间隔乘二即可。非递归思路导图如下：

            由以上图不难发现，此种非递归合并的思路与递归合并的思路有些不太一样，此种非递归的思想是一旦有了一个间隔值后，就一次性的将全部数据按照此间隔值进行间隔归并。

            非递归归并的时候要注意一个点，当数据个数为奇数时，不难发现，左区间[leftbegin,leftend]无影响，但右区间[rightbegin,rightend]将会溢出，此时情况，如果rightbegin溢出的话那么可之间退出，因为据上图中所示，每一趟归并时就相当于将下一趟的左区间就排列有序了；如果rightend溢出的话，直接令rightend为最后一个元素的下标进行归并排序即可。当数据个数为偶数时不会出现溢出情况。

    代码如下：

    void MergeSortNonR(int* a, int n) {
        int* nums = (int*)malloc(sizeof(int) * n);
        //gap是每次隔离的间隔，也可理解为将要排序的元素个数
        int gap = 1;

        //控制gap间据的大小
        while (gap < n) {
            for (int i = 0; i < n; i += 2 * gap) {
                //以gap为间距分割，左区间[leftbegin,leftend]共有gap个元素
                int leftbegin = i, leftend = i + gap - 1;
                //以gap为间距分割，当原始数有偶数的元素时，右区间[rightbegin,rightend]有gap个元素
                int rightbegin = i + gap, rightend = i + gap + gap - 1;
                int insert = i;
                //防止越界的情况，其中rightbegin间接控制了leftend的界限，若leftend越界，rightbegin一定越界。
                if (rightbegin >= n) {
                    break;
                }
                if (rightend >= n) {
                    rightend = n - 1;
                }
                //开始进行排序,排列的数据区间为[leftbegin, rightend]
                while (leftbegin <= leftend && rightbegin <= rightend) {
                    if (a[leftbegin] < a[rightbegin]) {
                        nums[insert++] = a[leftbegin++];
                    }
                    else {
                        nums[insert++] = a[rightbegin++];
                    }
                }
                while (leftbegin <= leftend) {
                    nums[insert++] = a[leftbegin++];
                }
                while (rightbegin <= rightend) {
                    nums[insert++] = a[rightbegin++];
                }
                //将排列的区间[leftbegin, rightend]进行拷贝，因为leftbegin和rightbegin都已改变，所以不能用这两个数据
                memcpy(a + i, nums + i, sizeof(int) * (rightend - i + 1));
            }
            gap *= 2;
        }
        free(nums);
    }

    样例代码，将以下中数组a进行排序(升序)：

    1. #include 
    2. #include 
    3. #include 
    4. void MergeSortNonR(int* a, int n) {
    5. 	int* nums = (int*)malloc(sizeof(int) * n);
    6. 	//gap是每次隔离的间隔，也可理解为将要排序的元素个数
    7. 	int gap = 1;
    8. 	while (gap < n) {
    9. 		for (int i = 0; i < n; i += 2 * gap) {
    10. 			//leftbegin和leftend理解为在gap区间内的元素
    11. 			int leftbegin = i, leftend = i + gap - 1;
    12. 			//rightbegin和rightend可理解为在预排序gap区间的后面的元素
    13. 			int rightbegin = i + gap, rightend = i + gap + gap - 1;
    14. 			int insert = i;
    15. 			//以下是当元素为奇数时的情况
    16. 			if (rightbegin >= n) {
    17. 				break;
    18. 			}
    19. 			if (rightend >= n) {
    20. 				rightend = n - 1;
    21. 			}
    22. 			//开始进行排序,排列的数据区间为[leftbegin, rightend]
    23. 			while (leftbegin <= leftend && rightbegin <= rightend) {
    24. 				if (a[leftbegin] < a[rightbegin]) {
    25. 					nums[insert++] = a[leftbegin++];
    26. 				}
    27. 				else {
    28. 					nums[insert++] = a[rightbegin++];
    29. 				}
    30. 			}
    31. 			while (leftbegin <= leftend) {
    32. 				nums[insert++] = a[leftbegin++];
    33. 			}
    34. 			while (rightbegin <= rightend) {
    35. 				nums[insert++] = a[rightbegin++];
    36. 			}
    37. 			//将排列的区间[leftbegin, rightend]进行拷贝，因为leftbegin和rightbegin都以改变，所以不能用这两个数据
    38. 			memcpy(a + i, nums + i, sizeof(int) * (rightend - i + 1));
    39. 		}
    40. 		gap *= 2;
    41. 	}
    42. 	free(nums);
    43. }
    44. int main() {
    45. 	int a[] = { 10,6,7,1,3,9,4,2 };
    46. 	MergeSortNonR(a, sizeof(a) / sizeof(int));
    47. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
    48. 		fprintf(stdout, "%d ", a[i]);
    49. 	}
    50. 	puts("");
    51. 	return 0;
    52. }

    运行图：

    分析：

            此种转换是从递归遍历的结尾入手，递归程序也就是当往下递归到最后时才开始进行后面的程序，然后再往上走。不难发现，此算法运用递归时，递归到1对1数据开始合并就结束往下递归的遍历。本非递归算法也就是直接从1对1数据开始合并起，模拟递归不断往上走。

    举一反三：

            此种非递归的转换是先摸清所有递归程序结束时的逻辑，然后再控制所有上层的情况不断运行。当我们运用此方法时必须要确保所有递归程序上层的逻辑，注意不能断层或忽视其中的情况，然后从最下层走起，不断往上层运行。

    运算的效率：

            最后我们来谈论一下此算法的效率，不难发现，由于此算法中运用的是二分思想，所以时间复杂度为O(nlogn)，空间复杂度O(n)。由此可见，此算法的效率也算高，跟快排不同的是，此算法与原始数据的初始位置并无太大影响，效率比较稳定。

    三，计数排序

            计数排序可从字面意思理解，通过数组的下标来计数来间接实现数据的排序。首先，我们需设置一个数组，此数组是通过下标来进行计数的，原数据中最大数据个数为max - min + 1(max是原数据的最大元素，min是原数据最小的元素)，即幅度range在区间[0，max - min]中，因此，我们可设置数组大小为max - min + 1(不包括重复数组，重复的数据我们可用相同下标对应的数值记录出现的次数)，即最大下标为max - min（记录最大元素的位置），下标的设置思想为：原数据 - min。然后将设置数组初始化为0(也可选举其它值，但选举0是最为简单的)，0表示原数据中没有此元素，然后幅度range遍历，一旦存在此元素加1，表示出现元素的次数，最后将其设置数组中出现过元素的下标加上min赋给原数据即可得到有序序列，思维导图如下：

    代码如下(以升序为例)：

    void CountSort(int* a, int n) {
        //以下是寻找最大值max和最小值min，为了后面确定幅度range
        int min = a[0], max = a[n - 1], j = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > max) {
                max = a[i];
            }
            if (a[i] < min) {
                min = a[i];
            }
        }
        //最大元素个数为range，下标为“原数据 - min”
        int range = max - min + 1;
        int* count = (int*)malloc(sizeof(int) * range);
        memset(count, 0, sizeof(int) * range);//初始化0，表元素个数为0
        for (int i = 0; i < n; i++) {
            //用计数数组count的有序下标来进行有序计数,记录出现过元素的次数
            count[a[i] - min]++;//注意: 不能count[a[i] - min] = 1,因为可能有重复数据
        }
        //最后遍历，一旦存在此值将，下标 + min即为数据
        for (int i = 0; i < range; i++) {
            while (count[i]--) {
                a[j++] = i + min;
            }
        }
        free(count);
    }

    代码演示(以升序为例)：

    1. #include 
    2. #include 
    3. #include 
    4. void CountSort(int* a, int n) {
    5. 	//以下是寻找最大值max和最小值min，为了后面确定幅度range
    6. 	int min = a[0], max = a[n - 1], j = 0;
    7. 	for (int i = 0; i < n; i++) {
    8. 		if (a[i] > max) {
    9. 			max = a[i];
    10. 		}
    11. 		if (a[i] < min) {
    12. 			min = a[i];
    13. 		}
    14. 	}
    15. 	//最大元素个数为range，下标为“原数据 - min”
    16. 	int range = max - min + 1;
    17. 	int* count = (int*)malloc(sizeof(int) * range);
    18. 	memset(count, 0, sizeof(int) * range);//初始化0，表元素个数为0
    19. 	for (int i = 0; i < n; i++) {
    20. 		//用计数数组count的有序下标来进行有序计数,记录出现过元素的次数
    21. 		count[a[i] - min]++;//注意: 不能count[a[i] - min] = 1,因为可能有重复数据
    22. 	}
    23. 	//最后遍历，一旦存在此值将，下标 + min即为数据
    24. 	for (int i = 0; i < range; i++) {
    25. 		while (count[i]--) {
    26. 			a[j++] = i + min;
    27. 		}
    28. 	}
    29. 	free(count);
    30. }
    31. int main() {
    32. 	int a[] = { 10,6,7,1,3,9,4,2 };
    33. 	CountSort(a, sizeof(a) / sizeof(int));
    34. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
    35. 		fprintf(stdout, "%d ", a[i]);
    36. 	}
    37. 	puts("");
    38. 	return 0;
    39. }

    运行图：

    计数效率与注意要点：

            计数排序的时间复杂度为O(range + n) ，空间复杂度为O(range)，效率是非常高的，因为无论什么排序算法，最好的时间效率无非是O(n)，而计数排序的时间复杂度达到O(range + n)，已经非常接近O(n)。无论是希尔排序，堆排序，快速排序还是归并排序都达不到此效率，但此算法也不是最优选择，因为此算法完全可以说是那空间换时间，当range非常大时会消耗很大的空间，而且由于此算法是运用数组下标进行间接排序的，因此，此算法只能对整型排序，不能对其它数据类型进行排序，使得此算法有了很大的局限性。

    四，排序算法的综合分析

    1，算法的效率分析

            排序算法的效率不能只根据时间复杂度和空间复杂度，因为两者的计算都是取最好情况和最坏情况进行概率的综合分析，最终取平均，比如排序的原始序列不同，快排算法，直接插入算法和冒泡算法的效率相差比较大，直接插入和冒泡最好的情况都是有序的情况，此时时间复杂度都为O(n)，而快排最好的情况是基准值每次在中间，此时时间复杂度为O(nlogn)。但大多数情况下，我们根本预测不了原始序列和原始数据，所以在大多数情况下可直接根据时间复杂度和空间复杂度直接判断，若对数据比较敏感的话就要根据具体情况进行具体分析，从而选取最优算法。

    2，算法的稳定性

            稳定性：相同的数据排序后，相对位置是否发生变化，若两者之间的相对位置没有发生变化，则算法稳定，发生变化，算法不稳定。

            在初学情况下，稳定性确实不算太重要，但是在后面深入学习系统操作和程序等先后顺序就显得尤为重要，例如，一个程序要对学生进行考试排名，其中高成绩出现了两个99分的和两个98分，这时两个99分的学生谁先排入第一名和两个98分的学生谁排入第三名就显得尤为重要，这就要求排序算法的稳定性。最后总结一下各个算法的效率和稳定性：

            其中计数排序没必要加上，因为计数局限性太强了，在后面的学习中基本用不到，并且提醒一下，以上中的算法效率和稳定性千万不要死记，因为之前说过，这些算法的效率基本都不稳定，不同的情况可能出现不同的效率，而某些算法的设计不同可能稳定，也可能不稳定，因此，理解算法的思想和如何实现尤为重要。

  • 相关阅读:
    从 0 开始手写实现一个 RPC 框架！
    Java并发编程--多线程间的同步控制和通信
    kubernetes之etcd基本操作
    单指标时间序列异常检测——基于重构概率的变分自编码（VAE）代码实现（详细解释）
    面试题-java实现字符串反转（附：StringBuffer和StringBuilder的区别）
    Electron录制-webm转mp4时长拉长问题
    如何做接口测试呢？接口测试有哪些工具
    技术干货| 如何运用 MongoDB 部分索引优化性能问题？
    Qt之自定义model读写CSV文件
    Git & GitHub 入门篇
  • 原文地址：https://blog.csdn.net/m0_74246469/article/details/133682555