1.选择排序(了解)
算法思路:
每轮选取当前未排序的元素中最小的元素交换到未排序部分的最开头,经过若干步骤就能排序完整个数组。即:先选出最小的,然后选出第二小的,依次类推。
算法实现:
1 | package edu.sort; |
总结:
- 算法思想:
- 贪心算法:每次决策都选当前最优,当前最优则全局最优。但是这种思想不是任何时候都适用。
- 减治思想:外层循环每次都能排定一个元素,问题规模逐渐减小,直到全部解决。即大而化小,小而化无。
- 优点:交换次数最少。
复杂度分析:
- 时间复杂度:O(N2),N为数组长度。
- 空间复杂度:O(1),只使用到了常数个临时变量。
2.插入排序(熟悉)
算法思路:
每次将一个元素插入到一个有序的数组里,使之成为一个更长的有序数组,有限次操作之后,数组整体有序。
图片来自「力扣」第 147 题:对链表进行插入排序。
算法实现:
1 | package edu.sort; |
总结:
- 插入排序在“几乎有序”的数组和“短数组”中表现良好,因此在小区间内执行排序任务的时候可以使用插入排序。
- 由于我们的内层循环的判断条件是
nums[j-1] > temp
,所以在数组几乎有序的情况下,插入排序的时间复杂度可以达到O(N)。
复杂度分析:
- 时间复杂度:O(N2),N为数组长度。
- 空间复杂度:O(1),只使用到了常数个临时变量。
3.归并排序(重点)
算法思路:
- 基本思路:借助额外空间,合并两个有序数组,使之成为一个更长的有序数组。
- 算法思想:分治思想。
大佬建议:「归并排序」是理解「递归思想」的非常好的学习材料,大家可以通过理解:递归完成以后,合并两个有序数组的这一步骤,想清楚程序的执行流程。即「递归函数执行完成以后,我们还可以做点事情」。因此,「归并排序」我个人觉得非常重要,一定要掌握。
作者:liweiwei1419
链接:https://leetcode.cn/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/
算法实现:
1 | package edu.sort; |
总结:
- 将无序数组拆分,排序后再合并成大的有序数组。
复杂度分析:
- 时间复杂度:O(N log N),这里 NN 是数组的长度;
- 空间复杂度:O(N),辅助数组与输入数组规模相当。
4.冒泡排序
算法思路:
两两交换,⼤的放在后⾯,第⼀次排序后最⼤值已在数组末尾。因为两两交换,需要 n-1 趟排序(⽐如10个数,需要9趟排序)
算法实现:
1 | public class BubbleSort { |
复杂度分析:
- 时间复杂度:O(N2)
- 空间复杂度:O(1)
5.快速排序
算法思路:
数组中找⼀个元素(节点),⽐它⼩的放在节点的左边,⽐它⼤的放在节点右边。⼀趟下来,⽐节点⼩的在
左边,⽐节点⼤的在右边。不断执⾏这个操作….
算法实现:
1 | public class QuickSort { |
复杂度分析:
时间复杂度:O(N log N)
空间复杂度:O(logN),这里占用的空间主要来自递归函数的栈空间。