1.2.4 非递归实现快排
基本思想：
借助栈来实现（用队列也行，只是栈更能生动的表示分治时不断递归的过程），先让最右边的下标先入栈，再让最左边的下标入栈，当栈不为空时然后出栈，先出的就是最左边的下标，再出最右边的下标，单趟排序后再不断重复入栈出栈过程，直至栈为空就排序好了。
具体代码实现：
void QuickSort3NonR(int* a, int sz) { ST st; StackInit(&st); StackPush(&st, sz - 1); StackPush(&st, 0); while (!StackEmpty(&st)) { int left = StackTop(&st); StackPop(&st); int right= StackTop(&st); StackPop(&st); int keyIndex = PartSort3(a, left, right); //[left,keyIndex-1] keyIndex [keyIndex+1,right] if (keyIndex + 1 < right) { StackPush(&st, right); StackPush(&st, keyIndex + 1); } if (left < keyIndex) { StackPush(&st, keyIndex); StackPush(&st, left); } } StackDestroy(&st); }
注意事项：
- 入栈的时候其实先入右和先入左都行，只是取的时候要控制好取得是啥。
- 单趟排序用快排的3中方法都行，但是为了调试效果明显最好就不要加3数取中了。
1.2.5 快排的3路并归
通过上面我们知道快排当重复数据过多时效率就比较低下了，解决得办法是用3路并归来实现。具体思路是单趟排序将其分为3个区间[left,begin-1] [begin,end] [end+1,right]
其中[begin,end]区间维护得是每次选出来的等于key的数据。
具体代码：
void QuickSort(int* a, int left, int right) { if (left >= right) return; int mid = GetMidNum(a, left, right); Swap(&a[left], &a[mid]); int key = a[left]; int begin = left, cur = left + 1, end = right; //分成3个区间[left,begin-1] [begin,end] [end+1,right] while (cur <= end) { if (a[cur] < key) { Swap(&a[cur], &a[begin]); cur++; begin++; } else if (a[cur] == key) cur++; else { Swap(&a[cur], &a[end]); end--; } } QuickSort(a, left, begin - 1); QuickSort(a, end + 1, right); }
快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫 快速 排序
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(logN)
4. 稳定性： 不稳定 （单趟排序时有可能将相同数据的相对位置打乱）
2 归并排序
2.1 归并排序的递归实现
基本思想：
归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用 分治 法（ Divide and Conquer ）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序 列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有表，称为二 路归并。
图解：
具体代码：
void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) { return; } int mid = (left + right) >> 1; //假设[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 index = left; //合并 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 i = left; i <= right; i++) { a[i] = tmp[i]; } } void MergeSort(int* a, int sz) { int* tmp = (int*)malloc(sizeof(int) * sz); _MergeSort(a, 0, sz - 1, tmp); free(tmp); }
注意事项：
当数据归并到最后一部分时别忘了将数据拷回去。
2.2 归并排序的非递归实现
基本思想：
归并排序的非递归用栈和队列实现起来比较困难，比较优的方法是借助循环来整。
具体代码：
第一种方式：
void MergeSortNonR(int* a, int sz) { int* tmp = (int*)malloc(sizeof(int) * sz); if (!tmp) { perror("malloc:"); exit(-1); } int rangeN = 1;//代表每组归并的数据个数 while (rangeN < sz) { for (int i = 0; i < sz; i += 2 * rangeN) { int begin1 = i, end1 = i + rangeN - 1, begin2 = i + rangeN, end2 = i + 2 * rangeN - 1, index = i; //printf("[%d %d] [%d %d]\n", begin1, end1, begin2, end2); //通过打印不难发现越界有三种情况： //1 end1 begin2 end2 越界 //2 begin2 end2 越界 //3 只有end2越界// if (end1 >= sz) { //有两种处理方式： break;//直接break跳出去，这种方式拷贝只能放在里面一次一次的拷贝，不能一次性全部拷贝，否则有可能将随机数（越界）给拷了回去 //第二种方式：修正 /*end1 = sz - 1; begin2 = sz; end2 = sz - 1;*/ //这里注意要将begin2和end2修正成begin2>end2形式（不能够加+），不让其进入下面的循环 } else if (begin2 >= sz) { break;//1 直接跳出 /*begin2 = sz; end2 = sz - 1;*/ //修正 } else if (end2 >= sz) { end2 = sz - 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++]; memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//不能写成2*rangeN，有可能会越界 } rangeN *= 2; //memcpy(a, tmp, sizeof(int) * sz);//这种方式是错误的,由于没有修正让随机数也被拷贝了过去，让原数据被覆盖 } }
第二种方式：
void MergeSortNonR(int* a, int sz) { int* tmp = (int*)malloc(sizeof(int) * sz); if (!tmp) { perror("malloc:"); exit(-1); } int rangeN = 1;//代表每组归并的数据个数 while (rangeN < sz) { for (int i = 0; i < sz; i += 2 * rangeN) { int begin1 = i, end1 = i + rangeN - 1, begin2 = i + rangeN, end2 = i + 2 * rangeN - 1, index = i; //printf("[%d %d] [%d %d]\n", begin1, end1, begin2, end2); //通过打印不难发现越界有三种情况： //1 end1 begin2 end2 越界 //2 begin2 end2 越界 //3 只有end2越界// if (end1 >= sz) { //第二种方式：修正 end1 = sz - 1; begin2 = sz; end2 = sz - 1; //这里注意要将begin2和end2修正成begin2>end2形式（不能够加+），不让其进入下面的循环 //如果是整体拷贝end2可以修改成任意小于begin2的数，一个一个拷贝的话只能修改成sz-1 } else if (begin2 >= sz) { begin2 = sz; end2 = sz - 1; //修正成不合理的形式 } else if (end2 >= sz) { end2 = sz - 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++]; //memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//不能写成2*rangeN，有可能会越界 } rangeN *= 2; memcpy(a, tmp, sizeof(int) * sz); } }
注意事项：
注意事项代码中都已经给出了说明。
归并排序的特性总结：
1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(N)
4. 稳定性： 稳定 （可以控制相同数据的相对位置不发生改变）
3.排序算法复杂度及稳定性分析
排序这方面就到处结束啦，如果有哪儿不对的地方希望各位佬能够指正。
