文章目录
一、插入排序（一）、什么是插入排序（二）、图例（三）、Java代码 二、希尔排序（一）、什么是希尔排序（二）、图例（三）、Java代码 三、冒泡排序（一）、什么是冒泡排序（二）、图例（三）、Java代码 四、源码一、插入排序
（一）、什么是插入排序
插入排序 ( InsertionSort )，一般也被称为直接插入排序。函数命名：insertionSort原理：1. 将一个记录插入到“已经排好序”的有序表中。2. 从而形成一个新的、数据项增 1 的“有序表”。
算法：
1. 两个for循环2. 外层循环：对除了第一个元素之外的所有元素3. 内层循环：对当前元素前面有序表进行待插入位置查找，并进行移动
性能分析：
1. 时间复杂度 O(n^2)2. 空间复杂度 O(1)3. 当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次4. 最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)
（二）、图例
监视哨的目的：避免数组下标出界（三）、Java代码
insertionSort/*** 直接插入排序* * @param arrs 待排序数组*/public void insertionSort(int[] arrs) {int n = arrs.length;for (int i = 0; i < n; i++) {// 1. 寻找元素 arrs[i] 合适的插入位置for (int j = i; j > 0; j--) {// 2. 找到合适位置就交换if (arrs[j] < arrs[j - 1]) // 决定升降序swap(arrs, j, j - 1);elsebreak;}}} // insertionSort
swap
/*** 数组两个位置交换* * @param arrs* @param i* @param j*/private void swap(int[] arrs, int i, int j) {int temp = arrs[i];arrs[i] = arrs[j];arrs[j] = temp;} // swap
testOfInsertionSort
public static void testOfInsertionSort() {int[] arrs = {5, 11, 1, 0, -1, 15, 20, 100, -99 };Sort sort = new Sort();sort.insertionSort(arrs);for (int i = 0; i < arrs.length; i++) {System.out.print(arrs[i]);System.out.print(" ");}}
输出样例
直接插入排序:-99 -1 0 1 5 11 15 20 100
二、希尔排序
（一）、什么是希尔排序
希尔排序，也称递减增量排序算法。希尔排序比直接插入排序更高效：直接插入排序每次只能将数据移动一位希尔排序是非稳定排序算法：简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前，这是排序的稳定性。原理：1. 先将整个待排序的序列分割成为若干子序列。2. 对子序列分别进行直接插入排序。3. 待每个子序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
算法：
1. 确定一个增量k2. 对序列进行 k 趟排序3. 每趟排序，看情况交不交换（升降）4. 仅增量因子为 1 时，排序完成
性能：
1. 时间复杂度：O(n^1.5)
（二）、图例
第一趟：增量为5第二趟：增量为3… …直到增量为1（三）、Java代码
-shellSort
/*** 希尔排序* * @param arrs*/public void shellSort(int[] arrs) {int n = arrs.length;// 1. 以n/2为间隔（增量）,直到增量为1for (int step = n / 2; step >= 1; step /= 2) {// 2. 直接插入排序for (int i = step; i < n; i++) {// j每次递减是减少step那么多for(int j=i; j>step-1; j-=step) {if(arrs[j-step] > arrs[j])swap(arrs, j-step, j);elsebreak;}}}} // shellSort
testOfShellSort
/*** 测试希尔排序*/public static void testOfShellSort() {int[] arrs = {5, 11, 1, 0, -1, 15, 20, 100, -99 };Sort sort = new Sort();sort.shellSort(arrs);for (int i = 0; i < arrs.length; i++) {System.out.print(arrs[i]);System.out.print(" ");}}
输出样例
希尔排序:-99 -1 0 1 5 11 15 20 100
三、冒泡排序
（一）、什么是冒泡排序
这个用的最多，又简单，主要是原理。简单了解一下原理。算法简单。冒泡排序（Bubble Sort）。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。算法：1. 比较相邻的元素。如果第一个比第二个大，就交换。2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。3. 针对所有的元素重复以上的步骤，除了最后一个。4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
性能：
1. 时间复杂度：O(n^2)
（二）、图例
（三）、Java代码
bubbleSort/*** 冒泡排序* * 不正宗，但简单呀* @param arrs*/public void bubbleSort(int[] arrs) {int n = arrs.length;for(int i=0; i<n; i++) {for(int j=0; j<n-1-i; j++) {if(arrs[j] > arrs[j+1]) {swap(arrs, j, j+1);}}}} // bubbleSort
testOfBubbleSort
/*** 测试冒泡排序*/public static void testOfBubbleSort() {int[] arrs = {5, 11, 1, 0, -1, 15, 20, 100, -99 };Sort sort = new Sort();sort.bubbleSort(arrs);for (int i = 0; i < arrs.length; i++) {System.out.print(arrs[i]);System.out.print(" ");}}
输出样例
冒泡排序:-99 -1 0 1 5 11 15 20 100
四、源码
package sort;public class Sort {/*** 直接插入排序* * @param arrs 待排序数组*/public void insertionSort(int[] arrs) {int n = arrs.length;for (int i = 0; i < n; i++) {// 1. 寻找元素 arrs[i] 合适的插入位置for (int j = i; j > 0; j--) {// 2. 找到合适位置就交换if (arrs[j] < arrs[j - 1]) // 决定升降序swap(arrs, j, j - 1);elsebreak;}}} // insertionSort/*** 数组两个位置交换* * @param arrs* @param i* @param j*/private void swap(int[] arrs, int i, int j) {int temp = arrs[i];arrs[i] = arrs[j];arrs[j] = temp;} // swap/*** 测试直接插入排序*/public static void testOfInsertionSort() {int[] arrs = {5, 11, 1, 0, -1, 15, 20, 100, -99 };Sort sort = new Sort();sort.insertionSort(arrs);for (int i = 0; i < arrs.length; i++) {System.out.print(arrs[i]);System.out.print(" ");}}/*** 希尔排序* * @param arrs*/public void shellSort(int[] arrs) {int n = arrs.length;// 1. 以n/2为间隔（增量）,直到增量为1for (int step = n / 2; step >= 1; step /= 2) {// 2. 直接插入排序for (int i = step; i < n; i++) {// j每次递减是减少step那么多for (int j = i; j > step - 1; j -= step) {if (arrs[j - step] > arrs[j])swap(arrs, j - step, j);elsebreak;}}}} // shellSort/*** 测试希尔排序*/public static void testOfShellSort() {int[] arrs = {5, 11, 1, 0, -1, 15, 20, 100, -99 };Sort sort = new Sort();sort.shellSort(arrs);for (int i = 0; i < arrs.length; i++) {System.out.print(arrs[i]);System.out.print(" ");}}/*** 冒泡排序* * @param arrs*/public void bubbleSort(int[] arrs) {int n = arrs.length;for (int i = 0; i < n; i++) {for (int j = 0; j < n - 1 - i; j++) {if (arrs[j] > arrs[j + 1]) {swap(arrs, j, j + 1);}}}} // bubbleSort/*** 测试冒泡排序*/public static void testOfBubbleSort() {int[] arrs = {5, 11, 1, 0, -1, 15, 20, 100, -99 };Sort sort = new Sort();sort.bubbleSort(arrs);for (int i = 0; i < arrs.length; i++) {System.out.print(arrs[i]);System.out.print(" ");}}public static void main(String[] args) {System.out.println("\r\n直接插入排序:");testOfInsertionSort();System.out.println("\r\n希尔排序:");testOfShellSort();System.out.println("\r\n冒泡排序:");testOfBubbleSort();}}
