基本排序算法-java 有更新!

  cheney

排序算法是最基本的算法之一,是许多人开始学习算法的启蒙,对理解计算机软件编写有很好的帮助。大致可分为:插入排序、交换排序、选择排序和其他排序。

为了方便测试,先做了几个工具函数。


private static void swap(int[] arr, int i ,int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
private static int[] createRamdomDate() {
    return createRamdomDate(100);
}

private static int[] createRamdomDate(int len) {
    int[] buff = new int[len];
    for( int i=0 ; i < len; i++ ){
        buff[i] = (int)(Math.random() * 200 - 100);
    }
    return buff;
}

private static void isOrdered(int[] list) throws Exception {
    for( int i=1 ; i< list.length ; i++ ){
        if( list[i] < list[i-1] ){
            throw new Exception(String.format("没排好: 第 %d 个数值是 %d | 第 %d 个数值是 %d",
                    i-1,list[i-1],i,list[i]));
        }
    }
}

选择排序

简单选择排序

/**
 * 选择排序
 * @param a
 */
public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int num = a[i];
        int loc = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < num) {
                num = a[j];
                loc = j;
            }
        }
        swap(a, i, loc);
    }
}

排序过程可以描述为:找一个位置,从后面的数据中选出最小的,放在这里,然后找下一个位置的数。
时间复杂度:最好 O(n * n),最坏O(n * n),平均 O(n * n)

堆排序

简单选择排序的绝大多数时间都浪费在挑出最小的数的过程,用堆积树的结构可以简化这个过程。堆积树是一种简单的二元树,(限定条件只有,最多两个子节点,父节点小于所有子节点),根节点永远是最小的节点。

/**
 * 推排序 调整树
 * @param a
 * @param i
 * @param len
 */
public static void adjustTree(int[]a, int i, int len){
    int lchild = 2 * i + 1;
    int rchild = 2 * i + 2;
    int father = i;
    if ( father < (len/2)){
        if( lchild < len && a[lchild] > a[father] ){
            father = lchild;
        }
        if( rchild < len && a[rchild] > a[father] ){
            father = rchild;
        }
        if (father != i){
            swap(a,father,i);
            adjustTree(a,father,len);
        }
    }

}

/**
 * 堆排序 建立树
 * @param all
 */
public static void buildTree(int[]all){
    for (int i=all.length/2 -1 ; i>=0 ; i--){
        adjustTree(all,i,all.length);
    }
}

/**
 * 堆排序
 * @param a
 */
public static void heapSort(int[] a) {
    buildTree(a);
    for (int i = a.length -1; i >= 0; i--) {
        swap(a,0,i);
        adjustTree(a,0,i);
    }
}

虽然从小到大排序,但是用了大顶堆,因为堆顶在 0, 最后一个一个取下来,放在最后。
调整堆积树的时候,只需要调整在长度的前一半就可以保证生成合法的生成树,后面的一定都是叶子。
生成堆积树的时候,也只需要管前一半,记着倒序生成。

插入排序

插入排序的基本想法是,将无序的序列一个个的插入到另一个空的序列中去,排序就完成了。包括:简单插入排序和希尔排序。

简单插入排序

/**
 * 简单插入排序
 * @param a
 */
public static void insertSort(int[] a) {
    for(int i=1; i<a.length; i++){
        int temp = a[i];
        int j = i-1;
        while( j >= 0 && a[j] > temp){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=temp;
    }
}

实际上并没有写成插入到另一个空序列中的方式,而是还在原来的数组中处理,因为“一个萝卜一个坑”,只需要额外的一个 temp 变量的存储空间就足够了。

排序过程可以描述为 : 拿出后面的数,和它前面的数依次比较,(前面的数认为是有序的,后面的数认为是无序的),如果它比前面的数大(或相等),那这里就是它的位置,如果比前面的数小, 就把前面的数往后移动,把当前数和前前面的数比较。

  • i的循环从 1 开始,可以避免一轮空操作。
  • 比较的时候不包含等号,可以减少不必要的移动。

时间复杂度:最好 O(n),最坏O(n * n),平均 O(n * n)

希尔排序

基本想法是将原始数组分成几段,对每一段都执行简单插入排序。

// shell
public static void shellSort(int[] a){
    int gap = 0;
    while( gap<a.length ){
        gap = gap*3 + 1;
    }
    while( gap > 0 ){
        for(int i = gap; i< a.length; i++){
            int j = i-gap;
            int temp = a[i];
            while(j >=0 && a[j] > temp){
                a[ j+gap ]=a[j];
                j -=gap;
            }
            a[j+gap] = temp;
        }
        gap=(gap-1)/3;
    }
}

人为规定了一个步长,这里是 3,然后不断的缩小 gap直到 1,此时就是插入排序了。

交换排序

冒泡排序

/**
 * 冒泡排序
 * @param a
 */
public static void bubbleSort(int[] a) {
    boolean flag = true;
    for (int i = 0; i < a.length && flag; i++) {
        flag = false;
        for (int j = 0; j < a.length - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a, j + 1, j);
                flag = true;
            }
        }
    }
}

