文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：冒泡排序
代码如下
1public class BubbleSort {
2 public static int[] bubbleSort(int[] arr) {
3 if (arr == null || arr.length < 2) {
4 return arr;
5 }
6 int n = arr.length;
7 for (int i = 0; i < n; i++) {
8 for (int j = 0; j < n -i - 1; j++) {
9 if (arr[j + 1] < arr[j]) {
10 int t = arr[j];
11 arr[j] = arr[j+1];
12 arr[j+1] = t;
13 }
14 }
15 }
16 return arr;
17 }
18)
性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、稳定排序 4、原地排序
优化一下冒泡排序的算法
假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时的数组已经是有序的了，我们无需再对剩余的元素重复比较下去了 。
代码如下：
1public class BubbleSort {
2 public static int[] bubbleSort(int[] arr) {
3 if (arr == null || arr.length < 2) {
4 return arr;
5 }
6 int n = arr.length;
7 for (int i = 0; i < n; i++) {
8 boolean flag = true;
9 for (int j = 0; j < n -i - 1; j++) {
10 if (arr[j + 1] < arr[j]) {
11 flag = false;
12 int t = arr[j];
13 arr[j] = arr[j+1];
14 arr[j+1] = t;
15 }
16 }
17 //一趟下来是否发生位置交换
18 if(false)
19 break;
20 }
21 return arr;
22 }
23}
4、希尔排序
希尔排序可以说是插入排序的一种变种 。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动 。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了 。
希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序 。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了 。
为方便理解我还准备了图片：
文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：希尔排序
代码如下
1public class ShellSort {
2 public static int[] shellSort(int arr[]) {
3 if (arr == null || arr.length < 2) return arr;
4 int n = arr.length;
5 // 对每组间隔为 h的分组进行排序，刚开始 h = n / 2;
6 for (int h = n / 2; h > 0; h /= 2) {
7 //对各个局部分组进行插入排序
8 for (int i = h; i < n; i++) {
9 // 将arr[i] 插入到所在分组的正确位置上
10 insertI(arr, h, i);
11 }
12 }
13 return arr;
14 }
15
16 /**
17 * 将arr[i]插入到所在分组的正确位置上
18 * arr[i]] 所在的分组为 ... arr[i-2*h],arr[i-h], arr[i+h] ...
19 */
20 private static void insertI(int[] arr, int h, int i) {
21 int temp = arr[i];
22 int k;
23 for (k = i - h; k > 0 && temp < arr[k]; k -= h) {
24 arr[k + h] = arr[k];
25 }
26 arr[k + h] = temp;
27 }
28}
需要注意的是，对各个分组进行插入的时候并不是先对一个组排序完了再来对另一个组排序，而是轮流对每个组进行排序 。
性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序
5、归并排序
将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组 。由于两个小的数组都是有序的，所以在合并的时候是很快的 。
通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来 。
为方便理解我还准备了动图：
文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：归并排序
代码如下：
1public class MergeSort {
2 // 归并排序
3 public static int[] mergeSort(int[] arr, int left, int right) {
【话不多说！程序员必学的十大算法】
推荐阅读
- 大厂高级程序员必备算法，看似简单的二分查找，您了解多少？
- 有哪些怼人的话不带脏字却超狠？
- 一个程序员的水平能差到什么程度,程序员水平难判断-程序员的6大等级,赶紧对号入座吧!-
- 程序员|《甄嬛传》中的经典台词，道出职场潜规则，一个比一个经典
- 三岁半男孩说话不清楚
- 和程序员谈恋爱是什么样的体验,程序员和程序员谈恋爱合适吗-
- 程序员|俄罗斯程序员开发 著名压缩软件7Zip被抵制：伪开源、还有后门
- 奥特曼图片奥特曼图片大全,奥特曼有哪些图片大全-
- 我很爱你的情话,最动人的情话不是我爱你而是-
- 程序员|不要盲目择校 选择合适自己的才重要