#yyds干货盘点#算法给小码农归并排序列阵 _盘点

弱龄寄事外，委怀在琴书。这篇文章主要讲述#yyds干货盘点#算法给小码农归并排序列阵相关的知识，希望能为你提供帮助。
 排序 常见的排序算法

文章图片

 常见排序算法的实现 归并排序
 基本思想 【#yyds干货盘点#算法给小码农归并排序列阵】

文章图片

文章图片

 递归写法 通过调试看一下现象

文章图片

 归并顺序

文章图片

文章图片

 归并排序递归子函数

// 归并排序递归子函数 void _MergeSort(int* a, int left, int right, int* tmp) //左大于右说明是空数组，空数组就跳 //左等于右就是我们要的单体有序 if (left > = right) return; //防溢出写法 int mid = left + (right - left) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid+1,right, tmp); // int begin1 = left; int end1 = mid; int begin2 = mid + 1; int end2 = right; int i = left; //跑空一组就直接跳 while (begin1< =end1 & & begin2< =end2) if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; while (begin1 < = end1) tmp[i++] = a[begin1++]; while (begin2 < = end2) tmp[i++] = a[begin2++]; //把tmp数组拷贝回到原来的数组中 i = left; while (i< =right)a[i] = tmp[i]; i++;

归并排序递归实现

// 归并排序递归实现 void MergeSort(int* a, int n) assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); //子函数 _MergeSort(a, 0, n - 1, tmp); //不用了就free掉 free(tmp); //然后置空 tmp = NULL;

非递归写法 2^n^个元素的数组

文章图片

文章图片

 随便几个元素的数组 修正下标

文章图片

文章图片

 归并排序非递归实现修正下标

// 归并排序非递归实现 void MergeSortNonR(int* a, int n) assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); int gap = 1; int i = 0; while (gap< n) for (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; //适用任何元素个数的核心部分 //end1出界，[begin2,end2]不存在 if (end1 > = n) end1 = n - 1; //[begin2,end2]不存在 if (begin2 > = n) begin2 = n ; end2 = n - 1; //end2出界 if (end2 > = n) end2 = n - 1; //printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2); ////重复拷贝基本是我们修正到同一个位置的原因 ////我们条件断点一下 //if (begin1 == end1 & & end1 == begin2 & & begin2 == end2 & & end2 == n-1) // ////随便一个代码来承接断点，一句费代码 //int a = 0; ////tmp需要一个索引 int index = i; while (begin1 < = end1 & & begin2 < = end2) if (a[begin1] > a[begin2]) tmp[index++] = a[begin2++]; else tmp[index++] = a[begin1++]; //肯定还有一个没跑完 while (begin1 < = end1) tmp[index++] = a[begin1++]; while (begin2 < = end2) tmp[index++] = a[begin2++]; //printf("%d", index); //printf("\\n"); //一行归并完了再考回去 for (i = 0; i < n; i++) a[i] = tmp[i]; gap *= 2; //不用了就free掉 free(tmp); //然后置空 tmp = NULL;

归一部分拷一部分

文章图片

 归并排序非递归实现归一部分拷一部分

