2.非递归实现
1.基本思路
快排的递归实现，由于存在栈溢出的可能性；往往需要用模拟栈来实现非递归；
给定一个N个数据的数组，其下标范围为[ 0,N-1 ],将这段区间入栈，然后出栈去找key，划分左右区间，因为栈的特点是后进先出，将这两个区间看做两个的整体，那么这两个区间入栈的顺序就是先入右子区间，再入左子区间；（详解如下）
其实整体的思路和递归很类似，但本质上是循环迭代的过程； 也是通过找key划分区间，每次划分出来的区间都去找key，每个区间key的左边都比key小，右边都比key大，直到不可划分为止，那么整个数组就排序完成了；
2.代码实现
//快排（非递归） void QuickSortNonR(int* a, int left, int right) { ST st; StackInit(&st); //先入0-9区间 StackPush(&st, left); StackPush(&st, right); while (!StackEmpty(&st)) { //取出0-9区间 int end = StackTop(&st); StackPop(&st); int begin = StackTop(&st); StackPop(&st); //找中间基准值、划分左右区间 int keyi = Partion3(a, begin, end); //[begin,keyi-1] keyi [keyi+1,end] //先入右区间 if (keyi + 1 < end) { StackPush(&st, keyi + 1); StackPush(&st, end); } //再入左区间 if (begin < keyi - 1) { StackPush(&st, begin); StackPush(&st, keyi - 1); } } StackDestroy(&st); }
三、归并排序
1.递归实现
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
代码实现
//归并排序(递归) //时间复杂度：O(N*logN) //空间复杂度：O(N) void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) { return; } int mid = (left + right) / 2; //如果[left,mid] [mid+1,right]有序 _MergeSort(a, left, mid, tmp);//归并左区间 _MergeSort(a, mid+1, right, tmp);//归并右区间 int begin1 = left, end1 = mid; int begin2 = mid + 1, 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数组的值拷贝回a数组中 for (int j = left; j <= right; ++j) { a[j] = tmp[j]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
2.非递归实现
1.方法1：分组归并、整体拷贝——边界控制的阐述
1.基本思路：
2.边界控制
上图进行gap分组依次归并，可以看出：两个数据归并——>四个数据归并——>八个数据归并——>归并结束，排序完成；也就说明这种非递归的思想只适用于数组元素个数是2^n；
针对数组元素个数非2^n时，要对其边界进行控制，这也是归并排序的一个难点；整体的框架可能大家都理解，利用临时的tmp数组，然后把待排序数组拆分成两个数组，依次取遍历两个数组，哪个小就先入tmp数组，可能存在没入完的数组，再将剩下的全部入tmp数组；
假设现有一个9个元素的数组，如何对其进行边界控制？
以gap=gap*2（gap>=1）的增长方式进行每组的归并操作，首先将数组分成两个区间，分别表示为[ begin1，end1 ]和[ begin2，end2 ];
如图所示：
这两个区间，在gap的以2倍的变化中且与元素个数存在一定的关系，我们需要利用这两个区间加上tmp数组的利用，进行归并操作；那么就必须保证这两个区间是有效的（区间一定要有数据）；因为在遍历数组的过程中，两个区间时时发生变化，就存在以下三种情况：
具体情况具体分析：
情况1：
此时[ begin2, end2 ]=[ 9, 9 ]，此区间是不存在元素的；根据归并的思想：把数据入tmp数组，再拷贝回原数组；就入数据而言，是对这两个区间的元素大小进行判断，既然此时只有一个区间有元素，那么就可以把没有元素的区间进行修正，修正为不存在的区间；元素个数n=9，将end2修正为8（end=n-1），那么就不存在这样的区间，就会把[ begin1, end1 ]=[ 8, 8 ]的数据入到tmp数组中去；能不能
情况2：
此时[ begin1, end1 ]=[ 8, 9 ]，[ begin2, end2 ]=[ 10, 11 ]；[ begin2, end2 ]区间不存在元素，虽然在情况1的基础上将其修改为不存在的区间，但是[ begin1, end1 ]有两个元素，一个是2，一个是随机值，当数据入tmp数组时，会把这个随机值带入，并拷贝回原数组；此时数组已经越界，一定会存在错误；此时还要将end1修正为8（end=n-1），那么此区间就只有一个元素了，就不会出现数组越界的情况；
情况3：
此时[ begin2, end2 ]=[ 8, 15 ]，此区间是不存在元素的；还需要将end2进行修正，修正为8（end=n-1）；也是由于此区间存在3个随机值，修正的目的就是让此区间只有一个明确的值存在的值，确保数组不越界；
以上就是针对数组元素个数非2^n时的边界控制，只要掌握归并排序的边界控制，其代码实现就变得容易许多；
代码实现
//归并排序(非递归)----适用于2的n次方 void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } int gap = 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; /*******************************重要*****************************/ //end1越界 [begin2,end2]不存在 if (end1 >= n) { //进行修正 end1 = n - 1; } // [begin1,end1]存在,[begin2,end2]不存在 if (begin2 >= n) { //进行修正 begin2 = n; end2 = n - 1; } //end2越界 if (end2 >= n) { end2 = n - 1; } /********************************重要****************************/ int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } } //printf("\n"); //把归并好的数据拷贝回原数组 for (int i = 0; i < n; ++i) { a[i] = tmp[i]; } gap *= 2; } free(tmp); tmp = NULL; }
2.方法2：分组归并、逐次归并拷贝——边界控制的阐述
1.基本思路：
2.边界控制
假设现有一个9个元素的数组，如何对其进行边界控制？
以gap=gap*2（gap>=1）的增长方式进行每组的归并操作，首先将数组分成两个区间，分别表示为[ begin1，end1 ]和[ begin2，end2 ];
如图所示：
与方法一不同的是，此方法不需要整体归并完后拷贝到原数组中去，而是归并一次拷贝一次，所有并不需要考虑原数组中数字2会被覆盖为随机值的情况；但是对于边界的问题在循环迭代的过程中，依然存在如下几中情况：
情况1：
因为是归并一次数据就拷贝回原数组，所以并不会影响到原数组末尾的2；此时end越界，将end修正，修正为8（end=n-1）；
情况2与情况3：
这两种情况在end2修正后，end1和begin2存在越界，因为是归并一次数据就拷贝回原数组，所以并不会影响到原数组末尾的2；所以只要当end1和begin2越界时，让其不执行拷贝的操作就可以了（即代码实现时让其遇到此情况就跳出循环，去执行下一次gap分组）
代码实现
/*第二种*/ void MergeSortNonR2(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } int gap = 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; int index = i; //核心思想：end1、begin2、end2都有可能越界 //end1越界 if (end1 >= n || begin2 >= n) { break; } //end2越界,需要归并，修正end2 if (end2>=n) { end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //把归并好的数据拷贝回原数组 for (int j = i; j <= end2; ++j) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); tmp = NULL; }
