-
动静图结合详解: 归并排序 ，计数排序
动静图结合详解: 归并排序 ，计数排序
每博一文案
我们常常会遇到各种各样的坎坷和困境，当我们被现实压得喘不过气时， 总希望能有人能帮我们一把，但现实是，当我们有难时，不仅没人帮， 就连那些昔日的好友，也都消失了，半年已过，慢慢的明白了一个道理： 困难要自己扛，眼泪要自己擦。因为靠山，山会倒，靠人，人会跑， 靠来靠去，你就发现了，最后唯一能靠的是你自己。 就像季羡林先生在，悲喜自度中说的那样，在人生的道路上，每个人都是孤独的旅客。 人间万千光景，苦乐喜忧，跌撞起伏，除了自度。他人爱莫能助，人生如逆旅，道阻且长。 有些困难只能自己杠，眼泪只有自己擦。 当我们想要求得到别人的帮助时，发现人人都有门前的雪，家家都有一本难念的经， 经历过生活的起起伏伏后，才明白没有谁是永远的避风港，只有自己才是避风躲雨的屋檐。 —————— 一禅心灵庙语- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
归并排序的基本思想
归并排序(merge sort) 是利用 归并 的思想实现的排序方法，该算法采用经典的 分治 (divide-and-conquer) 策略:
- 分(divide)：将问题分成一些小的问题，然后递归求解
- 治 (conquer): 将分的阶段得到的各个答案[修补] 在一起
即：分而治之
归并排序 就是利用 归并 的思想实现的排序方法。它的原理是假设初始序列含有 n 个记录，则可以看成是 n 个有序的子序列，每个序列的长度为 1， 然后两两归并，三三归并 … 直到所有数值都归并了，就有序了。
归并排序,升序
归并排序,升序的步骤
- 首先我们需要开辟一个大小和原数组一样的的临时数组，用于存放排序好的数值。
- 我们需要将(原数组)序列分组，分序列
- 一直分序到只有一个元素或是没有元素时，就说明该部分的序列已经有序了，分解就结束了
- 分解结束了，开始合并，这里是升序，通过比较分序列好的，数值，将比较小的赋值到临时数组中，所有排序好的数值都赋值到了临时数组中去。
- 最后将数值排序好的临时数组中的内容，拷贝,覆盖到原数组中去，然后释放临时数组的空间.
归并排序,动图如下
- 分：的过程只是为了分解
- 治：分组完成后，开始对每组进行排序，然后合并成一个有序的序列，直到最后将所有分组合并成一个有序序列。
可以看大这种结构很像一颗 完全二叉树 ，本文的归并排序我们采用 递归实现 (也可采用迭代循环的方式实现)。分的阶段 可以理解为就是递归拆分，得到子序列的过程。
归并排序静态的详细图示步骤
- 首先需要一个无需的数组
- 将序列分解，直到 只有一个数值或者，不存再的序列
每次以 除以 2 的倍数,分其序列- 1
- 再分半
- 再分半
- 一一归并
将分解到最后一个数值后，归并起来 6 < 10 6 先归并入临时数组, 1 < 7 1 先归并入临时数组 3 < 9 , 2 < 4- 1
- 2
- 再两两归并
6,10 和 1,7 归并为 第一组为 1,6,7,10 3,9 和 2,4 归并为 第二组为 2,3,4,9- 1
- 2
- 最后四四归并，临时数组有序了
- 归并排序的最后一次合并 升序
[begin1] = 1 < 2 = [begin2] ,升序，小的先入临时数组, 1 填入临时数组中，并且 begin1 ++ 右移- 1
[begin2] = 2 < 6 = [begin1], 2 填入临时数组中，并且 begin2++ 右移- 1
[begin2] = 3 < 6 = [begin1], 3 填入临时数组中,并且 begin2++ 右移- 1
[begin2] = 4 < 6 = [beign1], 4 填入临时数组中,并且 begin2++,右移- 1
[begin1] = 6 < 9 = [begin2], 6 填入临时数组中，并且 begin1++,右移- 1
[begin1] = 7 < 9 = [begin2], 7 填入临时数组中，并且 begin1++,右移- 1
[begin2] = 9 < 10 = [begin1], 9 填入临时数组中，并且 begin2++,右移- 1
右序列结束了，将左序列剩余的没有填入到
tmp临时数组中数值，全部填入进去左序列 只剩下一个 10 了,填入到临时数组 tmp 中去- 1
最后，将临时数组中排序好的数值，按照下标顺序，一次将全部数值拷贝到
原数组中去
如图所示：这是最后一次的合并(归并) 操作，是两个有序序列
- 从有序序列开始挨个比较，这里比较 1 和 2，1 < 2 ,那么 1 进入临时数组中，并且将自己的指针右移动一位
- 由于上一次 2 大于 1，指针并为移动，然后是 2 和 3 对比， 2 < 3 ,2 进入到临时数组中，并且将自己的指针右移动一位。
- …
- 如果某一组的数值已经全部进入临时数组，那么剩余的一组的剩余有序序列直接追加到临时数组中去。
- 将
temp临时数组的内容拷贝到原数组中去，完成排序 - 最后，将临时数组的空间，释放掉
具体归并排序,升序的代码如下:
// 打印数组 void printArray(int* arr, int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 归并排序,升序，分解,归并 void _mergeSortAsc(int* arr, int left, int right, int* tmp) // tmp 临时数组 { if (left >= right) // 递归结束条件,当序列中只有一个数值(left == right)或者不存在该序列(left > right)时,就返回, { return; } int mid = (left + right) >> 1; // 分组,分解 // 假设 [left, mid] [mid+1, right] 有序,那么我们就可以归并了 _mergeSortAsc(arr, left, mid, tmp); // 左区间 递归分解 _mergeSortAsc(arr, mid + 1, right, tmp); // 右区间 递归分解 int begin1 = left, end1 = mid; // 左区间的范围下标,保存 int begin2 = mid + 1, end2 = right; // 右区间的范围下标,保存 int index = left; // 数组的起始位置,保存 while (begin1 <= end1 && begin2 <= end2) { // 只要有一个序列排序完了,就跳出,将剩下的归并到一起 if (arr[begin1] < arr[begin2]) { // begin1 小,填入临时数组中 tmp[index++] = arr[begin1++]; } else // begin2 小,填入临时数组中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,将剩下没有填入到临时数组中的数值,归并到临时数组中 while (begin1 <= end1) { // 左区间序列没有归并完 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { // 右区间序列,没有归并完, tmp[index++] = arr[begin2++]; } // 将临时数组排序好的,拷贝覆盖到原数组中去 for (int i = left; i <= right; ++i) { arr[i] = tmp[i]; } } // 归并排序升序的主函数 void mergeSortAsc(int* arr, int n) { // 堆区上开辟空间,作为临时数组使用 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); // 提示错误 exit(-1); } _mergeSortAsc(arr, 0, n - 1, tmp); free(tmp); // 释放 tmp 的空间 tmp = NULL; // 置为 NULL, 防止空指针访问 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
上述代码解析:
if (left >= right)：递归结束条件,当 左右序列分解到只有一个数值时left == right返回，
left > right序列不存在，递归结束，返回int mid = (left + right) >> 1;除以 2 ，中间下标，分解[left, mid] [mid+1, right]：[left, mid] 左序列范围的，[mid+1,right] 右序列范围的while (begin1 <= end1 && begin2 <= end2)：表示当左右序列中存在一个序列归并入临时数组
完了，跳出循环，将剩余一个没有结束的，剩下的全部数值填入到数组中去
while (begin1 <= end1)左序列没有完，将其数值全部填入数组中去。- 后置 ++ ，
归并排序,降序
归并排序的降序，只需要将归并时，把比较大的先填入临时数组中就可以了。
将
if (arr[begin1] < arr[begin2])改为if (arr[begin1] > arr[begin2])大于号，大的填入临时数组中去。具体代码实现如下:
// 打印数组 void printArray(int* arr, int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 归并排序,降序 void _mergeSortDesc(int* arr, int left, int right, int* tmp) // tmp 临时数组 { if (left >= right) // 递归结束条件:只有一个数值或者序列不存在 { return; } int mid = (left + right) >> 1; // [left, mid] [mid+1, right] _mergeSortDesc(arr, left, mid, tmp); // 左区间范围,分解归并 _mergeSortDesc(arr, mid + 1, right, tmp); // 右区间范围,分解归并 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; // 保存数组起始位置 while (begin1 <= end1 && begin2 <= end2) // 其中一个结束了,跳出循环 { if (arr[begin1] > arr[begin2]) // begin2 大，填入临时数组中 { tmp[index++] = arr[begin1++]; } else // begin2 大，填入临时数组中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,临时将没有结束的数组的内容填入到临时数组中 while (begin1 <= end1) { // begin1 左边序列没有结束 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { // begin2 右边序列没有结束 tmp[index++] = arr[begin2++]; } // 将临时数组排序好的内容,拷贝覆盖到原数组中 for (int i = left; i <= right; i++) { arr[i] = tmp[i]; } } // 归并排序,降序,主函数 void mergeSortDesc(int* arr, int n) { // 内存堆区上开辟空间, 用作临时数组 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); // 提示错误 exit(-1); // 程序非正常结束 } _mergeSortDesc(arr, 0, n - 1, tmp); // 归并排序 free(tmp); // 释放tmp 空间 tmp = NULL; // 置为NULL,防止非法访问 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
非递归实现,归并排序,升序
递归深度太深，程序是没有错的，但是栈的空间不不够用。
递归的缺陷: 栈帧深度太深，栈空间不够用，可能会溢出
递归改非递归的方式有两种
- 直接改循环，如(斐波那契数列)
- 借助自己或库中的栈，模拟递归的过程，入栈出栈
这里我们使用 循环来代替 递归，归并排序的非递归算法并不需要借助栈来完成，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：如下示图：
上述情况是一种非常理想的情况，但是事实上，这种可能情况的可能性，比较少。
为了，保证，其排序的完整性。我们需要考虑其他的情况。具体如下：三种情况
第一种情况:
当最后一个小组进行合并时，倒数第一个小区间存在，但是该区间元素个数不够
gap分时，我们需要在合并序列时，将对倒数第一个区间存在但不够的问题的，进行边界上的调整控制，防止数组越界，访问了 。可以调整为数组的最后一个下标位置n-1; 如下图示:
第二种情况:
当最后一个小组进行合并时，倒数第一个右小区间 不存在，此时便不需要对该不存的右小区间进行合并了，因为不存在吗 ， 我们直接退出就可以了，因为前面的左区间上的数值已经排序好了。如下图示:
第三种情况:
进行最后一个小组进行合并时，倒数第二个小区间不存在，并且倒数第 一个 小区间的元素个数不够
gap分组，此时也不需要对该小区间进行合并，（与 第一种情况一样处理）。
我们只要把上述三种情况处理了，就可以写成完整的 非递归，归并排序
具体代码实现如下:
// 归并排序,非递归实现，合并 void _mergerSortNonrAsc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp) { int index = begin1; // 保存,用于,合并, int i = begin1; while (begin1 <= end1 && begin2 <= end2) // 存在一个序列,排序完,就结束，把剩下的那个没有结束的归并上 { if (arr[begin1] < arr[begin2]) // begin1 < begin2 将小于的填入临时表中 { tmp[index++] = arr[begin1++]; } else // begin2 小 填入临时表中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,将剩下的没有填入临时数组的,填入 while (begin1 <= end1) { // begin1 没有结束 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) // begin2 没有结束 { tmp[index++] = arr[begin2++]; } for (int j = i; j <= end2; j++) { arr[j] = tmp[j]; } } // 归并排序,非递归实现 void mergeSortNonrAsc(int* arr, int n) { // 堆区上开辟空间,用于临时数组,大小和原数组一样大 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); exit(-1); } int gap = 1; // 每组数据个数,从 1 开始分组 while (gap < n) // 每次分组时不可以大于 n(数组大小) { for (int i = 0; i < n; i += 2 * gap ) // 2*gap 每次分组扩大2倍 { // [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; // 数组最后一个下标位置 } _mergerSortNonrAsc(arr, begin1, end1, begin2, end2, tmp); // 合并两个有序数列 } gap *= 2; // 分组 2倍扩容 } free(tmp); tmp = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
上述代码解析及其注意事项
int gap = 1;以1个数值分组，while (gap < n)分组的大小不可以超过 数组的大小n[i, i+gap-1], [i+gap,i+2*gap-1]假定该序列有序
[i, i+gap-1] : 左区间的范围，[i+gap, i+2*gap-1] ：右区间的范围
if (begin2 >= n)第二种情况，归并或者分解时右区间不存在。直接退出，就可以了，
前面的区间我们已经排序好了，不用再动了
if (end2 >= n)第一种情况和第三种情况，归并或者分解的时候，右小区间少了，或者第二个区间少
了数值，进行一个修正，修正为
end2 = n - 1;数组的最后一个下标位置。gap *= 2分组扩展一下，继续分解以及归并while (begin1 <= end1 && begin2 <= end2)当左右序列中存在一个序列所有数值归并到了
临时数组中，跳出循环，将剩余一个序列的数值没有全部归并到临时数组，的数值归并进入临时数组中
-
if (arr[begin1] < arr[begin2])升序，将较小的数值，率先归并到临时数组中去 -
for (int j = i; j <= end2; j++)所有数值归并完了，以后，将临时数组归并排序好的数值，
全部拷贝，赋值到原数组中去。
非递归实现,归并排序,降序
同样归并排序，非递归实现的降序，将较大的数值，率先归并到临时数组中就可以了。
如将
if (arr[begin1] < arr[begin2])改为if (arr[begin1] > arr[begin2])就可以实现降序了。具体代码实现如下:
// 归并两个有序的数列,降序 void _mergerSortNonrDesc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp) { int index = begin1; int j = begin1; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] > arr[begin2]) // begin1 较大，率先填入临时数组中 { tmp[index++] = arr[begin1++]; } else // begin2 较小,率先填入临时数组中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,将剩余没有填入的临时数组的数值填入 while (begin1 <= end1) { // begin1 没有结束 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { // begin2 没有结束 tmp[index++] = arr[begin2++]; } //全部数值填入到了临时数组中了,将临时数组排序好的数值，拷贝,赋值到原数组中 for (; j <= end2; j++) { arr[j] = tmp[j]; } } // 归并排序,降序 void mergerSortNonrDesc(int* arr, int n) { // 堆区上开辟空间,用于临时数组 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); // 提示错误 exit(-1); // 程序非正常结束 } int gap = 1; // 分组标准开始以 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; // 修正数组的最后一个数值下标位置 } _mergerSortNonrDesc(arr, begin1, end1, begin2, end2, tmp); // 降序归并两个有序序列 } gap = gap * 2; // 分组扩大 2倍 } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
归并排序重要思想扩展
归并排序，也叫外排序
内排序: 数据量相对少一些，可以放到内存中进行排序。
外排序 ：数据量较大，内存中放不下，数据只能放到磁盘文件中，排序
对于数据量庞大的序列，排序的话，内排序 是无法实现了，因为内存空间不够存放，而 外排序 其中的归并排序可以胜任这种海量的数据的排序。
例如：
假设我们有
10G的数据文件放到了硬盘中，需要我们排序一下。可是，我们的内存只有1G可以使用。这里我们就可以使用归并排序的思想：
10G的文件，我们将其切分成10个1G的文件，并且让 10 个 1G 的文件有序。- 每次从
10G的文件中读取一个1G的文件到内存中进行排序（内排序），并将排序好的结果写入到一个临时文件中(就是上面归并排序的临时数组中去)，再继续下一个1G的文件的数据的排序，不断重复这个过程。最终会生成10个各自有序的小文件。每个文件1G的大小 - 将生成的
10个1G的文件进行归并处理，先是归并成 5个2G的文件 ——> 再将 5 个2G的文件，归并成 两个4G和 一个2G的文件 ——> 再将 其归并为一个8G和 一个2G的文件 ——> 最后 归并为了 一个有序的10G文件 。
注意: 这里将两个文件进行 一一归并(合并) ,并不是先将两个文件读入到内存中，然后进行归并的，这时不行的，内存只有
1G是不够的。这里的 一一归并(合并) 是利用文件输入输出函数，从两个文件中各自读取一个数据，然后进行比较，将比较小的数据写入到一个新的(临时文件) 中去，然后再读取，再比较，再写入，最终将两个文件中的数据全部写入到另外一个文件(临时文件) 中去，此时这个文件的内容就是有序的了。这就是归并排序的思想：将一个一个无序的数据，分解成一个一个有序的数据，再一一归并成一个大的有序数据 分而治之 。
计数排序的基本思想
计数排序 是一个非基于比较的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的数值决定的。该算法于 1945年 由
Harold H. Seware提出。它的优势在于对一定的范围内的整数排序时，它的时间赋值度为O(n+k)k 表示的是该整数的范围，该排序快于任何比较排序算法。当然，这也是存在一定缺陷的，需要牺牲空间换取时间的做法，而且当O(k) > O(nlogn)的时候，效率反而不如基本比较排序，因为基本比较排序的时间复杂度在理论上的下限是O(nlogn)
计数排序: 名副其实，就是根据 ”计数“ 的方式来进行排序的，而所谓的 计数: 就是统计每个元素数值出现的次数。
再根据统计到的数值次数，进行一个映射的排序 。存在着两种 映射 方式
- 绝对映射
开辟的空间大小是序列中对应的最大数值的大小。如下图:
存在较大的空间上的浪费，如，该序列
[100,101,102,103,101,105,107]，我们只有 5 个数值需要排序，但是我们却要开辟100个空间，其中100个空间没有用上，浪费了，如下图：
- 相对映射
开辟的空间大小是
数组中最大值 - 数组的最小值 +1大小的空间。[0~9] 的数组大小为 ; 9-0+1= 10; 进可能上节省了空间。 再通过数值 - 数组中的最小值映射到对应的数组下标位置。再通过数组下标 + 数组最小值还原回去，同样是序列 :[100,101,102,103,101,105,107]只需要开辟: 107 - 100 +1 = 7 ，7 个大小的空间。如下图：
计数排序"，名副其实，就是根据"计数"的方式来进行排序，所谓"计数"，就是统计每个元素重复出现的次数。
计数排序,升序
计数排序，升序的基本思想
- 这里我们使用 相对映射的方式 ,统计数值出现的个数
- 需要使用 相对映射的方式 的话，我们需要首先找到该数组中的 最大值和最小值 ，通过 计算出
数组的
最大值 - 最小值 +1的 的数值大小，根据该数值开辟临时数组空间（用于统计数组中所有数值出现的个数）因为是 相对映射 ，所以需要实际数值 - min(数组的最小值)映射到对应数组的下标位置上去。- 最后通过统计到的数值个数，进行排序，注意需要将 结果 +
min恢复原来的数值大小 - 释放临时开辟的空间，防止非法访问。
代码具体实现如下:
// 计数排序,升序 void countSortAsc(int* arr, int n) { int max = arr[0]; // 数组中的最大值 int min = arr[0]; // 数组中的最小值 for (int i = 0; i < n; i++) { // 找数组中的最小值 if (min > arr[i]) { min = arr[i]; } // 找数组中的最大值 if (max < arr[i]) { max = arr[i]; } } int range = max - min + 1; // 数组的范围大小 + 1 // 根据计算得到的 数组大小 range 堆区上开辟临时数组，用于统计数值出现的个数 int* count = (int*)malloc(sizeof(int) * range); // 判断空间开辟是否成功 if (NULL == count) { perror("malloc error"); // 错误提醒 exit(-1); // 程序非正常退出 } memset(count, 0, sizeof(int) * range); // 临时数组元素全部初始化为 0 // 统计原数组中全部数值出现的个数 for (int i = 0; i < n; i++) { count[arr[i] - min]++; // 相对映射 } for (int i = 0, j = 0; i < range; i++) { // 根据统计的数值次数，排序 while (count[i]--) { arr[j++] = i + min; // 相对映射,+min 将数值还原回去 } } free(count); // 释放空间 count = NULL; // 置为 NULL,防止非法访问 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
上述代码解析及其注意事项:
int max = arr[0];int min = arr[0];默认初始的数组中的最大值和最小值是数组中下标为 0 的
的数值，防止找到错误的最大最小值
int range = max - min + 1求数组的实际大小，需要 额外 +1 ,如 [0~9] 实际数组的大小是 9-0+1 = 10 ，因为数组是从 0 下标开始的memset(count, 0, sizeof(int) * range);初始化临时数组，将其全部元素初始化为 0count[arr[i] - min]++;相对映射统计，数组中所有数值出现的个数，实际数值 - min(最小值)，
注意: 实际赋值排序的时候，需要加回去
+min-
arr[j++] = i + min;根据统计到的数值个数，赋值排序，i+min恢复到原来的实际数值。再赋值到原数组中去。 -
free(count);count = NULL;释放开辟的空间，手动置为 NULL,防止非法访问。
计数排序,降序
计数排序的降序，只需要将最后一步中的，统计的数值个数，赋值排序到原来的数组中时，把统计到的数值个数，从后往前，把统计到的后面的数值，放到原数组的前面就可以了。调换一下赋值顺序，
for (int i = 0, j = 0; i < range; i++)改为for (int i = range-1, j = 0; i <= 0; i--)其他不变。具体代码实现如下:
// 计数排序,降序 void countSortDesc(int* arr, int n) { int max = arr[0]; // 默认数组中的最大值和最小值为数组下标 0 的是数值 int min = arr[0]; for (int i = 0; i < n; i++) { // 找最小值 if (min > arr[i]) { min = arr[i]; } // 找最大值 if (max < arr[i]) { max = arr[i]; } } int range = max - min + 1; // 数组的大小 [0~9] = 9-0+1=10; // 堆区上开辟空间，临时数组计数 int* count = (int*)malloc(sizeof(int) * range); // 判断堆区上开辟的空间是否成功 if (NULL == count) { perror("malloc error"); exit(-1); } memset(count, 0, sizeof(int) * range); // 将临时数组中所有的元素初始化为 0 for (int i = 0; i < n; i++) { count[arr[i] - min]++; // 相对映射,统计实际数值个数 } for (int i = range-1, j = 0; i>= 0; i--) // range -1 实际数组最后一个下标位置 { // j= 0 赋值到原数组的开头开始 while (count[i]--) { arr[j++] = i + min; // 恢复到原来的数值大小,赋值给原来的数组中去 } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
计数排序的特别说明
虽然计数排序看上去很强大，但是它存在两大局限性：
- 当数列最大值与最小值差距过大时，并不适用于计数排序
比如：给定 20 个随机整数，范围在 0 到 1亿之间，此时如果使用 计数排序 的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。
- 当数列元素不是整数时，并不适用于计数排序
如果数列中的元素都是小数，比如：3.1415926, 或者是 0.00000001 这样的，则无法创建对应的统计数组，这样显然无法进行计数排序。
正是，由于这两个局限性，才使得计数排序不像，快速排序，归并排序那样被人们广泛的使用。
非递归归并排序 与 递归归并排序 性能上的测试
将排序开始之前的时间点 - 排序结束之后的时间点 = 排序的效率了
具体代码实现如下:
// 归并非递归，递归性能测试 void testTop() { srand(time(0)); // 时间种子 const int N = 1000000; // 100w int* a = (int*)malloc(sizeof(int) * N); int* b = (int*)malloc(sizeof(int) * N); if (NULL == a || NULL == b) { perror("malloc error"); exit(-1); } for (int i = 0; i < N; i++) { a[i] = rand(); // 产生随机值 b[i] = a[i]; } int begin1 = clock(); // 非递归归并排序开始之前的时间点 mergeSortNonrAsc(a, N); // 归并排序非递归实现,升序 int end1 = clock(); // 非递归归并排序结束之后的时间点 int begin2 = clock(); // 递归归并排序开始之前的时间点 mergeSortAsc(b, N); // 归并排序递归实现,升序 int end2 = clock(); // 递归归并排序结束之后的时间点 /* * 排序的效率 = 排序结束之后的时间点 end - begin 排序开始之前的时间点 */ printf("非递归归并排序：%d\n", end1 - begin1); printf("递归归并排序：%d\n", end2 - begin2); free(a); a = NULL; free(b); b = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
归并排序，计数排序的完整代码:
下面是有关归并排序，计数排序完整代码的实现，大家可以直接复制，粘贴就可以运行使用了，大家可以运行看看
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #include #include // 打印数组 void printArray(int* arr, int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 归并排序,升序，分解,归并 void _mergeSortAsc(int* arr, int left, int right, int* tmp) // tmp 临时数组 { if (left >= right) // 递归结束条件,当序列中只有一个数值(left == right)或者不存在该序列(left > right)时,就返回, { return; } int mid = (left + right) >> 1; // 分组,分解 // 假设 [left, mid] [mid+1, right] 有序,那么我们就可以归并了 _mergeSortAsc(arr, left, mid, tmp); // 左区间 递归分解 _mergeSortAsc(arr, mid + 1, right, tmp); // 右区间 递归分解 int begin1 = left, end1 = mid; // 左区间的范围下标,保存 int begin2 = mid + 1, end2 = right; // 右区间的范围下标,保存 int index = left; // 数组的起始位置,保存 while (begin1 <= end1 && begin2 <= end2) { // 只要有一个序列排序完了,就跳出,将剩下的归并到一起 if (arr[begin1] < arr[begin2]) { // begin1 小,填入临时数组中 tmp[index++] = arr[begin1++]; } else // begin2 小,填入临时数组中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,将剩下没有填入到临时数组中的数值,归并到临时数组中 while (begin1 <= end1) { // 左区间序列没有归并完 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { // 右区间序列,没有归并完, tmp[index++] = arr[begin2++]; } // 将临时数组排序好的,拷贝覆盖到原数组中去 for (int i = left; i <= right; ++i) { arr[i] = tmp[i]; } } // 归并排序升序的主函数 void mergeSortAsc(int* arr, int n) { // 堆区上开辟空间,作为临时数组使用 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); // 提示错误 exit(-1); } _mergeSortAsc(arr, 0, n - 1, tmp); free(tmp); // 释放 tmp 的空间 tmp = NULL; // 置为 NULL, 防止空指针访问 } // 归并排序,降序 void _mergeSortDesc(int* arr, int left, int right, int* tmp) // tmp 临时数组 { if (left >= right) // 递归结束条件:只有一个数值或者序列不存在 { return; } int mid = (left + right) >> 1; // [left, mid] [mid+1, right] _mergeSortDesc(arr, left, mid, tmp); // 左区间范围,分解归并 _mergeSortDesc(arr, mid + 1, right, tmp); // 右区间范围,分解归并 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; // 保存数组起始位置 while (begin1 <= end1 && begin2 <= end2) // 其中一个结束了,跳出循环 { if (arr[begin1] > arr[begin2]) // begin2 大，填入临时数组中 { tmp[index++] = arr[begin1++]; } else // begin2 大，填入临时数组中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,临时将没有结束的数组的内容填入到临时数组中 while (begin1 <= end1) { // begin1 左边序列没有结束 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { // begin2 右边序列没有结束 tmp[index++] = arr[begin2++]; } // 将临时数组排序好的内容,拷贝覆盖到原数组中 for (int i = left; i <= right; i++) { arr[i] = tmp[i]; } } // 归并排序,降序,主函数 void mergeSortDesc(int* arr, int n) { // 内存堆区上开辟空间, 用作临时数组 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); // 提示错误 exit(-1); // 程序非正常结束 } _mergeSortDesc(arr, 0, n - 1, tmp); // 归并排序 free(tmp); // 释放tmp 空间 tmp = NULL; // 置为NULL,防止非法访问 } // 归并排序,非递归实现，合并 void _mergerSortNonrAsc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp) { int index = begin1; // 保存,用于,合并, int i = begin1; while (begin1 <= end1 && begin2 <= end2) // 存在一个序列,排序完,就结束，把剩下的那个没有结束的归并上 { if (arr[begin1] < arr[begin2]) // begin1 < begin2 将小于的填入临时表中 { tmp[index++] = arr[begin1++]; } else // begin2 小 填入临时表中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,将剩下的没有填入临时数组的,填入 while (begin1 <= end1) { // begin1 没有结束 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) // begin2 没有结束 { tmp[index++] = arr[begin2++]; } for (int j = i; j <= end2; j++) { arr[j] = tmp[j]; } } // 归并排序,非递归实现 void mergeSortNonrAsc(int* arr, int n) { // 堆区上开辟空间,用于临时数组,大小和原数组一样大 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); exit(-1); } int gap = 1; // 每组数据个数,从 1 开始分组 while (gap < n) // 每次分组时不可以大于 n(数组大小) { for (int i = 0; i < n; i += 2 * gap ) // 2*gap 每次分组扩大2倍 { // [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; // 数组最后一个下标位置 } _mergerSortNonrAsc(arr, begin1, end1, begin2, end2, tmp); // 合并两个有序数列 } gap *= 2; // 分组 2倍扩容 } free(tmp); tmp = NULL; } // 归并两个有序的数列,降序 void _mergerSortNonrDesc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp) { int index = begin1; int j = begin1; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] > arr[begin2]) // begin1 较大，率先填入临时数组中 { tmp[index++] = arr[begin1++]; } else // begin2 较小,率先填入临时数组中 { tmp[index++] = arr[begin2++]; } } // 跳出循环,将剩余没有填入的临时数组的数值填入 while (begin1 <= end1) { // begin1 没有结束 tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { // begin2 没有结束 tmp[index++] = arr[begin2++]; } //全部数值填入到了临时数组中了,将临时数组排序好的数值，拷贝,赋值到原数组中 for (; j <= end2; j++) { arr[j] = tmp[j]; } } // 归并排序,降序 void mergerSortNonrDesc(int* arr, int n) { // 堆区上开辟空间,用于临时数组 int* tmp = (int*)malloc(sizeof(int) * n); if (NULL == tmp) { perror("malloc error"); // 提示错误 exit(-1); // 程序非正常结束 } int gap = 1; // 分组标准开始以 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; // 修正数组的最后一个数值下标位置 } _mergerSortNonrDesc(arr, begin1, end1, begin2, end2, tmp); // 降序归并两个有序序列 } gap = gap * 2; // 分组扩大 2倍 } } // 计数排序,升序 void countSortAsc(int* arr, int n) { int max = arr[0]; // 数组中的最大值 int min = arr[0]; // 数组中的最小值 for (int i = 0; i < n; i++) { // 找数组中的最小值 if (min > arr[i]) { min = arr[i]; } // 找数组中的最大值 if (max < arr[i]) { max = arr[i]; } } int range = max - min + 1; // 数组的范围大小 + 1 // 根据计算得到的 数组大小 range 堆区上开辟临时数组，用于统计数值出现的个数 int* count = (int*)malloc(sizeof(int) * range); // 判断空间开辟是否成功 if (NULL == count) { perror("malloc error"); // 错误提醒 exit(-1); // 程序非正常退出 } memset(count, 0, sizeof(int) * range); // 临时数组元素全部初始化为 0 // 统计原数组中全部数值出现的个数 for (int i = 0; i < n; i++) { count[arr[i] - min]++; // 相对映射 } for (int i = 0, j = 0; i < range; i++) { // 根据统计的数值次数，排序 while (count[i]--) { arr[j++] = i + min; // 相对映射,+min 将数值还原回去 } } free(count); // 释放空间 count = NULL; // 置为 NULL,防止非法访问 } // 计数排序,降序 void countSortDesc(int* arr, int n) { int max = arr[0]; // 默认数组中的最大值和最小值为数组下标 0 的是数值 int min = arr[0]; for (int i = 0; i < n; i++) { // 找最小值 if (min > arr[i]) { min = arr[i]; } // 找最大值 if (max < arr[i]) { max = arr[i]; } } int range = max - min + 1; // 数组的大小 [0~9] = 9-0+1=10; // 堆区上开辟空间，临时数组计数 int* count = (int*)malloc(sizeof(int) * range); // 判断堆区上开辟的空间是否成功 if (NULL == count) { perror("malloc error"); exit(-1); } memset(count, 0, sizeof(int) * range); // 将临时数组中所有的元素初始化为 0 for (int i = 0; i < n; i++) { count[arr[i] - min]++; // 相对映射,统计实际数值个数 } for (int i = range-1, j = 0; i>= 0; i--) // range -1 实际数组最后一个下标位置 { // j= 0 赋值到原数组的开头开始 while (count[i]--) { arr[j++] = i + min; // 恢复到原来的数值大小,赋值给原来的数组中去 } } } void sortTest() { int arr[] = { 10,6,7,1,3,9,4,2 }; countSortDesc(arr, sizeof(arr) / sizeof(int)); // 计数排序,降序 // countSortAsc(arr, sizeof(arr) / sizeof(int)); // 计数排序,升序 //mergerSortNonrDesc(arr, sizeof(arr) / sizeof(int)); // 归并排序,非递归实现,降序 //mergeSortNonrAsc(arr, sizeof(arr) / sizeof(int)); // 归并排序,非递归实现,升序 //mergeSortDesc(arr, sizeof(arr) / sizeof(int)); // 归并排序,递归实现,降序 //mergeSortAsc(arr, sizeof(arr) / sizeof(int)); // 归并排序,递归实现,升序 printArray(arr, sizeof(arr) / sizeof(int)); /* * sizeof(arr)/sizeof(int) : 表示数组的大小 * sizeof(arr): 表示数组所占空间的大小,单位字节 * sizeof(int) : 表示数组元素所占空间的大小,单位字节 */ } // 归并非递归，递归性能测试 void testTop() { srand(time(0)); // 时间种子 const int N = 1000000; // 100w int* a = (int*)malloc(sizeof(int) * N); int* b = (int*)malloc(sizeof(int) * N); if (NULL == a || NULL == b) { perror("malloc error"); exit(-1); } for (int i = 0; i < N; i++) { a[i] = rand(); // 产生随机值 b[i] = a[i]; } int begin1 = clock(); // 非递归归并排序开始之前的时间点 mergeSortNonrAsc(a, N); // 归并排序非递归实现,升序 int end1 = clock(); // 非递归归并排序结束之后的时间点 int begin2 = clock(); // 递归归并排序开始之前的时间点 mergeSortAsc(b, N); // 归并排序递归实现,升序 int end2 = clock(); // 递归归并排序结束之后的时间点 /* * 排序的效率 = 排序结束之后的时间点 end - begin 排序开始之前的时间点 */ printf("非递归归并排序：%d\n", end1 - begin1); printf("递归归并排序：%d\n", end2 - begin2); free(a); a = NULL; free(b); b = NULL; } int main() { //sortTest(); testTop(); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
- 444
- 445
- 446
- 447
- 448
- 449
- 450
- 451
- 452
- 453
- 454
- 455
- 456
- 457
- 458
- 459
- 460
- 461
- 462
- 463
- 464
- 465
- 466
- 467
- 468
- 469
- 470
- 471
- 472
- 473
- 474
- 475
- 476
- 477
- 478
- 479
- 480
- 481
- 482
- 483
- 484
- 485
- 486
- 487
- 488
- 489
- 490
- 491
- 492
- 493
- 494
- 495
- 496
- 497
- 498
- 499
- 500
- 501
- 502
- 503
- 504
- 505
- 506
- 507
- 508
- 509
- 510
- 511
- 512
- 513
- 514
- 515
- 516
- 517
- 518
- 519
- 520
最后:
限于自身水平，其中存在的错误，希望大家可以给予指教，韩信点兵——多多益善，谢谢大家，后会有期，江湖再见 !!!
-
相关阅读:
springboot+mybatis实现一对一，一对多
为什么百度百科总是审核不通过？
Spring 事务(Transaction)的简介说明
uniapp路由跳转的六种方式
【大数据开发技术】实验03-Hadoop读取文件
react使用hook封装一个search+input+checkbox组件
02UEc++【打飞艇：无人机运动】
研报精选 | 麦肯锡《业务流程自动化成功的必要条件》精要解读
CN_@数据链路层的子层@局域网@以太网@Ethernet v2@802.3@802.1Q@802.11@MAC帧
中国石油大学(北京)-《 油气田开发方案设计》第一阶段在线作业
- 原文地址：https://blog.csdn.net/weixin_61635597/article/details/126694663
