基础排序

冒泡排序

public void sort(List<Integer> data){
    for(int i=0;i<data.size()-1;i++){
        for(int j=0;j<data.size()-1-i;j++){
            if(data.get(j)>data.get(j+1)){
                int temp = data.get(j);
                data.set(j,data.get(j+1));
                data.set(j+1,temp);
            }
        }
    }
}

快速排序

public void sort(List<Integer> data,int left,int right){
    if(left >= right){
        return;
    }
    int key = data.get(left);
    int i = left;
    int j = right;
    while(i < j){
        while(data.get(j)>=key && i < j){
           j--;
        }
        while(data.get(i)<=key && i < j){
           i++;
        }
        if(i < j){
            int temp = data.get(i);
            data.set(i,data.get(j));
            data.set(j,temp);
        }
    }
    data.set(left,data.get(i));
    data.set(i,key);
    sort(data,left,i-1);
    sort(data,i+1,right);
}

简单插入排序

public void sort(List<Integer> data){
    for(int i=1;i<data.size();i++){
        int key = data.get(i);
        int j = i-1;
        while(data.get(j) > key && j>0){
            int temp = data.get(j);
            data.set(j,data.get(j+1));
            data.set(j+1,temp);
            j--;
        }
    }
}

希尔排序

public void sort(List<Integer> data){
    for(int i=data.size()/2;i>0;i=i/2){
            for(int j=i;j<data.size();j++){
                int key = data.get(j);
                int index = j;
                while(index-i >=0 && data.get(index-i) > key){
                    int temp = data.get(index);
                    data.set(index,data.get(index-i));
                    data.set(index-i,temp);
                    index = index-i;
                }
            }
     }
}

选择排序

public void sort(List<Integer> data){
    for(int i=0;i<data.size()-1;i++){
        int min = i;
        for(int j=i;j<data.size();j++){
            if(data.get(min)>data.get(j)){
                min = j;
            }
        }
        int temp = data.get(i);
        data.set(i,data.get(min));
        data.set(min,temp);
    }
}

归并排序

public List<Integer> getResult(List<Integer> data){
    if(data.size()<2){
        return data;
    }
    int mid = data.size()/2;
    List left = data.subList(0,mid);   //subList方法切出来的List是subList，会抛异常
    List right = data.subList(mid,data.size());
    return sort(getResult(left),getResult(right));
}
public List<Integer> sort(List<Integer> left,List<Integer> right){
    List<Integer> result = new ArrayList();
    while(left.size()>0 && right.size()>0){
        if(left.get(0)<right.get(0)){
            result.add(left.get(0));
            left.remove(0);
        }else{
            result.add(right.get(0));
            right.remove(0);
        }
    }
     if (left.size() >0){
        left.stream().forEach(l -> result.add(l));
     }
    if (right.size() >0){
        right.stream().forEach(r -> result.add(r));
    }
    return result;
}

参考：https://www.cnblogs.com/onepixel/articles/7674659.html