排序算法8----归并排序（非递归）（C）

       1、介绍

        归并排序既可以是内排序（在内存上的数据排序），也可以是外排序（磁盘上）（硬盘）（在文件中的数据排序）。

        其他排序一般都是内排序。

        区别于快速排序的非递归，归并排序非递归不适合使用栈。

        因为快速排序的本质是一种前序递归，而归并排序的本质是一种后序递归，并没有“根”来区分左右。

        那么归并排序的非递归应该怎么样实现呢？

        2、思想

        我们先想想归并的思想和目的：递归的分治是将数组分割成两边有序的子序列，然后再合并这两个。那么我们是否可以直接将数组中两两元素归并呢？答案是：对的！因为我们将数组中所有元素看作两两一组（每组数据中都各有一个元素），那么这一组中的两个元素单个来看就是有序的子序列，然后合并这两个元素。再往上就是四四一组（每组数据中都各有两个有序的元素），八八一组........

        听起来好像很简单，其实坑很多，下面慢慢实现。

        3、代码

void MergeSortNonR_incline(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");exit(-1);}int gap = 1;//1-1归//gap代表归并每组数组个数，即gap个和gap个归并while (gap < n){for (int i = 0; i < n; i += 2 * gap)//[0,n){int begin1 = i, end1 = i + gap - 1;//第一组int begin2 = i + gap, end2 = i + 2 * gap - 1;//第二组//[begin1,end1],[begin2,end2] 归并//[0,0]-[1,1]归，[2,2]-[3,3],[4,4]-[5,5]....//[0,1]-[2,3]归, [4,5]-[6,7]....//[0,3]-[4,7]归, [8,11]-[11,15]......// ......//注意：begin1不会越界，end1，begin2，end2都可能越界，所以要修正if (end1 >= n || begin2>=n)break;if (end2 >= n)end2 = n - 1;//合并，将arr中对应位置，放入tmp的对应位置int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[j++] = arr[begin1++];elsetmp[j++] = arr[begin2++];}while (begin1 <= end1){tmp[j++] = arr[begin1++];}while (begin2 <= end2){tmp[j++] = arr[begin2++];}//[begin1,end1],[begin2,end2]memcpy(arr + i, tmp + i, sizeof(int) * (end2-i+1));//每次归并完拷贝回去}gap *= 2;}free(tmp);tmp = NULL;
}

        4、实现效果

	int arr[] = { 1,6,41,32,5,12,7,11 };int size = sizeof(arr) / sizeof(int);printf("原数组\n");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}printf("\n");printf("排序后\n");MergeSortNonR_incline(arr, size);for (int i = 0; i < size; i++){printf("%d ", arr[i]);}printf("\n");

原数组：1 6 41 32 5 12 7 11

排序后：1 5 6 7 11 12 32 41