内容参考此链接，感谢🙏。
一、插入排序
1. 直接插入排序
/**
* 插入排序
*
* 1. 从第一个元素开始，该元素可以认为已经被排序
* 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 5. 将新元素插入到该位置后
* 6. 重复步骤2~5
* @param arr 待排序数组
*/
public static void insertionSort(int[] arr){
for(int i=1;i<arr.length;i++){
int temp = arr[i]; // 记录一下这个要排序的值
for(int j=i;j>=0;j--){
if(j>0&&arr[j-1]>temp){
arr[j]=arr[j-1];
}else{ // 要么到头了，就是j=0，要么就是arr[j-1]<temp
arr[j]=temp;
break; // 当前这个temp已经放进去了，那就退出最里层的for循环
}
}
}
}
2. 希尔排序
/**
* 希尔排序
*
* 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
* 2. 按增量序列个数k，对序列进行k趟排序；
* 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
* @param arr 待排序数组
*/
public class ShellSort {
public static void main(String[] args)
{
int[] ins = {2,3,5,1,23,6,78,34,23,4,5,78,34,65,32,65,76,32,76,1,9};
int[] ins2 = shellSort(ins);
for(int in: ins2){
System.out.print(in+" ");
}
}
public static int[] shellSort(int[] arr){
int gap = arr.length/2;
for(;gap>0;gap/=2){ // gap不断缩小，直到gap=1
for(int i=0;i<gap;i++){
for(int j=i+gap;j<arr.length;j+=gap){
int temp = arr[j];
int k = j - gap;
while(k>=0&&arr[k]>temp){
arr[k+gap] = arr[k];
k-=gap;
}
arr[k + gap] = temp;
}
}
}
return arr;
}
}
二、选择排序
1. 简单选择排序/直接选择排序
/**
* 选择排序
*
* 1. 从待排序序列中，找到关键字最小的元素；
* 2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
* 3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。
* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
* @param arr 待排序数组
*/
public static void selectionSort(int[] arr){
for(int i=0;i<arr.length;i++){
int min = i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[min]){
min=j;
}
}
if(min!=i){
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
2. 堆排序（不想看了 想吐了🤮）
/**
* 堆排序
*
* 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
* 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n?1]和有序区K[n], 且满足K[1..n?1].keys?K[n].key
* 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n?1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
* @param arr 待排序数组
*/
public static void heapSort(int[] arr){
for(int i = arr.length; i > 0; i--){
max_heapify(arr, i);
int temp = arr[0]; //堆顶元素(第一个元素)与Kn交换
arr[0] = arr[i-1];
arr[i-1] = temp;
}
}
private static void max_heapify(int[] arr, int limit){
if(arr.length <= 0 || arr.length < limit) return;
int parentIdx = limit / 2;
for(; parentIdx >= 0; parentIdx--){
if(parentIdx * 2 >= limit){
continue;
}
int left = parentIdx * 2; //左子节点位置
int right = (left + 1) >= limit ? left : (left + 1); //右子节点位置，如果没有右节点，默认为左节点位置
int maxChildId = arr[left] >= arr[right] ? left : right;
if(arr[maxChildId] > arr[parentIdx]){ //交换父节点与左右子节点中的最大值
int temp = arr[parentIdx];
arr[parentIdx] = arr[maxChildId];
arr[maxChildId] = temp;
}
}
System.out.println("Max_Heapify: " + Arrays.toString(arr));
}
三、交换排序
1. 冒泡排序
/**
* 冒泡排序
*
* 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
* 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了 n 个数据的排序工作。
**/
public class BubbleSort {
public void bubbleSort(Integer[] arr, int n) {
if (n <= 1) return; //如果只有一个元素就不用排序了
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) { //此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，
// 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少
if (arr[j] > arr[j + 1]) { //即这两个相邻的数是逆序的，交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag) break;//没有数据交换，数组已经有序，退出排序
}
}
public static void main(String[] args) {
Integer arr[] = {2, 4, 7, 6, 8, 5, 9};
SortUtil.show(arr);
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.bubbleSort(arr, arr.length);
SortUtil.show(arr);
}
}