快排（非递归）
算法实现
void Quicksortnon(int* a, int begin, int end) { SK sk; SKinit(&sk); SKpush(&sk, begin); SKpush(&sk, end); while (!SKempty(&sk)) { int right = SKtop(&sk); SKpop(&sk); int left = SKtop(&sk); SKpop(&sk); int key = Partsort3(a, left, right); if (key + 1 < right) { //左边先入栈 SKpush(&sk, key + 1); SKpush(&sk, right); } if (left < key - 1) { //右边后入栈 SKpush(&sk, left); SKpush(&sk, key - 1); } } }
快排的特点
综合性能较好，适应场景较多
时间复杂度：O(N*logN)
空间复杂度：O（logN)
稳定性：不稳定
归并排序（递归）
思路：将已有序的子序列合并，得到完全有序的序列；若子序列未有序，先使子序列有序，再进行合并（符合分治法的思想）
算法实现
void mergesort(int* a, int begin, int end, int* tmp) { //递归结束条件 if (begin >= end) { return; } //将数组平分 int mid = begin + (end - begin) / 2; //进行递归 mergesort(a, begin, mid, tmp); mergesort(a, mid+1, end, tmp); //归并 取小的尾插 int begin1 = begin; int end1 = mid; int begin2 = mid + 1; int 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(n * sizeof(int)); if (tmp == NULL) { perror("malloc fail"); return; } int begin = 0; int end = n - 1; //如果直接在归并函数中递归，每次都会开辟空间，导致程序崩溃 //所以创建子函数进行归并 mergesort(a, begin, end, tmp); free(tmp); tmp = NULL; }
归并排序（非递归）
算法实现
void Mergesortnon(int* a, int n) { //开辟空间，用于排序 int* tmp = (int*)malloc(n * sizeof(int)); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { int j = 0; //每组gap个数据 for (j = 0; j < n; j += 2 * gap) { //取小尾插，进行归并 int begin1 = j; int end1 = j + gap - 1; int begin2 = j + gap; int end2 = j + 2 * gap - 1; int i = j; 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; }
图示分析似乎没有什么问题，但如果再向数组中加一个数，结果会怎么样呢？
如果再向数组中加入一个数，结果又是怎么样的呢？
目前出现的这两种情景，上面都没有考虑到，那又该如何解决呢？
先将每次分组的数据下标打印出来，再进行分析
总结下来越界有三种可能
前一组的end1越界
后一组全部越界
后一组end2越界
解决办法
直接跳出循环，剩余的数据不再临时开辟的空间中进行排序
直接跳出循环，剩余的数据不再临时开辟的空间中进行排序
修改end2的数值，end2=n-1 再进行排序
优化后
void Mergesortnon(int* a, int n) { //开辟空间，用于排序 int* tmp = (int*)malloc(n * sizeof(int)); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { int j = 0; //每组gap个数据 for (j = 0; j < n; j += 2 * gap) { //取小尾插，进行归并 int begin1 = j; int end1 = j + gap - 1; int begin2 = j + gap; int end2 = j + 2 * gap - 1; int i = j; //第一组end1越界 if (end1 >= n) { printf("[%d,%d]",begin1,end1); break; } //第二组全部越界 if (begin2 >= n) { printf("[%d,%d]",begin1,end1); break; } //第二组部分越界 if (end2 >= n) { //修改end2,继续归并 end2 = n - 1; } printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2); 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; printf("\n"); } free(tmp); tmp = NULL; }
归并排序的特点
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
计数排序
思路：
先统计相同元素出现的次数，然后开辟相对大小的空间（最大值-最小值+1），将相同元素按照对应的下标中赋以其出现的次数
用于计数的数组的下标时其对于的值（相对）的个数，某个值出现几次，便会被计数几次
算法实现
void Countsort(int* a, int n) { int max = a[0]; int min = a[0]; int i = 0; for (i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; //统计次数 int* tmp = (int*)malloc(sizeof(int) * range); memset(tmp, 0, sizeof(int) * range); for (i = 0; i < n; i++) { tmp[a[i] - min]++; } //排序 int j = 0; for (i = 0; i < range; i++) { while (tmp[i]--) { a[j] = i + min; j++; } } free(tmp); tmp = NULL; }
计数排序的特点
当数据范围比较集中时，效率很高
时间复杂度：O(N,range)
空间复杂度：O(range)
稳定性：稳定