排序过程可以描述为:不断的扫描数组,如果发现前面的比后面大,就把这两个数交换。
- 每一轮都会产生最大的数,这个数的位置不会再动了,(冒泡到顶了),可以减少扫描次数。
- 如果有一轮,一次交换都没有发生,那就证明已经排好了。可以提前结束循环。

时间复杂度:最好 O(n),最坏O(n * n),平均 O(n * n)

快速排序

/**
 * 快速排序
 * @param a
 */
public static void quickSort(int[] a) {
    quickSort(a,0,a.length -1);
}

// 快速排序
public static void quickSort(int[] a, int i, int j) {
    // 只有一个数据或者出错了
    if (i >= j) {
        return;
    }
    // 只有两个数据
    if (i + 1 == j) {
        if (a[i] > a[j]) {
            swap(a, i, j);
        }
        return;
    }

    int[] first = new int[j - i + 1];
    int[] last = new int[j - i + 1];
    int firstNum = 0;
    int lastNum = 0;
    int sentinel = a[i];

    // 将数据按照对一个数的大小分成两组
    for (int n = i + 1; n <= j; n++) {
        if (a[n] < sentinel) {
            first[firstNum++] = a[n];
        } else {
            last[lastNum++] = a[n];
        }
    }

    // 将前面的数据拷贝回去
    System.arraycopy(first,0,a,i,firstNum);

    // 加上基准数据
    a[firstNum + i] = sentinel;

    // 将后面的数据拷贝回去
    System.arraycopy(last,0,a,firstNum + 1 + i,lastNum);

    // 对前面的数同样排序
    quickSort(a, i, firstNum - 1 + i);
    // 对后面的数同样排序
    quickSort(a, firstNum + 1 + i, j);
}```

排序过程可以描述为:随便拿一个数,所有比这个数大的放到一边,比这个数小的,放到另一边。直到只有一个数了,或者只有两个数了。
时间复杂度:最好 O(n logn),最坏O(n * n),平均 O(n logn)


## 并归
并归排序和快速排序的想法类似,快速排序分组的时候要求一边的数全部大于基准,一边的数全部小于基准。并归排序只是简单的简单的分成两组,分别排序之后再合起来。

```java
/**
 * 归并排序
 */
public static void mergeSort(int[] a){
    mergeSort(a,0,a.length-1);
}
public static void mergeSort(int[] a, int i, int j) {
    if (i >= j) {
        return;
    }
    if (i + 1 == j) {
        if (a[i] > a[j]) {
            swap(a, i, j);
        }
        return;
    }

    int middle = (i + j) / 2;
    int beforeMiddle = i;
    int afterMiddle = middle + 1;

    // 分别排序
    mergeSort(a, beforeMiddle, middle);
    mergeSort(a, afterMiddle, j);

    // merge
    int[] b = new int[j - i + 1];
    int bNum = 0;
    while (beforeMiddle <= middle && afterMiddle <= j) {
        if (a[beforeMiddle] < a[afterMiddle]) {
            b[bNum] = a[beforeMiddle];
            beforeMiddle++;
            bNum++;
        } else {
            b[bNum] = a[afterMiddle];
            afterMiddle++;
            bNum++;
        }
    }

    // 或许有一边会比较多 有一边会比较少
    while (beforeMiddle <= middle) {
        b[bNum] = a[beforeMiddle];
        bNum++;
        beforeMiddle++;
    }
    while (afterMiddle <= j) {
        b[bNum] = a[afterMiddle];
        bNum++;
        afterMiddle++;
    }

    // 拷贝回去
    System.arraycopy(b,0,a,i,j - i + 1);
}