// 归并排序非递归实现 void MergeSortNonR(int* a, int n) assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); int gap = 1; int i = 0; while (gap< n) for (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; ////适用任何元素个数的核心部分 ////end1出界，[begin2,end2]不存在 //if (end1 > = n) //end1 = n - 1; // ////[begin2,end2]不存在 //if (begin2 > = n) //begin2 = n ; //end2 = n - 1; // ////end2出界 //if (end2 > = n) //end2 = n - 1; // //适用任何元素个数的核心部分 //end1出界，[begin2,end2]不存在都不需要归并 if (end1 > = n || begin2 > = n) //直接跳，因为是在原数组操作的不需要担心最后一个没考进去 break; //end2出界需要归并就修正 if (end2 > = n) end2 = n - 1; //printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2); ////重复拷贝基本是我们修正到同一个位置的原因 ////我们条件断点一下 //if (begin1 == end1 & & end1 == begin2 & & begin2 == end2 & & end2 == n-1) // ////随便一个代码来承接断点，一句费代码 //int a = 0; ////tmp需要一个索引 int index = i; while (begin1 < = end1 & & begin2 < = end2) if (a[begin1] > a[begin2]) tmp[index++] = a[begin2++]; else tmp[index++] = a[begin1++]; //肯定还有一个没跑完 while (begin1 < = end1) tmp[index++] = a[begin1++]; while (begin2 < = end2) tmp[index++] = a[begin2++]; //归一部分拷贝一部分 int j = 0; for (j = i; j < = end2; j++) a[j] = tmp[j]; //printf("%d", index); //printf("\\n"); ////一行归并完了再考回去 //for (i = 0; i < n; i++) //a[i] = tmp[i]; // gap *= 2; //不用了就free掉 free(tmp); //然后置空 tmp = NULL;

归并排序的特性总结 时间复杂度 测性能
 1000一千

文章图片

 10000一万==先抛弃选择和冒泡==

文章图片

 100000十万==再抛弃直接插入==

文章图片

 1000000一百万

文章图片

 10000000一千万

文章图片

 代码
 Sort.h

