冒泡排序
冒泡排序的基本思想
- 一轮循环一定会将最大的元素排序到指定的位置
- 每次都比较相邻元素。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
算法实现
public class BubbleSort { public static <E extends Comparable<E>> void sort(E[] arr) { for(int i = 0; i < arr.length; i++) { for(int j = 0; j < arr.length - 1 - i; j++) { if(arr[j].compareTo(arr[j + 1]) > 0) { swap(arr, j, j + 1); } } } } public static <E extends Comparable<E>> void swap(E[] arr, int l, int r) { E temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } }
算法优化
当对于有序数组时，我们可以提前终止比较
因为在比较第一个元素的时候，就已经可以确定该数组是有序的，所以就可以提前终止了。
- 添加一个判断的变量。
public static <E extends Comparable<E>> void sort2(E[] arr) { for(int i = 0; i < arr.length; i++) { boolean isWrap = false; for(int j = 0; j < arr.length - 1 - i; j++) { if(arr[j].compareTo(arr[j + 1]) > 0) { swap(arr, j, j + 1); isWrap = true; } } if(!isWrap) { // 一轮循环后，没有元素交换位置，那么将说明该数组有序。 break; } } }
部分有序时，不需要比较后面的元素了。
网络异常，图片无法展示
|
我们知道外层循环变量是表示是指当前已经排序好的元素的个数。所以我们可以控制外层循环变量，来控制比较的位置。
public static <E extends Comparable<E>> void sort3(E[] arr) { for(int i = 0; i < arr.length;) { int lastIndex = 0; for(int j = 0; j < arr.length - 1 - i; j++) { if(arr[j].compareTo(arr[j + 1]) > 0) { swap(arr, j, j + 1); lastIndex = j + 1; // 这个表示排序好的位置 } } i = arr.length - lastIndex; // 决定下次比较的元素到达的位置 } }
希尔排序
就是将数组分组，然后使用插入排序。
不断让数组元素有序。通过将元素设置成更小的元素，让其有序，最后当间距为1。
网络异常，图片无法展示
|
public class ShellSort { public static <E extends Comparable<E>> void sort(E[] arr) { int h = arr.length / 2; // 表示间隔多少的元素组成一个数组进行插入排序 while (h >= 1) { // 表示直到间隔为1时，为最后一次数组的插入排序 for(int start = 0; start < h; start++) { // 表示处理多少个子数组。 h即可表示拆分为多少个数组 // 进行插入排序, [start, start + h, start + 2h ... start + nh]; for(int i = start + h; i < arr.length; i += h) { // 注意这里开始的下标是子数组的第二个元素，因为第一个元素前面没有元素了 E cur = arr[i]; int j; for(j = i; j - h >= 0; j -= h) { if(cur.compareTo(arr[j - h]) < 0) { // 当前比较的值小于当前值将向右移一位 arr[j] = arr[j - h]; } } arr[j] = cur; } } h /= 2; } } }
简化希尔排序的写法
上面我们可以看出，内层循环实现了三层for循环的嵌套，比较麻烦。因为他是每次只去比较每个子数组。
但是我们可以依次处理元素，只不过需要偏移h个元素查看交换条件而已。
public static <E extends Comparable<E>> void sort2(E[] arr) { int h = arr.length / 2; // 表示间隔多少的元素组成一个数组进行插入排序 while (h >= 1) { // 表示直到间隔为1时，为最后一次数组的插入排序 // 进行插入排序, [start, start + h, start + 2h ... start + nh]; for(int i = h; i < arr.length; i += h) { // 注意这里开始的下标是子数组的第二个元素，因为第一个元素前面没有元素了 E cur = arr[i]; int j; for(j = i; j - h >= 0; j -= h) { if(cur.compareTo(arr[j - h]) < 0) { // 当前比较的值小于当前值将向右移一位 arr[j] = arr[j - h]; } } arr[j] = cur; } h /= 2; } }
复杂度分析
网络异常，图片无法展示
|
网络异常，图片无法展示
|
通过步长序列，来优化希尔算法
// 步长序列 public static <E extends Comparable<E>> void sort3(E[] arr) { int h = 1; while(h < arr.length) { // 当不满足这个条件时，即为h的初始取值。 h = h * 3 + 1; // [4, 13, 40, 121, ...] } while (h >= 1) { // 表示直到间隔为1时，为最后一次数组的插入排序 // 进行插入排序, [start, start + h, start + 2h ... start + nh]; for(int i = h; i < arr.length; i ++) { // 注意这里开始的下标是子数组的第二个元素，因为第一个元素前面没有元素了 E cur = arr[i]; int j; for(j = i; j - h >= 0; j -= h) { if(cur.compareTo(arr[j - h]) < 0) { // 当前比较的值小于当前值将向右移一位 arr[j] = arr[j - h]; } } arr[j] = cur; } h /= 3; } }
基于比较的选择排序算法总结
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
排序算法的稳定性
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
基本排序算法
- 选择排序是不稳定的。
- 插入排序是稳定的。每次都是比较相邻的元素，所以不会出现元素的跳跃。
- 希尔排序是不稳定的。
- 冒泡排序是稳定的。每次都是比较相邻的元素，所以不会出现元素的跳跃。高级排序算法
- 堆排序不稳定。
- 快速排序不稳定。
- 归并排序稳定。
