代码实现
//hoare版本单趟 int part_sort1(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[midi], &a[left]); int keyi = left; while (left < right) { while (left < right && a[right] >= a[keyi])//R先走，找小于key的值停下 { --right; } while (left < right && a[left] <= a[keyi])//L后走，找到大于key的值 { ++left; } //执行交换 Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); return left; }
（2）挖坑法
挖坑法相较于hoare法，更加容易理解，就是我们把key这个位置的数据拷贝出来，然后把这个位置看作是一个坑，然后右边找小，放在坑位里，左边找大放在新的坑位里，直到两个下标相遇，把key放在最终的坑里。
动图演示
代码实现
int part_sort2(int* a, int left, int right)//挖坑法 { //三数取中 int midi = GetMidIndex(a, left, right); Swap(&a[midi], &a[left]); int key = a[left]; int hole = left; while (left < right) { while (left < right && a[right] >= key)//右边找小的 { right--; } a[hole] = a[right]; hole = right; while (left < right && a[left] <= key)//左边找大的 { left++; } a[hole] = a[left]; hole = left; } a[hole] = key; }
（3）前后指针法
我们定义三个变量：keyi = left、prev = left 和 cur = prev +1，其中的 keyi 代表 key 值所在的下标，而 prev 和 cur 就是我们的主角 – 前后指针了；我们让 cur 先走，当找到小于 a[keyi] 的元素时停下来，然后先让 prev++，再判断 prev 是否等于 cur，如果不等于就交换二者对应元素的值，然后重复前面的步骤，直到 cur > right；最后交换 a[keyi] 和 a[prev] 即可。
动图演示
代码实现
int part_sort3(int* a, int left, int right)//前后指针法 { //三数取中 int midi = GetMidIndex(a, left, right); Swap(&a[midi], &a[left]); int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } Swap(&a[keyi], &a[prev]); return prev; }
1.2快排的非递归实现
为什么会有递归转换成非递归求解的必要呢？我们使用递归不是能够非常轻松的求解问题，而且思路非常简单吗？但是我们要知道，每递归一层，都会在栈上开辟一层栈帧，栈的空间是非常小的，一般只有8M左右，所以如果遇到递归层数非常多的情况，就会出现栈溢出，所以我们要把递归转换为非递归。关于递归转非递归的思想，在之前我们就使用过，比如求解斐波那契数列的时候，我们就使用了循环的方式来改写递归。但是，对于这种较为复杂的情况，我们还是需要借助一些数据结构来实现。这里我们就使用我们的数据结构栈来实现。
在函数递归的过程中，本质也是在栈帧中存放数据，我们可以把这个数据给存放在我们自己开辟的栈里面，分析算法得知，在递归的过程中，栈帧里面存放的是数组的下标，那么我们可以把它存在栈中，然后每次取出一个数组区间，把这个区间进行一次快排，然后再次分成两个子区间，直到这个区间全部排序成功，栈为空，结束循环。代码实现见6.2.2。
2.代码实现
2.1递归版本
void QuickSort(int* a, int begin, int end) { if (begin >= end) return; int keyi = part_sort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
小区间优化
我们知道，二叉树的叶子节点占据了所有节点的半数，而且递归到最后几层节点的时候，数组区间已经非常小了，这个时候我们可以再调用直接插入排序，此时的效率就会更高啦。
优化后代码
void QuickSort(int* a, int begin, int end) { if (begin >= end) return; if (end - begin < 8) { InsertSort(a + begin, end - begin + 1); } else { int keyi = part_sort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
2.2非递归版本
void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(&st); StackPush(&st, left); StackPush(&st, right); while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); if (left >= right) continue; int keyi = part_sort1(a, left, right); //[left,keyi-1] keyi [keyi+1,right] StackPush(&st, keyi + 1); StackPush(&st, right); StackPush(&st, left); StackPush(&st, keyi - 1); } StackDestory(&st); }
3. 复杂度和稳定性
时间复杂度上文已经分析过了，这里就不过多赘述
空间复杂度
对于递归的方式，由于没有创建额外的空间，所以空间复杂度为O(1),对于非递归的方式，我们使用了数据结构栈，又额外消耗，所以为O(logN)。
4.特性总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以被称之为快速排序；
- 时间复杂度：O(N*logN)；
- 空间复杂度：O(1) – 递归，O(logN) – 非递归；
- 稳定性：由于快速排序选出的 key 值是不确定的,所以不稳定
7.归并排序
1.排序思想
1.1递归版本
归并排序的思想就是基于将两个有序数组合并为一个新的数组，并保持其有序状态，我们要保证两个数组都有序，就需要对两个数组分别调用归并排序。就这样递归下去，当数组内只有一个元素的时候，这个数组就是已经有序的，不需要再调用归并，此时递归调用结束。排序完成。
1.2非递归版本
归并排序的非递归不能使用栈来实现，因为同一区间的begin或end可能会别多次使用，而是像斐波那契数列一样，通过前面的区间来得到后面的区间，我们定义一个 gap 变量，用于指定每次进行排序的一组数据元素的个数，然后定义循环，让两组数据进行归并，待数组所有组都两两归并之后，我们再让 gap *= 2，让其归并更大组的数据，直到 gap > n 时，数组有序；
但是上述方法只能用于排序拥有 2^n 个数据的数组，当数组元素个数不满足这个条件时，就会发生越界访问，此时，我们可以分析一下，发生越界访问的情况共有三种
1、第一组越界：第一组越界时只可能是 right 越界，因为如果连第一组的 left 都越界了那根本就不会进行归并，此时，第二组一定全部越界；这种情况下只有一组数据，不需要归并，直接break；
2、第二组全部越界，即第二组 left 越界，第一组没越界；这种情况下也只有一组数据，不需要归并，直接break
3、第二组部分越界，即第二组的 right 越界，left 没越界；此时存在两组数据，需要将第二组的right修正，然后继续进行归并；
动图演示
2.代码实现
2.1递归版本
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = begin + (end - begin) / 2; //[begin,mid] [mid+1,end] _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); //归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; 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++]; } //拷贝回原数组 memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
2.2非递归版本
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int gap = 1; while (gap < n) { for (int j = 0; j < n; j += 2 * gap)//gap个数据归并 { //归并 int begin1 = j, end1 = j + gap - 1; int begin2 = j + gap, end2 = j + 2 * gap - 1; int i = j; //修正边界 if (end1 >= n)//第一组越界 { break; } if (begin2 >= n)//第二组全部越界 { break; } if (end2 >= n)//第二组部分越界 { end2 = n - 1; } 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++]; } memcpy(a + j, tmp + j, (end2 - j + 1) * sizeof(int)); } gap *= 2; } free(tmp); tmp = NULL; }
3.复杂度
时间复杂度
对于递归版本的归并排序来说，递归的深度为 logN，每一层待排序的元素个数都为 N，所以时间复杂度是严格的 O(NlogN)；对于非递归来说，gap 每次增加二倍，每次 gap 中待排序的数据等于或者小于 N，所以非递归的时间复杂度也是 O(NlogN)；
空间复杂度
归并排序需要额外开辟一个与原数组同等大小的数组用于归并，所以空间复杂度为：O(N)；
4.特性总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题；
- 时间复杂度：O(N*logN)；
- 空间复杂度：O(N)；
- 稳定性：稳定。
8.计数排序
1.排序思想
计数排序是对哈希定址法的应用，是非比较排序，就是遍历数组，将所有数据出现的次数映射在对应数组下标的空间内(映射分为绝对映射和相对映射，相对映射是绝对映射的优化)。遍历完数组之后，我们开辟的新数组内部，对应的下标内存放的就是该下标元素出现的次数，那么我们就可以对这些数据进行处理，把数据依次覆盖到原数组内部。
2.代码实现
void CountSort(int* a, int n) { int min, max; max = min = a[0]; for (int i = 1; i < n; ++i)//找到数组中最大和最小的数 { if (max < a[i]) { max = a[i]; } if (min > a[i]) { min = a[i]; } } int range = max - min + 1;//给出映射范围 int* tmp = (int*)calloc(range, sizeof(int));//开辟新数组 assert(tmp); for (int i = 0; i < n; ++i)//计数 { tmp[a[i] - min]++; } //将计数以后的值覆盖到原数组 int j = 0; for (int i = 0; i < n; ++i) { while (tmp[i]--) { a[j++] = i + min; } } free(tmp); tmp = NULL; }
3.复杂度
时间复杂度
时间复杂度为O(N+range)
空间复杂度
在计数的时候开辟的新的空间，这段空间的大小是range，所以空间复杂度位O(range)
4.特性总结
- 只能排序整形数据，不能排序浮点数、字符串等其他类型的数据；
- 只使用与数据分布范围较小的情景，当数据分布较分散时，空间消耗太大；
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
覆盖到原数组内部。
2.代码实现
void CountSort(int* a, int n) { int min, max; max = min = a[0]; for (int i = 1; i < n; ++i)//找到数组中最大和最小的数 { if (max < a[i]) { max = a[i]; } if (min > a[i]) { min = a[i]; } } int range = max - min + 1;//给出映射范围 int* tmp = (int*)calloc(range, sizeof(int));//开辟新数组 assert(tmp); for (int i = 0; i < n; ++i)//计数 { tmp[a[i] - min]++; } //将计数以后的值覆盖到原数组 int j = 0; for (int i = 0; i < n; ++i) { while (tmp[i]--) { a[j++] = i + min; } } free(tmp); tmp = NULL; }
3.复杂度
时间复杂度
时间复杂度为O(N+range)
空间复杂度
在计数的时候开辟的新的空间，这段空间的大小是range，所以空间复杂度位O(range)
4.特性总结
- 只能排序整形数据，不能排序浮点数、字符串等其他类型的数据；
- 只使用与数据分布范围较小的情景，当数据分布较分散时，空间消耗太大；
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
