很多人在学习数据结构时被排序所困扰，以下是我整理的五种排序总结（折半插入排序、冒泡排序、快速排序、简单选择排序、堆排序），包括代码、时间复杂度、应用场景等。
// 折半插入排序函数 ?
void insert_sort(int* array , int n){ ?
? ? int temp; // 用于暂存需要插入的元素 ?
? ? ?for(int i = 1; i < n; i++){ // 从第二个元素开始循环 ?
? ? ? ? ?int low = 0; // 左边界初始化为0 ?
? ? ? ? ?int hight = i-1; // 右边界初始化为当前元素的前一个位置 ?
? ? ? ? ?temp = array[i]; // 暂存当前元素的值 ?
? ? ? ? ?while(hight>=low){ // 当左边界小于或等于右边界时进行查找 ?
? ? ? ? ? ? ?int mid = ( low + hight ) / 2; // 计算中间位置 ?
? ? ? ? ? ? ?if (array[mid] > temp){ // 如果中间位置的元素大于要插入的元素 ?
? ? ? ? ? ? ? ? ? ? hight = mid - 1; // 将右边界缩小到中间位置的左边 ?
? ? ? ? ? ? ?}else{ ?
? ? ? ? ? ? ? ? ?low = mid + 1; // 如果中间位置的元素小于或等于要插入的元素，将左边界扩大到中间位置的右边 ?
? ? ? ? ? ? ? } ?
? ? ? ? ? } ?
? ? ? ? ? // 将找到的位置及其右侧的所有元素向右移动一位，为要插入的元素腾出空间 ?
? ? ? ? ? for (int j = i-1; j > hight; j--) { ?
? ? ? ? ? ? ? array[j+1] = array[j]; ?
? ? ? ? ? } ?
? ? ? ? ? // 将找到的位置赋值给要插入的元素 ?
? ? ? ? ? array[hight+1] = temp; ?
? ? } ?
}// 冒泡排序函数 ?
void bobber_sort(int* array , int n){ ?
? ? int temp; // 用于交换元素的临时变量 ?
? ? for(int i=0;i<n;i++){ // 外层循环控制排序的轮数 ?
? ? ? ? for(int j=0;j<n-i-1;j++){ // 内层循环控制每轮排序的比较次数 ?
? ? ? ? ? ? if(array[j]>array[j+1]){ // 如果当前元素大于其相邻的下一个元素 ?
? ? ? ? ? ? ? ? temp=array[j]; // 临时存储当前元素的值 ?
?? ? ? ? ? ? ? array[j]=array[j+1]; // 将当前元素的值设置为下一个元素的值 ?
? ? ? ? ? ? ? ? array[j+1]=temp; // 将下一个元素的值设置为临时存储的值，完成交换 ?
? ? ? ? ?? } ?
??? ? } ?
??? ? } ?
? }
// 快速排序函数 ?
void quick_sort(int* array , int low , int high){ ?
? ? int i = low, j = high; // 初始化两个指针，i指向数组的起始位置，j指向数组的末尾位置 ?
? ? int key = array[i]; // 选择数组的第一个元素作为基准值 ?
?
? ? while (i < j){ // 当两个指针没有相遇时，继续循环 ?
? ? ? ? while(i < j && array[j] >= key){ // 从右向左移动j指针，直到找到一个小于基准值的元素或j指针已经到了数组的起始位置 ?
? ? ? ? ? ? j--; ?
? ? ? ? } ?
? ? ? ? array[i] = array[j]; // 将找到的元素复制到i指针的位置 ?
?
? ? ? ? while(i < j && array[i] <= key){ // 从左向右移动i指针，直到找到一个大于基准值的元素或i指针已经到了数组的末尾位置 ?
? ? ? ? ? ? i++; ?
? ? ? ? } ?
? ? ? ? array[j] = array[i]; // 将找到的元素复制到j指针的位置 ?
? ? } ?
? ? array[i] = key; // 将基准值放到正确的位置上 ?
?
? ? if (i-1 > low) { // 如果基准值左边的元素个数大于1，递归进行排序 ?
? ? ? ? quick_sort(array, low, i-1); ?
? ? } ?
? ? if (i+1 < high){ // 如果基准值右边的元素个数大于1，递归进行排序 ?
? ? ? ? quick_sort(array, i+1, high); ?
? ? } ?
}
// 简单选择排序函数 ?
void select_sort(int* array , int n){ ?
? ? int i, j; // 循环控制变量 ?
? ? int min; // 待排序数组中最小值的下标 ?
? ? int tmp; // 临时变量，用于交换元素 ?
?
? ? for (i = 0; i < n - 1; ++i){ // 外层循环，控制排序的轮数，从0到n-2 ?
? ? ? ? min = i; // 假设当前位置的元素是最小的 ?
?
? ? ? ? // 内层循环，从当前位置的下一个元素开始，查找最小值的位置 ?
? ? ? ? for (j = i + 1; j < n; ++j){ ?
? ? ? ? ? ? if (array[j] < array[min]){ ?
? ? ? ? ? ? ? ? min = j; // 更新最小值的位置 ?
? ? ? ? ? ? } ?
? ? ? ? } ?
?
? ? ? ? // 如果找到了更小的值，则交换当前位置和最小值位置的元素 ?
? ? ? ? tmp = array[i]; // 临时存储当前位置的元素值 ?
? ? ? ? array[i] = array[min]; // 将最小值位置的元素值赋给当前位置 ?
? ? ? ? array[min] = tmp; // 将临时存储的值赋给最小值位置 ?
? ? } ?
} // 简单选择排序结束void swap(int* a, int* b) {//交换函数
? ? int tmp = *a;
? ? *a = *b;
? ? *b = tmp;
}
void maxheap_sort(int a[], int start,int end) {
? ? int c = start; // 当前（current）节点的位置
? ? int l = 2 * c + 1; // 左（left）孩子的位置
? ? int tmp = a[c]; // 当前（current）节点的大小
? ? for (; l <= end; c = l, l = 2 * l + 1) {
? ? ? ? // “l”是左孩子，“l+1”是右孩子
? ? ? ? if (l < end && a[l] < a[l + 1]) {
? ? ? ? ? ? l++; // 左右两个孩子中选择较大者，即m_heap[l+1]
? ? ? ? }
? ? ? ? if (tmp >= a[l]) {
? ? ? ? ? ? break; // 调整结束
? ? ? ? }
? ? ? ? else {// 交换值
? ? ? ? ? ? a[c] = a[l];
? ? ? ? ? ? a[l] = tmp;
? ? ? ? }
? ? }
}
void heap_sort(int a[], int n) {
? ? int i;
? ? // 从（n/2-1）--> 0 逐次遍历。遍历之后，得到的数组实际上是一个（最大）二叉堆
? ? for (i = n / 2 - 1; i >= 0; i--) {
? ? ? ? maxheap_sort(a, i, n - 1);
? ? }
? ? // 从最后一个元素开始对序列进行调整，不断地缩小调整的范围直到第一个元素
? ? for (i = n - 1; i > 0; i--) {
? ? ? ? // 交换a[0]和a[i]。交换后，a[i]是a[0..i]中最大的。
? ? ? ? swap(&a[0], &a[i]);
? ? ? ? // 调整a[0..i-1]，使得a[0..i-1]仍然是一个最大堆。
? ? ? ? // 即，保证a[i-1]是a[0..i-1]中的最大值。
? ? ? ? maxheap_sort(a, 0, i - 1);
? ? }
}