直接插入排序

发表于 分类于 ， ， 本文字数： 1.1k

代码实现

直接插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void sort(int l,int r){
    int tmp;
    for (int i = l+1,j; i <= r; i++) {
        tmp = data[i];
        for ( j = i; j >0; j--) {    //从后往前找
            if(data[j-1]>tmp){
                data[j]=data[j-1];   //比它大的往后移
            }else {        
                break;
            }
        }
        data[j]=tmp;                //填补空位
    }
}

折半插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private int lookForIndex(int l, int r, int val){

       int bl=l,br=r;
       int index=br;
       if(data[r]<=val){  //最大的数都小于等于它，就找不到
           return -1;
       }else if(data[l]>val){  //最小的数都大于它，直接插最前面
           return 0;
       }
       while (bl<br){        // data[l]<= val <data[r]  ,[l+1,r]中必有一个是最小的比val大的数，找到的数必比val大
          
           index = (bl+br)/2;
           if(data[index]>val){
               br=index;
           }else {
               bl=index+1;
           }
       }
       index = br;   //区间唯一，找到点了
       return index;
   }

   public void sortByBinary(int l,int r){
       int tmp,index;
       for (int i = l+1; i <= r; i++) {
           tmp = data[i];
           index = lookForIndex(l,i-1,tmp);
           if(index<0){  //找不到就不用插入了
               continue;
           }
           for (int j = i; j >index; j--) {
               data[j]=data[j-1];
           }
           data[index]=tmp;
           System.out.println(l+" "+i+" "+index+" "+Arrays.toString(data));
       }
   }
------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