1.1 数组排序

图1 冒泡排序算法（数组）

public class BubbleSortArray {public static void main(String[] args) {BubbleSortArray sort = new BubbleSortArray();sort.sortByBubble(new int[]{4, 2, 1, 3});}public void sortByBubble(int[] nums){int n = nums.length; // 数组大小for (int i = n-1; i > 0; i--) { // 循环n-1次for (int j = 0; j < i; j++) {if(nums[j] > nums[j+1]) { // 最大的值放最后，依次两两交换int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;}}}// 输出结果for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(nums[i]);continue;}System.out.print(nums[i]+"->");}}
}

1.2 链表排序

图2 冒泡排序核心交换图

public class BubbleSortByLinkedList {public static void main(String[] args) {// 创建链表ListNode head = new ListNode();ListNode temp = new ListNode();temp = head;ListNode node4 = new ListNode(4);temp.next = node4;temp = temp.next;ListNode node2 = new ListNode(2);temp.next = node2;temp = temp.next;ListNode node1 = new ListNode(1);temp.next = node1;temp = temp.next;ListNode node3 = new ListNode(3);temp.next = node3;temp = temp.next;BubbleSortByLinkedList sort = new BubbleSortByLinkedList();sort.sortByLinkedList(head.next);}public void sortByLinkedList(ListNode head){ListNode dummy = new ListNode();dummy.next = head;ListNode temp = head;int n = 0; // 统计链表节点个数while (temp != null){n++;temp = temp.next;}for (int i = 0; i < n-1; i++) {int num = n-i-1; // 统计内循环需要多少次ListNode pre = dummy; // 最前一个节点ListNode p = pre.next; // 第一个内循环节点ListNode q = p.next; // 第二个内循环节点for (int j = 0; j < num; j++) {if(p.val > q.val){ // 前一个比后一个大，两两交换p.next = q.next;q.next = p;pre.next = q;}// 下一次内循环指针指向pre = pre.next;p = pre.next;q = p.next;}}// 输出链表dummy = dummy.next;for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(dummy.val);continue;}System.out.print(dummy.val+"->");dummy = dummy.next;}}
}// 链表节点元素
class ListNode{ListNode next;int val;ListNode(){}ListNode(int val){this.val = val;}
}

2. 插入排序

2.1 数组排序

算法核心：
首先，每一轮都假定待插入元素之前的数组元素是排好序的（算法也的确如此，没问题）；
其次，找到大于待插入元素的下标；
紧接着，将待插入位置至待插入元素之前的上一个下标都后移一位；
最后，将待插入元素插入到找到的下标位置。
时间复杂度为 $\text{[math]}$
空间复杂度为 $\text{[math]}$
是否稳定：稳定

public class InsertSortByArray {public static void main(String[] args) {InsertSortByArray sort = new InsertSortByArray();sort.sortByInsert(new int[]{4, 2, 1, 3});}public void sortByInsert(int[] nums){// 统计数组元素个数int n = nums.length;for (int i = 1; i < n; i++) {int insertNum = nums[i];int j = 0;while (j<i && nums[j] < insertNum){ // 寻找比插入元素大的下标j++;}for (int k = i-1; k >= j; k--) { // 插入元素的后面元素都后移nums[k+1] = nums[k];}nums[j] = insertNum; // 插入元素}// 输出结果for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(nums[i]);continue;}System.out.print(nums[i]+"->");}}}

2.2 链表排序

算法核心：
添加虚拟节点dummy，有利于找到修改节点的上一个节点，做移除操作。
接下来只需三步：
1. 定位待插入节点和待插入节点的前一个节点；
2. 定位大于待插入节点和大于待插入节点的前一个节点；
3. 移除待插入节点，将待插入节点插入到相应位置。

public class InsertByLinkedList {public static void main(String[] args) {// 创建链表ListNode head = new ListNode();ListNode temp = new ListNode();temp = head;ListNode node4 = new ListNode(4);temp.next = node4;temp = temp.next;ListNode node2 = new ListNode(2);temp.next = node2;temp = temp.next;ListNode node1 = new ListNode(1);temp.next = node1;temp = temp.next;ListNode node3 = new ListNode(3);temp.next = node3;temp = temp.next;InsertByLinkedList sort = new InsertByLinkedList();sort.sortByLinkedList(head.next);}public void sortByLinkedList(ListNode head) {// 统计链表节点个数int n = 0;ListNode temp = head;while (temp != null){n++;temp = temp.next;}ListNode dummy = new ListNode();dummy.next = head;for (int i = 2; i <= n; i++) {int j = 1;ListNode pre = dummy; // 扫面链表节点的前一个节点ListNode p = pre.next; // 扫描链表节点ListNode pre_q = dummy; // 待插入节点的上一个节点ListNode q = dummy.next; // 待插入节点while (j < i){ j++;pre_q = pre_q.next;q = q.next;}pre_q.next = q.next; // 移除待插入节点while (p != q && p.val <= q.val) { // 查找大于待插入节点的节点位置pre = pre.next;p = p.next;}// 插入待插入节点q.next = p; pre.next = q;}// 输出链表dummy = dummy.next;for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(dummy.val);continue;}System.out.print(dummy.val+"->");dummy = dummy.next;}}// 链表节点定义static class ListNode{ListNode next;int val;ListNode(){}ListNode(int val){this.val = val;}}}