排序概念和思路已在注釋中寫明唯绍，此處不贅述。
package sort;
/**
* @Author Seth
* @Date 2021/9/7
*/
public class Sort {
public static void main(String[] args) {
int[] arr = {2,1,6,7,4,8,0};
SortUtil.printArr(arr);
insertionSort(arr);
SortUtil.printArr(arr);
}
/**
* 插入排序
* 給定一個(gè)數(shù)組arr,長(zhǎng)度為N（N > 2）,整體思路是先保證
* 索引0~索引0位置有序枝誊、
* 索引0~索引1位置有序况芒、
* 索引0~索引2位置有序、
* 索引0~索引3位置有序叶撒、
* ...
* 索引0~索引N-1位置有序
*
* 操作步驟:
* 1绝骚、保證索引0~索引0位置有序，相同位置一定有序祠够，不需要操作
* 2压汪、索引0~索引1位置有序，比較arr[0],arr[1],如果arr[1] < arr[0]古瓤，交換arr[0]和arr[1]的位置止剖；
* 3腺阳、索引0~索引2位置有序，比較arr[1],arr[2],如果arr[2] < arr[1]穿香，交換arr[1]和arr[2]的位置亭引；比較arr[0],arr[1],如果arr[1] < arr[0]，交換arr[0]和arr[1]的位置皮获；
* 4焙蚓、索引0~索引3位置有序，比較arr[2],arr[3],如果arr[3] < arr[2]洒宝，交換arr[2]和arr[3]的位置主届；比較arr[1],arr[2],如果arr[2] < arr[1]，交換arr[1]和arr[2]的位置待德；比較arr[0],arr[1],如果arr[1] < arr[0]君丁，交換arr[0]和arr[1]的位置；
* ...
* N将宪、索引0~索引N-1位置有序绘闷，比較arr[N-2],arr[N-1],如果arr[N-1] < arr[N-2]，交換arr[N-1]和arr[N-2]的位置较坛；比較arr[N-3],arr[N-2],如果arr[N-2] < arr[N-3]印蔗，交換arr[N-2]和arr[N-3]的位置.....比較arr[0],arr[1],如果arr[1] < arr[0]，交換arr[0]和arr[1]的位置丑勤；
*
* @param arr 待排序數(shù)組
*/
public static void insertionSort(int[] arr){
// 先處理邊界
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
for (int i = 0; i < N; i++) {
for (int j = i; j - 1 >= 0 && arr[j] < arr[j-1]; j--) {
SortUtil.swap(arr, j, j - 1);
}
}
}
/**
* 冒泡排序
* 倒一杯水在玻璃杯里华嘹，我們都看見過，杯中的水會(huì)有泡泡向上浮起法竞。冒泡排序的過程跟這個(gè)過程相似耙厚，
* 給定一個(gè)數(shù)組arr，相鄰索引之間兩兩比較岔霸，將更大的數(shù)字向后移動(dòng)薛躬，這樣第一次比較之后數(shù)組長(zhǎng)度N-1的位置一定是最大的數(shù)字；
* 再兩兩比較呆细，到數(shù)組N-2的位置型宝，這樣N-2一定是第二大的數(shù)字，重復(fù)這個(gè)步驟即可完成冒泡排序絮爷。
*
* 操作步驟:
* 1. 比較索引0趴酣，1位置的數(shù)字，如果arr[0]>arr[1},交換arr[0]和arr[1]的位置,否則不交換位置坑夯；比較索引1,2位置的數(shù)字岖寞，如果arr[1]>arr[2]，交換arr[1]和arr[2]渊涝，否則不交換位置慎璧；比較arr[N-2]和arr[N-1]...
* 2. 比較索引0床嫌，1位置的數(shù)字跨释，如果arr[0]>arr[1},交換arr[0]和arr[1]的位置,否則不交換位置胸私；比較索引1,2位置的數(shù)字，如果arr[1]>arr[2]鳖谈，交換arr[1]和arr[2]岁疼，否則不交換位置；比較arr[N-3]和arr[N-2]...
* 3. 比較索引0缆娃，1位置的數(shù)字捷绒，如果arr[0]>arr[1},交換arr[0]和arr[1]的位置,否則不交換位置；比較索引1,2位置的數(shù)字贯要，如果arr[1]>arr[2]暖侨，交換arr[1]和arr[2]，否則不交換位置崇渗；比較arr[N-4]和arr[N-3]...
*
* @param arr 待排序數(shù)組
*/
public static void bubbleSort(int[] arr) {
// 先處理邊界
if (arr == null || arr.length <2) {
return;
}
int N = arr.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtil.swap(arr, j, j + 1);
}
}
}
}
/**
* 選擇排序
* 給定一個(gè)數(shù)組字逗，使用選擇排序時(shí)，先假定第一個(gè)位置是最小值宅广，依次向后查找葫掉，找到更小的數(shù)就更新最小索引，遍歷完成交換第一個(gè)位置和最小索引數(shù)跟狱；再假定第二個(gè)位置是最小值俭厚，
* 依次向后查找，找到更小的數(shù)就更新最小索引驶臊，遍歷完成交換第二個(gè)位置和最小索引數(shù);重復(fù)這個(gè)步驟挪挤，最后假定數(shù)組長(zhǎng)度N-2的位置是最小值，與N-1的位置比較关翎，如果后面的數(shù)更小
* 就交換位置电禀。這樣整個(gè)數(shù)組就排序完成了。
*
* 操作步驟：
* 1笤休、假定最小數(shù)索引minValueIndex = 0,依次比較索引1,2,3...N, 如果找到更小的數(shù)尖飞，更新最小索引minValueIndex，交換索引0和minValueIndex的數(shù)字
* 2店雅、假定最小數(shù)索引minValueIndex = 1,依次比較索引2,3...N, 如果找到更小的數(shù)政基，更新最小索引minValueIndex，交換索引1和minValueIndex的數(shù)字
* 3闹啦、假定最小數(shù)索引minValueIndex = 2,依次比較索引2,3...N, 如果找到更小的數(shù)沮明，更新最小索引minValueIndex,交換索引2和minValueIndex的數(shù)字
* .
* .
* .
* N、假定最小數(shù)索引minValueIndex = N-1,依次比較索引N-1,N, 如果找到更小的數(shù)窍奋，更新最小索引minValueIndex,交換索引N-1和minValueIndex的數(shù)字
* @param arr 待排序數(shù)組
*/
public static void selectionSort(int[] arr) {
// 先處理邊界
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
for (int i = 0; i < N; i++) {
int minValueIndex = i;
for (int j = i + 1; j < N; j++) {
if (arr[minValueIndex] > arr[j]) {
minValueIndex = j;
}
}
SortUtil.swap(arr, i, minValueIndex);
}
}
}
SortUtil工具類
package sort;
/**
* @Author Seth
* @Date 2021/9/7
*/
public class SortUtil {
/**
* 打印數(shù)組
*
* @param arr 數(shù)組
*/
public static void printArr(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
/**
* 交換數(shù)組中索引為i, j的數(shù)字的位置
*
* @param arr 數(shù)組
* @param i 要交換位置的索引
* @param j 要交換位置的索引
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
