【算法】8种排序基本概念冒泡排序从头开始

来源：CSDN 时间：2023-03-17 10:37:06

(资料图片)

冒泡排序

从头开始，两两依次比较，直到找出这组数据中最大的，放在最后面，重复此过程，直到有序时间复杂度：o(n^2) 空间复杂度：o(1) 稳定性：稳定优点：简单，易实现，不需要额外空间缺点： `效率低

选择排序：从头开始，依次找最小的，放在第一个，直到有序时间复杂度：o(n^2) 空间复杂度：o(1) 稳定性：不稳定优点：表现最稳定，时间复杂度永远o(n^2),不需要额外空间缺点：稳定性上讲，不稳定，效率低

插入排序：从头开始，不断地将当前数据插入到之前排好的数据中，直到最后一个时间复杂度：o(n^2) 空间复杂度：o(1) 稳定性：稳定优点：效率略高于选择和冒泡，稳定缺点：效率不高

希尔排序：将一组数据分成若干组，每个组中第一个元素与第二个元素相差“增量”个元素，对每个组进行插入排序，然后逐渐减小增量，分小组，直到增量为1（只有一个组）。时间复杂度：o(nlogn) 空间复杂度：o(1) 稳定性：不稳定优点：效率高于三种简单排序，不需要额外空间缺点：不稳定

快速排序：从一组数据中找出一个基准，然后从后向前找比这个基准小的，放在基准位置，然后再从前向后找比基准大的，放在刚刚那个数字的位置，循环此过程，直到基准找到合适的位置，使基准前面的数字小于基准，基准后面的数字大于基准。接着换一个基准重复此方法,直到数列有序。时间复杂度：o(nlogn) 空间复杂度：o(logn) 稳定性：不稳定优点：排序速度最快

归并排序：(二路归并排序)将一个长度为n的数列，两两分组，组的个数>=2，对每个组内排序；再将两个组合并，排序，合并，排序，直到整个数列有序。时间复杂度：o(nlogn) 空间复杂度：o(n) 稳定性：稳定

堆排序：大顶堆：每个节点的值都大于其左右孩子将一组数维护成大顶堆，找出堆顶元素拿走（交换堆顶元素和堆底元素，堆的元素个数减一），重新维护成一个大顶堆，重复操作，直到数列有序时间复杂度：o(nlogn) 空间复杂度：o(n) 稳定性：不稳定

基数排序：将一组数按个位元素分别放到0~9（十个桶）中，然后按十个桶的顺序取出（先去0号桶，再取1号桶…）,然后按十位元素分十个桶，将数字按十位元素再次放入，再次取出，直到数列有序。时间复杂度：o(n*k) k:桶的个数空间复杂度：o(n+k) 稳定性：稳定缺点：不能对小数排序，只针对整数

责任编辑：

标签：

上一篇：【报资讯】什么是操作系统？Windows、Mac、Unix、Linux什么是iOS？
下一篇：最后一页

【算法】8种排序基本概念 冒泡排序从头开始

【算法】8种排序基本概念冒泡排序从头开始