排序算法

五种排序算法

选择排序

选择排序两个鲜明的特点：

1. 运行时间和输入无关：为了找出最小的元素而扫描一遍数组并不能为下一趟扫描提供任何有用的信息。一个已经有序的数组或者是元素全部相等的元素和一个随机排序的数组所用的排序时间一样长。
2. 数据移动是最少的：显然可见，移动数据只发生在是外层循环中。故选择排序只用了N次交换，这是其他大部分算法不具备的。

package com.algorithms;

import java.util.Arrays;

public class Sort {

    private static int compareTo(double x, double y){
        if(x < y){
            return -1;
        }
        else if(x > y){
            return 1;
        }
        else{
            return 0;
        }
    }

    private static void exchange(double[] A, int i, int j){
        double temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    public static void selectionSort(double[] A){
        int N = A.length;
        for(int i = 0; i < N; ++i){
            int min = i;
            for(int j = i + 1; j < N; ++j){
                if(compareTo(A[min], A[j]) == 1){
                    min = j;
                }
            }
            exchange(A, i, min);
        }
    }


    public static void main(String[] args){
        double[] A1 = {5, 7, 1, 0, 4, 9, 2, 3, 8, 6};
        selectionSort(A1);
        System.out.println(Arrays.toString(A1));
    }
}

插入排序

插入排序和选择排序有一个相同的地方是：当前索引左边的所有元素都是有序的。
与选择排序不同的是：插入排序所需的时间取决于排序数组中元素的初始顺序。例如，一个很大且其中的元素已经（或接近有序）的数组进行排序会比对随机顺序的数组或者是逆序数组（最坏情况）进行来的快。
特点：插入排序对于部分有序的数组十分高效，也很适合于小规模数组。

public static void insertionSort(double[] A){
    int N = A.length;
    for(int i = 1; i < N; ++i){
        //因为[0, j-1]，已经是有序
        //如果当索引j大于索引j-1的值，那么数组[0, j]就是有序的，跳出循环
        for(int j = i; j > 0 && (compareTo(A[j-1], A[j]) == 1); --j){
            exchange(A, j-1, j);
        }
    }
}

希尔排序

希尔排序是一种基于插入排序的快速排序算法。
对于大规模的乱序排序算法，插入排序会很慢，因为它只会交换相邻的元素，因此元素只能一点点地从数组的一端移动到另一端。希尔排序为了加快排序，交换不相邻的元素对数组局部进行排序，并最终用插入排序将局部有序的数组排序。
特点：对于中等大小的数组运行时间可接受。它的代码量小，且不需要额外的内存空间。

public static void shellSort(double[] A){
    int N = A.length;
    int h = 1;
    while(h < N/3){
        h = 3 * h + 1;
    }
    while(h >= 1){
        for(int i = h; i < N; ++i){
            for(int j = i; j >= h && compareTo(A[j-h], A[j]) == 1; j -= h)
            exchange(A, j-h, j);
        }
        h = h / 3;
    }
}

归并排序

将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
优点：它能够保证将任意长度为N的数组排序所需的时间和NlogN成正比；
缺点：所需额外的辅助空间和N成正比。

 private static double[] aux;

 public static void mergeSort(double[] A){
     aux = new double[A.length];
     mergeSortAPI(A, 0, A.length-1);
 }

//进行分割数组操作
 private static void mergeSortAPI(double[] A, int lo, int hi){
     if(lo >= hi){
         return;
         //可以设置当lo + x >= hi时，使用插入排序，减少递归带来的性能损耗
     }
     int mid = lo + (hi - lo) / 2;
     mergeSortAPI(A, lo, mid);
     mergeSortAPI(A, mid+1, hi);
     merge(A, lo, mid, hi);
 }

 private static void merge(double[] A, int lo, int mid, int hi){
     for(int k = lo; k <= hi; ++k){
         aux[k] = A[k];
     }
     int i = lo;
     int j = mid+1;
     for(int k = lo; k <= hi; ++k){
         if(i > mid){
             A[k] = aux[j++];
         }
         else if(j > hi){
             A[k] = aux[i++];
         }
         else if(compareTo(aux[i], aux[j]) == -1){
             A[k] = aux[i++];
         }
         else{
             A[k] = aux[j++];
         }
     }
 }

快速排序

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；快速排序则是当两个数组都有序时，整个数组也自然就有序了。

public static void quickSort(double[] A){
    quickSortAPI(A, 0, A.length-1);
}
private static void quickSortAPI(double[] A, int lo, int hi){
    if(lo >= hi){
        //这里可以使用插入排序，降低递归带来的效率下降
        //判断条件应该是 lo + x >= hi
        return;
    }
    int pivot = partition(A, lo, hi);
    quickSortAPI(A, lo, pivot-1);
    quickSortAPI(A, pivot+1, hi);
}

private static int partition(double[] A, int lo, int hi){
    int pivot = lo;
    int i = lo;
    int j = hi+1;

    for( ; ; ){

        //这里的边界条件是i < hi, 如果当i == hi时
        //在进行下次循环的时候访问的A[hi+1]就会越界
        while(compareTo(A[++i], A[pivot]) == -1 && i < hi){}
        while(compareTo(A[pivot], A[--j]) == -1 && j > lo){}

        //这里的边界条件是相同的道理,如果 i == j == hi 时候未跳出
        //在for循环的第一次while的A[hi+1]就会越界
        if(i >= j){
            break;
        }
        exchange(A, i, j);
    }

    exchange(A, pivot, j);
    //pivot记得放在正确的位置
    //A[lo, j-1] <= A[j] <= A[j+1, hi] 成立

    return j;
}

三向切分的快速排序

优点：三向切分的快速排序比归并排序、标准快速排序和其他排序方法在包括重复元素很多的实际应用中更快。

public static void quickThreeWaySort(double[] A){
    quickThreeWay(A, 0, A.length-1);
}

private static void quickThreeWay(double[] A, int lo, int hi){
    if(lo >= hi){
        //同上
        return;
    }

    double pivot = A[lo];
    int lt = lo;	//小于pivot的指针
    int i = lo + 1;	//等于pivot的指针
    int gt = hi;	//大于pivot的指针
    while(i <= gt){
        int cmp = compareTo(A[i], pivot);
        if(cmp < 0){
            exchange(A, i++, lt++);
        }
        else if(cmp > 0){
            exchange(A, i, gt--);
        }
        else{
            i++;
        }
    }
    //跳出while循环后
    //A[lo, lt-1] < pivot=A[lt, gt] < A[gt+1, hi]成立

    quickThreeWay(A, lo, lt-1);
    quickThreeWay(A, gt+1, hi);
}

public static void quickSort(double[] A){
    quickSortAPI(A, 0, A.length-1);
}
private static void quickSortAPI(double[] A, int lo, int hi){
    if(lo >= hi){
        //这里可以使用插入排序，降低递归带来的效率下降
        //判断条件应该是 lo + x >= hi
        return;
    }
    int pivot = partition(A, lo, hi);
    quickSortAPI(A, lo, pivot-1);
    quickSortAPI(A, pivot+1, hi);
}

冒泡排序

public static void bubbleSort(int []A){
    int N = A.length;
    for(int i = 0; i < N; ++i){
        boolean isSequence = true;
        for(int j = N-1; j > i; --j){
            if(Util.compareTo(A, j-1, j) == 1){
                Util.exchange(A, j-1, j);
                isSequence = false;
            }
        }
        if(isSequence){
            break;
        }
    }
}

堆排序