排序算法汇总

排序算法

选择排序

冒泡排序

插入排序

梳排序

/**
 * 梳排序
 * @param a
 * @return
 */
public static int[] combSort(int[] a) {
    int N = a.length;
    int step = N;
    int k;
    // 第一部分
    while((step /= 1.3) > 1) {
        for (int i = N-1; i >= step; i--) {
            k = i -step;
            if(a[k]>a[i]){
                // 交换位置
                exc(a, k, i);
            }
        }
    }
    // 第二部分：进行冒泡排序
    a= bubbleSort2(a);
    return a;
}

希尔排序

/**
 * shell排序
 * @param a
 * @return
 */
public static int[] shellSort(int[] a){
    int N = a.length;
    int h = 1;
    // 增量序列
    while(h < N/3){
        // h = 1,4,13,40,……
        h = h*3 + 1; 
    }

    while(h>=1){
        for (int i = h; i < N; i++) {
            // 进行插入排序，诺a[j]比a[j-h]小，则向前挪动h
            for (int j = i; j >= h && a[j-h]>a[j]; j -= h) {
                exc(a, j, j-h);
            }
        }
        h /= 3;
    }
    return a;
}

参考 https://www.cnblogs.com/xiaohuiduan/p/11188304.html