1. 直接插入排序

1.1 详细过程

1.2 代码实现

public static void swap(int[]arr,int a,int b){int tmp=arr[a];arr[a]=arr[b];arr[b]=tmp;}public static void sort(int[] arr,int left,int right){if(right>=arr.length) return;if(left>=right) return;if(arr[left]>arr[left+1]){swap(arr,left,left+1);sort(arr,0,left);}left++;sort(arr,left,right);}public static void main(String[] args) {int[] arr=new int[]{1,5,7,21,2,6,93,8};sort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}

2. 二分插入排序

2.1 详细过程

2.2 代码实现

  public static int search(int[] arr, int left, int right, int key) {if (left > right) {// 没有找到key，返回应该插入的位置return left;}int mid = (left + right) / 2;if (arr[mid] == key) {return mid;}if (arr[mid] > key) {return search(arr, left, mid - 1, key);} else {return search(arr, mid + 1, right, key);}}public static void sort(int[]arr){//遍历比较for (int i = 1; i < arr.length; i++) {if(arr[i]<arr[i-1]){//进入二分查找int pos=search(arr,0,i-1,arr[i]);//目标位置集体往后移int tmp=arr[i];for(int j=i-1;j>=pos;j--){arr[j+1]=arr[j];}//插入arr[pos]=tmp;}System.out.println("第"+i+"次: "+Arrays.toString(arr));}}public static void main(String[] args) {int[] arr=new int[]{1,56,88,66,35,2,8};sort(arr);}

3. shell排序

3.1 详细过程

3.2 代码实现

    public static void sort(int[] arr){int gap=arr.length/2;//开始遍历int j=1;do{for(int i=0;i<arr.length-gap;i++){
[video(video-SY1ydW46-1732779457803)(type-csdn)(url-https://live.csdn.net/v/embed/436204)(image-https://v-blog.csdnimg.cn/asset/26566b09687ce9bdc33dff17e9c146c4/cover/Cover0.jpg)(title-二分插入排序1)]if(arr[i]>arr[i+gap]){//交换int tmp=arr[i];arr[i]=arr[i+gap];arr[i+gap]=tmp;}}gap/=2;System.out.println("第"+j+++"次: "+Arrays.toString(arr));}while(gap>=1);}public static void main(String[] args) {int[] arr=new int[]{1,56,88,66,35,2,8};sort(arr);}