常用的排序算法详解：希尔排序，桶排序，选择排序，冒泡排序，快速排序

排序算法——希尔排序

希尔排序是插入排序的一种，又称"缩小增量排序”，是插入排序算法的一种更高效的改进版本。

希尔排序原理

• 1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组。
• 2.对分好组的每一组数据完成插入排序。
• 3.减小增长量，最小减为1，重复第二步操作。

code 实现

希尔排序的API设计

• 类名 Shell
• 构造方法 Shell():创建Shell对象
• 成员方法
  • 1.public static void sort(Comparable[] a): 对数组内的元素进行排序
  • 2.private static boolean greater(Comparable v,Comparable w): /判断v是否大于w
  • 3.private static void exchange(Comparable[] a,int i,int j): 交换a数组中，索引i和索引j处的值

希尔排序的代码实现

public class Shell {
    //对数组a中的元素进行排序
    public static void sort(Comparable[] a){
        int N=a.length;
        //确定增长量h的最大值
        int h=1;
        while(h<N/2){
            h=2*h+1;
        }
        //当增长量h小于1，排序结束
        while(h>=1){
            //找到待插入的元素
            for(int i=h;i<N;i++){
                //a[i]就是待插入的元素
                //把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中
                for(int j=i;j>=h;j-=h){
                    //a[j]就是待插入的元素，依次和a[j-h],a[j-2h],a[j-3h]进行比较，如果a[j]小，
                    // 那么交换位置，如果不小于，a[j]大，则插入完成
                    if(greater(a[j-h],a[j])){
                        exchange(a,j,j-h);
                    }else{
                        break;
                    }
                }
            }
            h/=2;
        }
    }
    //比较v元素是否大于w元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    //数组元素i和j交换位置
    private static void exchange(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
class Test{
    public static void main(String[] args) {
        Integer[] a={9,1,2,5,7,4,8,6,3,5};
        Shell.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

由于增量h没有固定的值，希尔排序的时间复杂度较为复杂，但在处理大批量数据时，希尔排序的性能高于插入排序！

希尔排序的第二种写法

public class ShellSort {
    private static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        int temp;
        while (gap >= 1) {
            for (int i = gap; i < arr.length; i++) {
                temp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
            gap = gap / 2;
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

排序算法——桶排序

桶排序是计数排序的升级版。通过“分配”和“收集”过程来实现排序，分治思想。

原理

设计k个桶( bucket )（编号O~k-1)，然后将n个输入数分布到各个桶中去，对各个桶中的数进行排序，然后按照次序把各个桶中的元素列出来即可。

适用范围：均匀分配

code 实现

第一种写法：