插入排序
1、直接插入排序
2、折半插入排序
3、希尔排序
1、直接插入排序
package sort; public class InsertSort {//直接插入排序 //有序区 无序区 [前：后] public static void sortA(int[] arr,int n){ int tmp;//临时值 int i,j; for(i=1;i<n;i++){//保证从小到大 if(arr[i]<arr[i-1])//后一个数 <前一个数 { tmp=arr[i];//存放那个值 //比较大的数，向右移动 //不可缺少的条件：j>=0 //失败一： //for(j=i-1;arr[j]>tmp;j--){ //失败二： //for(j=i-1;arr[j]>tmp&&j>=0;j--){ for(j=i-1;j>=0&&arr[j]>tmp;j--){ // i-1 > i arr[j+1]=arr[j]; } arr[j+1]=tmp; } } } public static void main(String[] args) { int arr[]={4,5,6,3,1,9,0,8,7,2}; System.out.println("排序前："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } sortA(arr,arr.length); System.out.println("\n排序后："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } } }2、折半插入排序
package sort; //折半插入排序 public class HalfInsertSort { // 有序区 无序区 [前：后] public static void sortA(int[] arr, int n) { int tmp;// 临时值 int i, j; int low, mid, high;// 左边 中间 右边 for (i = 1; i < n; i++) {// 保证从小到大 tmp = arr[i];// 存放那个值 // 改进了直接插入排序的插入点位置 // 通过折半查找的方法进行查找插入位置，优化 low = 0; high = i - 1; // high = n - 1;//错误 while (low <= high) {// 在arr[low .. high] 中折半查找 有序 插入的位置 mid = (low + high) / 2;// 中间位置 if (arr[mid] > tmp) {// 插入位置 在 左半区【左】 high = mid - 1; } else low = mid + 1;// 插入位置 在 右半区【右】 }//low>high的时候终止 // System.out.println("low:"+low+"---high:"+high); //此时，知道了插入的元素位置 //插入位置为 x=high+1=low //方法一： //注意:j=i-1开始，因为for循环的开始，是1开始 for(j=i-1;j>=high+1;j--){ // i-1 > i arr[j+1]=arr[j]; } arr[high+ 1] = tmp; //将插入位置到待插入元素的位置上的元素整体向后移动一个位置 //方法二： // for(j = i; j > low; j--) { // arr[j] = arr[j-1]; // } // arr[low] = tmp; } } public static void main(String[] args) { int arr[] = { 4, 5, 6, 3, 1, 9, 0, 8, 7, 2 }; System.out.println("排序前："); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } sortA(arr, arr.length); System.out.println("\n排序后："); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }3、希尔排序
package sort; //希尔排序 优于 n*n public class ShellSort { //直接插入排序 --> 希尔排序 public static void sortA(int[] arr,int n){ int tmp;//临时值 int i,j; int gap=n;//间隔 while(gap>1){//gap=1的时候，排序完成 gap=gap/3+1; //直接插入排序：比较 i 和 i-1 //希尔排序： 比较 i 和 i-gap for(i=gap;i<n;i++){//保证从小到大 if(arr[i]<arr[i-gap])//后一个数 <前一个数 { tmp=arr[i];//存放那个值 //比较大的数，向右移动 //直接插入排序：比较 i-1 > i 移动 j-- //希尔排序： 比较 i-gap > i 移动 j=j-gap for(j=i-gap;j>=0&&arr[j]>tmp;j=j-gap){ arr[j+gap]=arr[j]; } arr[j+gap]=tmp; } } } } public static void main(String[] args) { int arr[]={4,5,6,3,1,9,0,8,7,2}; System.out.println("排序前："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } sortA(arr,arr.length); System.out.println("\n排序后："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } } }
