java排序

2018-11-09 02:38:14来源：博客园阅读 ()

双端扫描交换排序


public  void sort(int[] item, int start,int end){
        if(start < end){
            int head = item[start];
            int i = start + 1;
            int j = end;
            while(i <= j){
                while(i <= j && item[i] < head){//条件满足的话,i一直向右走, 直到条件终止(item[i]大于pro)
                    i ++;
                }
                //注意: 这里的大小判断用的是大于等于
                while(i <= j && item[j] >= head){//条件满足,j一直向左走, 直到条件终止(item[i]小于pro)
                    j --;
                }
                //当i,j停止移动,说明item[i]大于pro, item[j]小于pro, 这个时候交换item[i]和item[j]的值
                if(i <= j){//交换i j , 小的在左边,大的在右边
                    int tem = item[i];
                    item[i] = item[j];
                    item[j] = tem;
                }
            }
            //当i大于j的时候,将pro和item[j]交换, 这样就形成了以item[j]为分界点, 左边小于item[j], 右边大于item[j]
            int tem = item[j];
            item[j] = head;
            item[start] = tem;
            //快排左边
            sort(item,start,j-1);
            //快排右边
            sort(item,j+1,end);
        }
    }

赋值排序

public void filling(int[] item, int start, int end){
        if(start < end){
            int head = item[start];
            int i = start;
            int j = end;
            while(i < j){
                while(i < j && item[j] > head){
                    j --;
                }
                item[i] = item[j];
                while(i < j && item[i] <= head){
                    i ++;
                }
                item[j] = item[i];
            }
            item[i] = head;
            filling(item,start,i - 1);
            filling(item, i + 1, end);
        }
    }