一、排序概念及其运用
1. 排序的概念
以下是排序的一些相关概念：
- 排序：使一串记录，按照其中某个或某些关键字的大小，让其以递增或递减方式排列起来的操作。
- 稳定性：排序中，遇到相同的关键字时，在排序结束后相同关键字依然保持原来顺序的能力。即在原序列中r[i]=r[j]，且r[i]在r[j]之前，那么排序后依然保持r[i]在r[j]之前。
- 内部排序：数据元素全部存放在内存中的排序。
- 外部排序：数据元素个数太多而不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。（指排序主要在外部存储设备上进行，避免内存和外存之间的频繁移动）
2. 排序的应用
- 京东或者淘宝之类网上商城的商品间价格、销量、评价数量的排序。
- 国内外高校的综合实力排名。
- 游戏内玩家的综合战力排名。
。。。
3. 常见排序算法
其中所有排序都是内排序，归并排序同时也是外排序。（内外指的是内外存，归并排序适合在外存中处理大量数据）
// 排序实现的接口// 插入排序
void InsertSort(int* a, int n);// 希尔排序
void ShellSort(int* a, int n);// 选择排序
void SelectSort(int* a, int n);// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);// 冒泡排序
void BubbleSort(int* a, int n)// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)// 计数排序
void CountSort(int* a, int n)
二、常用排序算法的实现
1. 冒泡排序
冒泡排序在C语言学习初期就作为一道基础题出现过，其思路简单，好上手，但其时间复杂度过高而导致其目前只有教学作用，实际项目中几乎用不上。
- 思路(升序)：从左到右两个数之间两两相比，直到把序列中最大的数放至最右边。重复该步骤，直至排序完成。
假设数组元素个数是n，且数组是倒序，那么第一组交换次数为n-1，第二组为n-2，。。。，第n-1组为1，用等差数列求和公式可得出其时间复杂度为O(N^2)。
//冒泡排序就是两两相比，交换，从左到右，将最大元素放到最右边，最坏时间复杂度O(N^2)，最好O(N^2)
// 但部分无序时，插入排序比冒泡排序好很多
//优化：如果有序就不排列
void bubble_sort(int* a, int n) //建议先写单趟，再写次数控制！
{for (int i = n - 1; i >= 0 ; i--){bool exchange = false; //内置判断是否为升序for (int j = 1; j <= i; j++){if (a[j - 1] > a[j]){swap(&a[j - 1], &a[j]);exchange = true;}}if (exchange == false){break;}}
}
2. 插入排序
思路：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际中我们玩扑克牌时，就用了插入排序的思想
特点：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
//1. 插入排序，待排序元素与其前面元素比较大小，并交换顺序，然后再轮到下一个元素，依此类推
// 时间复杂度：最坏情况(降序数组)：O(N^2); 最好情况(升序数组)：O(N)
void insert_sort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1; //待排序数的上一个数的下标int temp = a[i]; //保存待排序的数while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = temp;}
}
3. 希尔排序（缩小增量排序）
先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
特点：
希尔排序是对直接插入排序的优化，将数据分为一个个组，对每一组进行插入排序，这个过程称为预排序。当最后gap=1时，数据已接近有序，再进行插入排序便会快很多。
希尔排序的时间复杂度不好计算，我们暂定为O(N^1.3)
//2. 希尔排序
//先预排序，使目标接近有序，然后再直接插入排序
//预排序：
//1.间隔为gap的元素之间分为一组
//有两种写法：1.排完一组再排另一组；2.多组并排
//gap多少合适？
//gap越大，跳得越快，越难以接近有序；而gap越小，越接近有序
//可以设置gap为n，然后gap每次除2，直到gap等于1结束循环，这样就可以不用插入排序了// 时间复杂度：
// 最开始gap很大：gap = n/3+1 or n/2 -> N
// 最后gap很小：gap=1 -> N(因为预排序，复杂度不再是N^2)
// n->∞时，时间复杂度为O(N*(logN)^2)
// 结论：O(N^1.3)void shell_sort_1(int* a, int n) //多组并排
{int gap = n;while (gap > 1){gap /= 2; //一定要保证最后一次排序的gap是1for (int i = 0; i < n - gap; i++) //end不会触到最后一个数，只有temp才会，这是插排的性质{int end = i;int temp = a[i + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}print_array(a, n);}}void shell_sort_2(int* a, int n) //一组一组排
{int gap = n;while (gap > 1){gap /= 2; //一定要保证最后一次排序的gap是1for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap) //end不会触到最后一个数，只有temp才会，这是插排的性质{int end = i;int temp = a[i + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}print_array(a, n);}}
}
3. 选择排序
每一次从待排序数组中选择最小或最大的元素，存放到待排序数组的起始位置(与起始位置的元素进行交换)，直至排序完成。
特点：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
//3. 直接选择排序，选最小最大，交换，再选次小次大，交换，依此类推，直到排序完成
//最好最坏的情况下时间复杂度都是：O(N^2)void select_sort(int* a, int n)
{int left = 0;int right = n - 1;while (left < right){int min = left;int max = left;for (int i = left; i <= right; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}swap(&a[left], &a[min]);if (max == left) //调试时，max与left重叠，意味着原来最大的数在最左边，//如今最大与最小互换了，那么就将min给max，调整下标{max = min;}swap(&a[right], &a[max]);left++;right--;}
}
4. 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
堆排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
typedef int hp_data_type;//大堆
typedef struct heap
{hp_data_type* a;int size; //总指向最后一个元素的下一位int capacity;
}hp;void swap(hp_data_type* a, hp_data_type* b)
{hp_data_type temp = *a;*a = *b;*b = temp;
}void adjust_up(hp_data_type* a, int child) //向上调整，子节点大于父节点，就互换
{int parent = (child - 1) / 2;while (child > 0) //当子节点循环到根时就停止{if (a[parent] < a[child]){swap(&a[child], &a[parent]);//hp_data_type temp = a[parent];//a[parent] = a[child];//a[child] = temp;child = parent;parent = (child - 1) / 2;}elsebreak;}
}void adjust_down(hp_data_type* a, int n, int parent)
{assert(a);int child = parent * 2 + 1;while (child < n) //当孩子节点下标大于等于最后数组最后元素下标时，就不用继续比下去{if ((child + 1 < n) && a[child] < a[child + 1])//左孩子+1就是右孩子, 为什么child+1<n，而不是<=，因为n为元素个数{child++;}if (a[child] > a[parent]) //建大堆还是小堆通过符号来更改{swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void heap_sort(int* a, int n) //n为元素个数, 堆排序,整个复杂度O(N*logN)
{//注意不同建堆方法的开始调整位置//法一：向上调整建堆：复杂度为O(N*logN)//for (int i = 1; i < n; i++) //头元素不用调，从第二个元素开始调，将第二个元素设为孩子//{// adjust_up(a, i); //}//法二：向下调整建堆，从最后一个子树开始调，一直调到第一个子树,复杂度为O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--) //找最后一个叶节点的父节点{adjust_down(a, n, i);}int end = n - 1;while (end > 0) //开始排序,复杂度：O(N*logN){swap(&a[0], &a[end]); //第一个数一定是最大的数，第一个和最后一个调换adjust_down(a, end, 0); //调整堆，堆的元素个数少了1个（已经往前挪了1个）end--; //使最后节点往前挪}
}
4. 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：
- hoare版本
- 挖坑法
- 前后指针法
快速排序的特性总结：
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
//5. 快速排序，复杂度也是O(N*logN)，逆序和顺序都是最坏情况，是N^2，很可能栈溢出
//升序：右边找小，左边找大；降序时就反过来；左边做key，右边先走
//先写单趟排序
//递归单趟，当左下标等于右下标时就结束
//为什么left和right相遇时的那个值一定比key要小？
//答：左边做key，右边先走，反之亦然，保证上面结论。
//相遇的两种情况：
//1. R找到小，L没有找到大，L遇到R，此时相遇的值肯定比R小，即比key所在位置的值小；
//2. R找不到小，直接跟L相遇，此时相遇的值肯定小于等于R。
//所以要先找小！// 还有一种方法：三数取中选key
// 从第一个数，最后一个数，中间的数 中 选处于中间的值(返回中间数的下标)
int get_mid_num_i(int* a, int left, int right)
{int mid = (left + right) / 2;if ((a[left] <= a[mid] && a[mid] <= a[right]) || (a[right] <= a[mid] && a[mid] <= a[left])) {return mid;}else if ((a[mid] <= a[left] && a[left] <= a[right]) || (a[right] <= a[left] && a[left] <= a[mid])) {return left;}else {return right;}
}//Hoare法
int quick_sort_hoare(int* a, int begin, int end) //初始快排
{if (begin >= end)return 0;int key = begin; //设左边为key，右边先走// 如果key每次都接近中间值，那么效率更高，那么选取key很重要// int randi = left + (rand()%(right - left)); //随机选key// swap(&a[key], &a[randi]);// 三数取中, 对有序或接近有序的数组效率更高// int midi = get_mid_num_i(a, left, right);//swap(&a[key], &a[midi]);int left = begin;int right = end;while (end > begin){while (a[end] >= a[key] && end > begin) //右边找小，找到比key小的数就停下，加等号防止死循环，加上另一个条件防止漂移end--;while (a[begin] <= a[key] && end > begin) //左边找大，遇到比key大的数就停下begin++;swap(&a[begin], &a[end]); //左右互换值}swap(&a[begin], &a[key]); // key的值与left互换key = begin; // key放到基准位置quick_sort_hoare(a, left, key - 1); //开始递归左区间quick_sort_hoare(a, key + 1, right); //开始递归右区间return key;}//改进快排：挖坑法
//思路：
// 1.将第一个数据存放在临时变量key中，原本存放第一个数据的位置形成坑位；(或者是三数取中的key)
// 2.右边先行，找小，找到小的将这个值放到坑位中，然后目前的位置形成新的坑位；
// 3.左边找大，找到大的就将这个值放进坑位中，目前位置形成新的坑位；
// 4.依此类推， 最后左右一定相遇在坑上，再将key填到坑上。
//两种方法单趟排出来不一定相同，但本质没变。
void quick_sort_pit(int* a, int begin, int end)
{if (begin >= end)return;int keyi = get_mid_num_i(a, begin, end); //三数取中得key，另一边边先走//int midi = get_mid_num_i(a, begin, end);//swap(&key, &a[midi]);swap(&a[keyi], &a[begin]); //三数取中后要将这个中值放到最左边！！！int key = a[begin];int left = begin;int right = end;int pit = begin;while (right > left){while (a[right] >= key && right > left) //右边找小，找到比key小的数就停下，加等号防止死循环，加上另一个条件防止漂移{right--;}a[pit] = a[right];//找到小之后形成新坑pit = right;while (a[left] <= key && right > left) //左边找大，遇到比key大的数就停下{left++;}a[pit] = a[left]; //找到大之后填坑并形成新坑pit = left;}a[pit] = key; // key的值赋给新坑keyi = pit;quick_sort_pit(a, begin, keyi - 1); //开始递归左区间，注意不要用left和right，这两个是移动过的！quick_sort_pit(a, keyi + 1, end); //开始递归右区间
}//快排方法3：前后指针法
//思路：
// 1.cur找到比key小的值，++prev，cur与prev的值交换，++cur；(一开始，prev在左边，cur在prev后面一位)
// 2.cur找到比key大的值，++cur；
// 3.直到cur越界，prev的值与key互换。
//情况：
// 1.prev紧跟着cur；
// 2.prev与cur之间间隔着一段比key大的值；
// 最终比key大的值都翻到右边，小的翻到左边void quick_sort_point(int* a, int begin, int end)
{if (begin >= end)return;int* cur;int* prev;int keyi = get_mid_num_i(a, begin, end);swap(&a[keyi], &a[begin]);prev = &a[begin];cur = &a[begin] + 1;while (cur != &a[end] + 1){if (*cur > a[begin]){cur++;}else{prev++;swap(cur, prev);cur++;}}swap(prev, &a[begin]);quick_sort_point(a, begin, prev - a - 1); //注意：此时中间值的位置是prev，而不是keyi！quick_sort_point(a, prev - a + 1, end);
}// 看数据量选排序方法，数据量极大就用希尔和快排；数据量较小，100个以内用插入排序就好//如果一直递归，区间越来越小，那么小区间的递归次数比较多，浪费时间，那么就可以进行小区间优化，即不通过递归而是其它方式进行排序，如插入排序
//小区间优化：二分情况下最理想，可消灭87.5%的递归次数void quick_sort_optimizing(int* a, int left, int right)
{if (right - left + 1 > 10) //大区间用快排，大区间有多大自己定，太大不行，太小也不行{quick_sort_point(a, left, right);}else //小区间用插入，小区间优化{insert_sort(a + left, right - left + 1); //左边参数是因为区间不一定从第一个元素开始}
}//递归存在的问题：1. 深度太深，栈帧扛不住，会溢出；2. 效率不太高，每次都要调用栈帧（数据量大时，影响很大）//解决方法：
//1. 递归改非递归：
// 直接改循环；如斐波那济数列
// 使用栈辅助改循环；如二叉树// 先将单趟快排作为一个函数写出来, 返回keyi
static int part_quick_sort(int* a, int left, int right)
{int* prev;int* cur;int keyi = get_mid_num_i(a, left, right);swap(&a[left], &a[keyi]);prev = &a[left];cur = prev + 1;while (cur != &a[right] + 1){if (*cur > a[left]){++cur;}else{++prev;swap(prev, cur);cur++;}}swap(prev, &a[left]);return prev-a; //这个才是中间位置
}// 1.栈内取一段区间，单趟排序；
// 2.单趟排好后，再将单趟分割的子区间入栈；
// 3. 子区间只有1个值或者不存在就不入栈。
void quick_sort_non_recur(int* a, int left, int right)
{stack st;stack_init(&st);//入栈先右后左，出栈时才可以先左后右stack_push(&st, right);stack_push(&st, left);while (!stack_empty(&st)){int begin = stack_top(&st);stack_pop(&st);int end = stack_top(&st);stack_pop(&st);int keyi = part_quick_sort(a, begin, end); //单趟排序并返回中间下标// 入左右区间[begin, keyi-1] [keyi+1, end]if (keyi + 1 < end) //只有1个或没有就不入{stack_push(&st, end);stack_push(&st, keyi + 1);}if (begin < keyi - 1){stack_push(&st, keyi - 1);stack_push(&st, begin);}}stack_destroy(&st);
}
5. 归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
//归并排序
//两个有序区间归并：依次比较，小的尾插到新空间（区间元素数量相等）
//子区间归并排序-》全区间归并排序
//类似于后序遍历，整体复杂度O(N*logN)//先开一个临时数组，这个临时数组在原函数里面开
//取中，递归两个区间，依次往下，剩下一个数时就返回
//每个区间都要归并到临时数组，然后将临时数组的值拷贝回原数组相应位置void _merge_sort(int* a, int begin, int end, int* temp) //一般函数名开头有下划线代表其是原函数的核心部分
{if (begin >= end)return;int mid = (begin + end) / 2;_merge_sort(a, begin, mid, temp); //每次传的temp都是临时数组的起始位置，因为递归栈帧独立，每层递归的temp是不同的_merge_sort(a, mid + 1, end, temp);int left1 = begin; int right1 = mid;int left2 = mid + 1; int right2 = end;while (left1 <= right1 && left2 <= right2) //两区间归并{if (a[left1] <= a[left2]){*(temp++) = a[left1++];//left1++;//temp++;}else{*(temp++) = a[left2++];//left2++;//temp++;}}//若两区间其中一个没走完，就继续走，直到走完为止while (left1 <= right1){*(temp++) = a[left1++];}while (left2 <= right2){*(temp++) = a[left2++];}//归并完了就拷贝回原数组//注意：因为归并的特点是两两排序然后四四排序(递归的后序遍历)，依此类推，每排序完一个区间就要copy回去；//所以paste回去时就要注意区间的起始点。//temp每次排完序时里面存放的是排序好的数，因为每次递归要排序的数的数量不同，//所以copy时要回退区间内元素的数量memcpy(a + begin, temp - (end - begin + 1), (end - begin + 1) * sizeof(int));}
void merge_sort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail.");return;}_merge_sort(a, 0, n - 1, temp);free(temp);
}//非递归实现归并排序
//在归并过程中会出现三种情况
//1. end1越界
//2. end1没越界，但begin2越界
//3. end1，begin2没有越界，但end2越界
//处理方法1
//情况1，2：修正end1，越界的不归并，越界的区间修正成不存在的区间，使得其走不了循环
//情况3：修正end2，继续归并
//处理方法2
//如果越界那就直接跳过这次的归并，不拷贝到数组上，但这个方法要将拷贝操作放入循环内（归并一组拷贝一组，非归并完后一次性拷贝）
//建议拷贝放在循环内，这样更好控制
void merge_sort_non_recur(int* a, int n)
{//定义gap，代表归并过程中，每组的数据个数int gap = 1;int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail.");return;}int* temp = tmp; //用于临时数组中移动while (gap < n) //为什么gap<n,而不是gap<n/2 ?//确保最后一次归并囊括所有数据，这样就可以解决之前归并过程中因越界导致无法纳入归并范围的数据未处理的问题。{for (int i = 0; i < n; i += gap*2) //单趟循环{//定义两段区间int begin1 = i; int end1 = i + gap - 1;int begin2 = i + gap; int end2 = i + gap * 2 - 1;//修正1：这种修正适用于单趟排完后一次性拷贝或一组一组拷贝情况1：end1越界//if (end1 >= n)//{// end1 = n - 1;//}情况2：end1没越界，begin2越界//if (begin2 >= n)//{ //制造不存在的区间，使得其不能进入归并// begin2 = n;// end2 = n - 1;//}//if (end2 >= n)//{// end2 = n - 1;//}//修正2：这种修正适用于一组一组拷贝//情况1与情况2：直接跳过这组的排序，不拷贝if (end1 >= n || begin2 >= n){break; }//情况3：修正end2if (end2 >= n){end2 = n - 1;}printf("[%d, %d][%d, %d] ", begin1, end1, begin2, end2);//开始归并并拷贝到temp中while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){*(temp++) = a[begin1++];}else{*(temp++) = a[begin2++];}}while (begin1 <= end1){*(temp++) = a[begin1++];}while (begin2 <= end2){*(temp++) = a[begin2++];}//归并完成，开始拷贝回去//这是每排序完一组再拷贝memcpy(a + i, temp - (end2 - i + 1), sizeof(int) * (end2 - i + 1));}gap *= 2; //数据个数是2的倍数temp = tmp; //temp归位printf("\n");//这是单趟排完再拷贝，跟修正1匹配，不适用于修正2，不推荐使用//memcpy(a, temp, sizeof(int) * n);}
}
6. 计数排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
计数排序的特性总结：
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
- 稳定性：稳定
//非比较排序：计数排序、基数排序、桶排序
//计数排序
//1.统计每个数据出现的次数：创建count_a数组作为计数表，遍历一边原数组，O(N)
// 计数表的元素下标对应相对值，而计数表的元素值对应出现次数。
//2.排序：根据count_a进行原数组覆盖，遍历一边计数数组,O(range)
//如果计数数组接近N，那么时间复杂度就很小
//如果计数范围特别大，那么如何节省空间？ 找原数组最小值，将数组内每个数减去最小值，这样就可以缩小计数表的范围
//适用范围：该方法适合范围集中，且范围不大的整型数组排序，不适合范围分散或非整形的排序，如浮点数或字符数组
//采用相对映射可以排负数
//时间复杂度O(N + range),取决于range，空间复杂度也是。
void count_sort(int* a, int n)
{int min = a[0];int max = a[0];for (int i = 0; i < n; i++) // 找最大，最小值{if (min > a[i])min = a[i];if (max < a[i])max = a[i];}int range = max - min + 1;int* count_a = (int*)malloc(sizeof(int) * range);if (count_a == NULL){perror("malloc fail.");return;}for (int i = 0; i < range; i++) //初始化count_a{count_a[i] = 0;}for (int i = 0; i < n; i++) //对应下标增加次数{count_a[a[i] - min]++;}int* temp = a;for (int i = 0; i < range; i++) //遍历count_a，覆盖原数组{while (count_a[i]--){*(temp++) = i + min;}}free(count_a);
}
三、排序算法复杂度及其稳定性
总结一下：复杂度为O(N*logN)的排序只有归并排序稳定，复杂度为O(N^2)的排序只有选择排序不稳定。
最后，如有错误，请批评指正，谢谢。