排序 冒泡排序 优缺点、复杂度 稳定,平均/最坏时间复杂度 O(n²),元素基本有序时最好时间复杂度 O(n),空间复杂度 O(1) 步骤 从头开始,依次比较数组中相邻的2个元素,如果前面的数比后面的数大,则交换位置每进行一轮比较,都会把数组中最大的元素放到最后面针对 n 个元素重复以上步骤 n -1 次排序完毕 选择排序 优缺点、复杂度 不稳定,时间复杂度 O(n²),空间复杂度 O(1) 步骤 将第一个值与全员比较,找到最小的那个值放在首位排除第一个值,剩下的值重复步骤1,直到所有元素排序完毕 插入排序 优缺点、复杂度 稳定,平均/最差时间复杂度 O(n²),元素基本有序时最好时间复杂度 O(n),空间复杂度 O(1) 步骤 将第一个元素作为有序数组下一个元素从后遍历并插入到有序数组中,组成有序数组重复步骤2,直到排序完毕 快速排序 优缺点、复杂度 不稳定,平均/最好时间复杂度 O(nlogn),元素基本有序时最坏时间复杂度O(n²),空间复杂度 O(logn) 步骤 从数列中取出一个数作为基准数分区:将比它大的数全放到它的右边,小于或等于它的数全放到它的左边再对左右区间重复第二步,直到各区间只有一个数 堆排序 优缺点、复杂度 不稳定,时间复杂度 O(nlogn),空间复杂度 O(1) 原理 堆:近似完全二叉树的结构,堆中某个节点值总是不大于或者不小于其父节点的值根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆 步骤 将排序元素组成大根堆或小根堆取出根节点,将剩下元素再组成大根堆或小根堆重复步骤2,直到元素为1