潮州网站建设公司,深圳市点击未来科技网站建设,wordpress手机上导航俩字,iis7.5 没有默认网站个人主页#xff1a;Lei宝啊
愿所有美好如期而遇 目录
归并排序递归实现
归并排序非递归实现 归并排序递归实现
图示#xff1a; 代码#xff1a;
先分再归并#xff0c;像是后序一般。
//归并排序
void MergeSort(int* arr, int left, int right)
{int* temp (int…个人主页Lei宝啊
愿所有美好如期而遇 目录
归并排序递归实现
归并排序非递归实现 归并排序递归实现
图示 代码
先分再归并像是后序一般。
//归并排序
void MergeSort(int* arr, int left, int right)
{int* temp (int*)malloc(sizeof(int) * (right));if (temp NULL){perror(malloc fail);}_MergeSort(arr, temp, left, right - 1);free(temp);
}void _MergeSort(int* arr, int* temp, int left, int right)
{if (left right)return;int mid (left right) / 2;int begin1 left;int begin2 mid 1;int end1 mid;int end2 right;_MergeSort(arr, temp, left, mid);_MergeSort(arr, temp, mid 1, right);int index left;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){temp[index] arr[begin1];}else{temp[index] arr[begin2];}}while (begin1 end1){temp[index] arr[begin1];}while (begin2 end2){temp[index] arr[begin2];}memcpy(arr left, temp left, sizeof(int) * (right - left 1));
}
归并排序非递归实现
这里的非递归实现不可借助栈实现因为返回去的时候不能使之有序。
代码
//归并排序非递归
void MergeSortNonR(int* arr, int n)
{int* temp (int*)malloc(sizeof(int) * n);if (temp NULL){perror(malloc fail);}int gap 1;while (gap n){ for (int i 0; i n; i 2 * gap){//归并的区间int begin1 i; int end1 i gap - 1;int begin2 i gap;int end2 i gap * 2 - 1;if (begin2 n - 1){break;}if (end2 n - 1){end2 n - 1;}int index i;//每次归并从i位置开始while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){temp[index] arr[begin1];}else{temp[index] arr[begin2];}}while (begin1 end1){temp[index] arr[begin1];}while (begin2 end2){temp[index] arr[begin2];}memcpy(arr i, temp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(temp);
}
时间复杂度O(n*logn),空间复杂度O(N);
