前言排序就是使一组数据按照某种规则递增或递减排列起来的操作。是生活中应用最广泛的算法之一。包括多种排序算法今天我们介绍最常见的几种下面我默认都是用int数据排成升序作为演示。一、插入排序1. 直接插入排序直接插入排序是一种简单的插入排序法基本思想是把待排序的数据按照其大小逐个插入到一个已经排好序的有序序列中直到所有的记录都插入完为止得到一个新的有序序列。这种排序思想类比像我们玩扑克牌时一张张插入手牌。当插入第i个元素时前面的arr[0] arr[1] ... arr[i-1]已经是有序的了此时用arr[i]与这些数据进行比较找到正确的位置插入原位置及之后的元素后移一位。代码实现1234567891011121314151617voidInsertSort(vectorint arr){intn arr.size();for(inti 1; i n; i){inttmp arr[i];// 当前待插入元素intj i - 1;// 向前找比tmp大的元素大就往后移一位while(j 0 arr[j] tmp){arr[j 1] arr[j];j--;}arr[j 1] tmp;// 插入到正确位置}}测试复杂度分析时间复杂度O(n2)数组越接近有序时间效率越高空间复杂度O(1)2. 希尔排序希尔排序是直接插入排序的优化版本也叫 “缩小增量排序”。它的基本思想是先选定一个整数gap通常是gap n/3 1把待排序数据按照下标间隔gap分成各组如n10gap 4则下标0, 4, 8在同一组并对每一组内的数据进行插入排序然后gap gap/3 1再用新gap分成新组进行插入排序。当gap 1时就相当于直接插入排序了。举个直观的分析过程例子原数组[8 9 1 7 2 3 5 4 6 0]gap 10/3 1 4按 gap4 分组每组元素下标差为 4组 1[8, 2, 6] → 插入排序后 [2, 6, 8]组 2[9, 3, 0] → 插入排序后 [0, 3, 9]组 3[1, 5] → 插入排序后 [1, 5]组 4[7, 4] → 插入排序后 [4, 7]数组变为[2, 0, 1, 4, 6, 3, 5, 7, 8, 9]gap 4/3 1 2按 gap2 分组每组元素下标差为 2组 1[2, 1, 6, 5, 8] → 插入排序后 [1, 2, 5, 6, 8]组 2[0, 4, 3, 7, 9] → 插入排序后 [0, 3, 4, 7, 9]数组变为[1, 0, 2, 3, 5, 4, 6, 7, 8, 9]gap 2/3 1 1此时 gap1相当于对整个基本有序的数组做直接插入排序排序后最终结果[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]gap 1时都是预排序目的是让数据更接近有序。gap 1时数组已经接近有序了进行直接插入排序就会很快代码实现12345678910111213141516171819202122232425voidShellSort(vectorint arr){intn arr.size();intgap n;while(gap 1)// gap 1 时做预排序{gap gap / 3 1;// 直接遍历所有元素按gap做插入排序for(inti gap; i n; i){inttmp arr[i];// 当前待插入元素intj i - gap;// 同组的前一个元素下标// 向前找比tmp大的元素大则后移while(j 0 arr[j] tmp){arr[j gap] arr[j];j - gap;}arr[j gap] tmp;// 插入到正确位置}}}测试复杂度分析时间复杂度希尔排序的时间复杂度受gap的影响很难去计算通常介于O(n1.3)~O(n2)之间数组越接近有序时间效率越高。综合来说它的效率还是优于直接插入排序的。空间复杂度O(1)二、选择排序选择排序的基本思想是每一次从待排序元素中选出最小的元素放在已排好序列的起始位置直到全部待排序数据选择完毕。1. 直接选择排序直接选择排序就是按照上面的思路进行代码实现12345678910111213141516171819voidSelectSort(vectorint arr){intn arr.size();for(inti 0; i n - 1; i){intmin i;// min记录当前最小元素的下标// 找到[i1, n)中的最小元素for(intj i 1; j n; j){if(arr[j] arr[min]){min j;}}//将找到的最小位置交换到当前位置swap(arr[i], arr[min]);}}复杂度分析时间复杂度O(n2)实际中很少使用空间复杂度O(1)2. 堆排序堆排序是指利用“堆”这种数据结构设计的一种排序算法它是选择排序的一种利用堆来进行选择数据。以前我有一篇文章讲过了当时我是用C语言实现的在C中我们有了std::priority_queue而它的底层也是使用的堆或者STL的算法库中还有一个std::make_head可以直接在一段迭代器区间上建堆所以C中写堆排序可以直接利用它们了。