#pragma once #include < stdio.h> #include < stdlib.h> #include < assert.h> #include < time.h> #define HEAP1// 排序实现的接口 // 打印数组 extern void PrintArray(int* a, int n); // 插入排序 extern void InsertSort(int* a, int n); // 希尔排序 extern void ShellSort(int* a, int n); //数据交换 extern void Swap(int* pa, int* pb); // 选择排序 extern void SelectSort(int* a, int n); //向下调整 extern void AdjustDwon(int* a, int n, int parent); // 堆排序 extern void HeapSort(int* a, int n); // 冒泡排序 extern void BubbleSort(int* a, int n); // 快速排序递归实现 // 快速排序hoare版本 extern int PartSort1(int* a, int left, int right); // 快速排序挖坑法 extern int PartSort2(int* a, int left, int right); // 快速排序前后指针法 extern int PartSort3(int* a, int left, int right); extern void QuickSort(int* a, int left, int right); // 快速排序非递归实现 extern void QuickSortNonR(int* a, int left, int right); // 归并排序递归实现 extern void MergeSort(int* a, int n); // 归并排序非递归实现 extern void MergeSortNonR(int* a, int n); // 计数排序 extern void CountSort(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Sort.h" #include"Stack.h"// 打印数组 void PrintArray(int* a, int n) assert(a); int i = 0; for (i = 0; i < n; i++) printf("%d ", a[i]); printf("\\n"); // 插入排序 void InsertSort(int* a, int n) assert(a); int i = 0; for (i = 0; i < n - 1; i++) int end = i; int x = a[end+1]; while (end > = 0) //要插入的数比顺序中的数小就准备挪位置 if (a[end] > x) a[end + 1] = a[end]; end--; else //插入的数比顺序中的要大就跳出 break; //跳出来两种情况 //1.end == -1 的时候 //2.break 的时候 //把x给end前面一位 a[end + 1] = x; // 希尔排序 void ShellSort(int* a, int n) //分组 int gap = n; //多次预排序（gap> 1）+ 直接插入（gap == 1） while (gap> 1) //gap /= 2; //除以三我们知道不一定会过1，所以我们+1让他有一个必过1的条件 gap = gap / 3 + 1; //单组多躺 int i = 0; for (i = 0; i < n - gap; i++) int end = i; int x = a[end + gap]; while (end > = 0) if (a[end] > x) a[end + gap] = a[end]; //步长是gap end -= gap; else break; a[end + gap] = x; //数据交换 void Swap(int* pa, int* pb) int tmp = *pa; *pa = *pb; *pb = tmp; // 选择排序 void SelectSort(int* a, int n) int begin = 0; int end = n - 1; while (begin < end) //单趟 //最大数，最小数的下标 int mini = begin; //这边假设是刚开始的下标 int maxi = end; //这边假设是末尾的下标 int i = 0; for (i = begin; i < = end; i++) if (a[i] < a[mini]) mini = i; if (a[i] > a[maxi]) maxi = i; //最小的放前面 Swap(& a[begin], & a[mini]); if (begin == maxi) //如果最大数就是begin位置的，那么交换的时候最大数连带着下标一起动 maxi = mini; //最大的放后面 Swap(& a[end], & a[maxi]); begin++; end--; //向下调整函数 void AdjustDown(int* a, int n, int parent)assert(a); //创建一个孩子变量，有两个孩子就在这个上加1就行 int child = parent * 2 + 1; #if HEAP while (child < n)//选大孩子 if (child + 1 < n & & a[child] < a[child + 1])child++; //大的孩子还大于父亲就交换 if (a[child] > a[parent])Swap(& a[child], & a[parent]); parent = child; child = parent * 2 + 1; elsebreak; #elif !HEAP while (child < n)//选小孩子 if (child + 1 < n & & a[child] > a[child + 1])child++; //小的孩子还小于父亲就交换 if (a[child] < a[parent])Swap(& a[child], & a[parent]); parent = child; child = parent * 2 + 1; elsebreak; #endif // HEAP// 堆排序我们之前讲过升序建大堆 void HeapSort(int* a, int n) //建堆时间复杂度O(N) //建大堆 int i = 0; for (i = (n - 1 - 1) / 2; i > = 0; i--) AdjustDown(a, n, i); int end = n - 1; //堆排序时间复杂度O(N*logN) while (end> 0) //交换把最大的放到后面 Swap(& a[0], & a[end]); //在向下调整 AdjustDown(a,end,0); end--; // 冒泡排序 void BubbleSort(int* a, int n) //多躺 int j = 0; for (j = 0; j < n - 1; j++) //交换标记变量 int flag = 0; //单趟 int i = 0; for (i = 0; i < n - 1-j; i++) if (a[i] > a[i + 1]) //交换标记改变 flag = 1; Swap(& a[i], & a[i + 1]); //标记还是0就跳出 if (!flag) break; //三数取中 int GetMinIndex(int* a, int left, int right) //这样可以防止 int 溢出 int mid = left + (right - left) / 2; if (a[left] < a[mid]) if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) return left; else return right; else //a[left] > = a[mid]if (a[mid] > a[right]) return mid; else if (a[left] < a[right]) return left; else return right; // 快速排序hoare版本单趟排序 //最左边做key[left,right]我们这里给区间 int PartSort1(int* a, int left, int right) //三数取中 int mini = GetMinIndex(a, left, right); //把中间的数放到最左边，交换即可 Swap(& a[mini], & a[left]); //还是最左边为keyi int keyi = left; //左右相遇就停止 while (left < right)//最左边为key，那么最右边就先动 //找小于key的 while (left < right & & a[right] > = a[keyi]) right--; //然后再动右边的 //找大于key的 while (left < right & & a[left] < = a[keyi]) left++; Swap(& a[left], & a[right]); Swap(& a[keyi], & a[right]); //返回正确位置后的keyi return left; // 快速排序挖坑法 int PartSort2(int* a, int left, int right) assert(a); //三数取中 int mini = GetMinIndex(a, left, right); //把中间的数放到最左边，交换即可 Swap(& a[mini], & a[left]); //先把Key存下来 int Key = a[left]; //挖坑 int pit = left; while (left< right) //右边找小 while (left < right & & a[right] > = Key) right--; //找到后把数据扔到坑里面去 Swap(& a[right],& a[pit]); //自己就变成新的坑 pit = right; //左边找大 while (left < right & & a[left] < = Key) left++; //找到后把数据扔到坑里面去 Swap(& a[left], & a[pit]); //自己就变成新的坑 pit = left; //出来后把Key放到坑里面去 a[pit] = Key; return pit; // 快速排序前后指针法 int PartSort3(int* a, int left, int right) assert(a); //三数取中 int mini = GetMinIndex(a, left, right); //把中间的数放到最左边，交换即可 Swap(& a[mini], & a[left]); //把keyi记下来 int keyi = left; int prev = left; int cur = prev + 1; while (cur < = right) ////比Key小就跳出 //while (cur < = right & & a[cur] > = a[keyi]) //cur++; // //if (cur < = right) ////跳出来prev++ //prev++; ////交换 //Swap(& a[prev], & a[cur]); ////交换完后cur也++ //cur++; // if(a[cur] < a[keyi]) Swap(& a[prev++], & a[cur]); cur++; //跳出来说明交换a[prev]和Key Swap(& a[prev],& a[keyi]); return prev; // 快速排序小区间优化 void QuickSort(int* a, int left, int right) if (left > = right) return; if (right - left + 1 < 10)//10以内的数插入InsertSort(a + left, right - left + 1); elseint keyi = PartSort3(a, left, right); //[left,keyi-1] keyi [keyi+1,right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); // 快速排序非递归实现 void QuickSortNonR(int* a, int left, int right) //建栈 ST st; //初始化栈 StackInit(& st); //left进栈 StackPush(& st, left); //right进栈 StackPush(& st, right); //空栈跳出 while (!StackEmpty(& st))//先取尾 int end = StackTop(& st); //pop掉 StackPop(& st); //再取头 int start = StackTop(& st); //再pop掉 StackPop(& st); //然后单趟排序找到keyi int keyi = PartSort3(a,start,end); //[start,keyi-1] keyi [keyi+1,end] if (keyi + 1 < end)//表示分割开来的区间大于1//因为我们先取尾，所以问先入头 StackPush(& st, keyi + 1); //再入尾 StackPush(& st, end); if (keyi - 1 > start)//表示分割开来的区间大于1//因为我们先取尾，所以问先入头 StackPush(& st, start); //再入尾 StackPush(& st, keyi - 1); //与初始化联动的栈销毁 StackDestroy(& st); // 归并排序递归子函数 void _MergeSort(int* a, int left, int right, int* tmp) //左大于右说明是空数组，空数组就跳 //左等于右就是我们要的单体有序 if (left > = right) return; //防溢出写法 int mid = left + (right - left) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid+1,right, tmp); // int begin1 = left; int end1 = mid; int begin2 = mid + 1; int end2 = right; int i = left; //跑空一组就直接跳 while (begin1< =end1 & & begin2< =end2) if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; while (begin1 < = end1) tmp[i++] = a[begin1++]; while (begin2 < = end2) tmp[i++] = a[begin2++]; //把tmp数组拷贝回到原来的数组中 i = left; while (i< =right)a[i] = tmp[i]; i++; // 归并排序递归实现 void MergeSort(int* a, int n) assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); //子函数 _MergeSort(a, 0, n - 1, tmp); //不用了就free掉 free(tmp); //然后置空 tmp = NULL; // 归并排序非递归实现 void MergeSortNonR(int* a, int n) assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); int gap = 1; int i = 0; while (gap< n) for (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; ////适用任何元素个数的核心部分 ////end1出界，[begin2,end2]不存在 //if (end1 > = n) //end1 = n - 1; // ////[begin2,end2]不存在 //if (begin2 > = n) //begin2 = n ; //end2 = n - 1; // ////end2出界 //if (end2 > = n) //end2 = n - 1; // //适用任何元素个数的核心部分 //end1出界，[begin2,end2]不存在都不需要归并 if (end1 > = n || begin2 > = n) //直接跳，因为是在原数组操作的不需要担心最后一个没考进去 break; //end2出界需要归并就修正 if (end2 > = n) end2 = n - 1; //printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2); ////重复拷贝基本是我们修正到同一个位置的原因 ////我们条件断点一下 //if (begin1 == end1 & & end1 == begin2 & & begin2 == end2 & & end2 == n-1) // ////随便一个代码来承接断点，一句费代码 //int a = 0; ////tmp需要一个索引 int index = i; while (begin1 < = end1 & & begin2 < = end2) if (a[begin1] > a[begin2]) tmp[index++] = a[begin2++]; else tmp[index++] = a[begin1++]; //肯定还有一个没跑完 while (begin1 < = end1) tmp[index++] = a[begin1++]; while (begin2 < = end2) tmp[index++] = a[begin2++]; //归一部分拷贝一部分 int j = 0; for (j = i; j < = end2; j++) a[j] = tmp[j]; //printf("%d", index); //printf("\\n"); ////一行归并完了再考回去 //for (i = 0; i < n; i++) //a[i] = tmp[i]; // gap *= 2; //不用了就free掉 free(tmp); //然后置空 tmp = NULL;

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Sort.h"// 测试排序的性能对比 void TestOP()//设置随机起点 srand(time(NULL)); //将要创建的数组大小 const int N = 10000000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); int* a8 = (int*)malloc(sizeof(int) * N); int* a9 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i)//保证两个数组是一样的 a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; a8[i] = a1[i]; a9[i] = a1[i]; int begin1 = clock(); //开始时间 //InsertSort(a1, N); int end1 = clock(); //结束时间 int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); //SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); //BubbleSort(a5, N); int end5 = clock(); int begin6 = clock(); QuickSort(a6, 0, N - 1); int end6 = clock(); int begin7 = clock(); QuickSortNonR(a7, 0, N - 1); int end7 = clock(); int begin8 = clock(); MergeSort(a8, N); int end8 = clock(); int begin9 = clock(); MergeSort(a9, N); int end9 = clock(); printf("InsertSort:%d\\n", end1 - begin1); //结束时间减去开始时间 printf("ShellSort:%d\\n", end2 - begin2); printf("SelectSort:%d\\n", end3 - begin3); printf("HeapSort:%d\\n", end4 - begin4); printf("BubbleSort:%d\\n", end5 - begin5); printf("QuickSort:%d\\n", end6 - begin6); printf("QuickSortNonR:%d\\n", end7 - begin7); printf("MergeSort:%d\\n", end8 - begin8); printf("MergeSortNonR:%d\\n", end9 - begin9); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); free(a9); //测试插入排序 void TestInsertSort() int a[] =1,5,3,7,0,9 ; InsertSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试希尔排序 void TestShellSort() int a[] =9,1,2,5,7,4,8,6,3,5 ; ShellSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试选择排序 void TestSelectSort() int a[] =9,1,2,5,7,4,8,6,3,5 ; SelectSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试堆排序 void TestHeapSort() int a[] =9,1,2,5,7,4,8,6,3,5 ; HeapSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试冒泡排序 void TestBubbleSort() int a[] =9,1,2,5,7,4,8,6,3,5 ; BubbleSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试单趟排序 void TestPartSort1() int a[] =5,5,5,5,5,5,5,5,5,5 ; PartSort1(a,0 ,sizeof(a) / sizeof(a[0])-1); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试快速排序 void TestQuickSort() int a[] =9,1,2,5,7,4,8,6,3,5 ; QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试快速排序--非递归 void TestQuickSortNonR() int a[] =9,1,2,5,7,4,8,6,3,5 ; QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试归并排序--递归 void TestMergeSort() int a[] =10,6,7,1,3,9,4,2 ; MergeSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); //测试归并排序--非递归 void TestMergeSortNonR() int a[] =10,6,7,1,3,9,4,2,5 ; MergeSortNonR(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); int main() //TestInsertSort(); //TestShellSort(); //TestSelectSort(); //TestHeapSort(); //TestBubbleSort(); //TestPartSort1(); //TestQuickSort(); //TestQuickSortNonR(); //TestMergeSort(); //TestMergeSortNonR(); TestOP(); return 0;