排序算法

MergeSort.java

public class MergeSort {
    
    private static int[] aux;  // 辅助数组

    /*
     * 自底而上归并排序法对 a 数组的元素进行排序
     * @param a 原数组
     * @effect a 数组中的所有元素变为升序
     */
    public static void mergeSortDownToUp(int[] a) {
        int N = a.length;
        aux = new int[N];
        for (int sz = 1; sz < N; sz+=sz) { // sz 为元素间隔，从 1 开始
            for (int lo = 0; lo < N-sz; lo += 2 * sz) {
                int mid = lo + sz - 1; // mid 是 a[lo..mid] a[mid+1..hi],前一个数组的结尾
                int hi = Math.min(lo+sz+sz-1,N-1);
                merge(a,lo,mid,hi);
            }
        }
    }


    /*
     * 自顶而下归并排序法对 a 数组的元素进行排序
     * @param a 原数组
     * @effect a 数组中的所有元素变为升序
     */
    public static void mergeSort(int[] a) {
        aux = new int[a.length];
        mergeSortHelper(a,0,a.length-1);
    }

    /*
     * 归并排序的帮助函数
     * @param a 原数组
     * @param lo 低位
     * @param hi 高位,后面数组的最后一个index
     * @effect a 数组中的所有元素变为升序
     */
    private static void mergeSortHelper(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        mergeSortHelper(a,lo,mid);
        mergeSortHelper(a,mid + 1,hi);
        merge(a,lo,mid,hi);
    }

    /*
     * 将 a[lo..mid] 和 a[mid+1..hi] 归并
     * @param a 原数组，其中 lo-mid, mid-hi 为有序的
     * @param lo 定位 index 低位
     * @param mid 定位 index 中位，前面的数组的最后一个index
     * @param hi  定位 index 高位,后面数组的最后一个index
     * @effect a  a 数组中的所有元素变为升序
     */
    private static void merge(int[] a,int lo,int mid,int hi) {
        int i = lo;             // i,j 用来定位辅助数组的位置
        int j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];      // 辅助数组与 a 的元素相同
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {          // 此时 i 已经跑完了
                a[k] = aux[j];
                j++;
            } else if (j > hi) {    // 此时 j 已经跑完了
                a[k] = aux[i];
                i++;
            } else if (aux[i] > aux[j]) {
                a[k] = aux[j];
                j++;
            } else {
                a[k] = aux[i];
                i++;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{1,5,6,41,62,12,2,6,32,11,6,3,6,8,3,1,4,4};
        mergeSortDownToUp(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

QuickSort.java

public class QuickSort {

    /*
     * 使用快速排序对数组 a 进行排序
     * @param a 原数组
     * @return 成功排序的数组
     */
    public static void quickSort(int[] a) {
        StdRandom.shuffle(a);
        quickSortHelper(a,0,a.length-1);
    }

    /*
     * 使用快速排序的帮助方法，lt，gt 对应的值等于 val 的index 开始和结束
     * @param a 原数组
     * @param lo 排序位置起点
     * @param hi 排序位置终点, hi 对应的是数组的最后一个 index
     * @return 成功排序的数组
     */
    private static void quickSortHelper(int[] a,int lo,int hi) {
        if (lo >= hi) return;
        int lt = lo;  // a[lo..lt-1] 都小于 val
        int gt = hi;  // a[gt+1..hi] 都大于 val
        int i = lo + 1;  // a[lt..i] 等于 val, a[i+1..gt] 未定
        int val = a[lo];
        while (i <= gt) {
            if (a[i] < val) {
                exch(a,lt,i);
                i++;
                lt++;
            } else if (a[i] > val) {
                exch(a,gt,i);
                gt--;
            } else {
                i++;
            }
        }
        quickSortHelper(a,lo,lt - 1); // 左边快排
        quickSortHelper(a,gt + 1,hi); // 右边快排
    }


    /*
     *  交换数组索引为 i,j 的数值
     * @param a 原数组
     * @param i 索引 i
     * @param j 索引 j
     * @effect a 数组中 i,j 对应的数值发生交换
     */
    private static void exch(int[] a,int i,int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1,5,6,3,5,3,2,6,32,4};
        quickSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}

SimpleSort.java

public class SimpleSort {

  
  // ---------------------------选择排序---------------------
    /*
     * 选择排序法对 a 数组的元素进行排序
     * @param a 原数组
     * @effect a 数组中的所有元素变为升序
     */
    public static void selectSort(int[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int minNumberIndex = i;          // 最小值的Index初定为 i
            for (int j = i+1; j < N; j++) { // 在余下的数组中找到最小值
                if (a[j] < a[minNumberIndex]) minNumberIndex = j;
            }
            exch(a,i,minNumberIndex);
        }
    }
    
    
    /*
     *  交换数组索引为 i,j 的数值
     * @param a 原数组
     * @param i 索引 i
     * @param j 索引 j
     * @effect a 数组中 i,j 对应的数值发生交换
     */
    private static void exch(int[] a,int i,int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


   // ---------------------------插入---------------------

    /*
     * 插入排序法对 a 数组的元素进行排序
     * @param a 原数组
     * @effect a 数组中的所有元素变为升序
     */
    public static void InsertSort(int[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) { // 第一个元素不用排序
            int temp = a[i];//先把要排序的数取出来
            int leftindex = i - 1; // 已排序数组的最后一个 index
            while(leftindex >= 0 && a[leftindex] > temp){//当比到最左边或者遇到比temp小的数据时，结束循环
                a[leftindex + 1] = a[leftindex];
                leftindex--;
            }
            a[leftindex + 1] = temp;//把temp放到空位上
        }
    }


    // ---------------------------希尔---------------------

    /*
     * 希尔排序法对 a 数组的元素进行排序
     * @param a 原数组
     * @effect a 数组中的所有元素变为升序
     */
    public static void ShellSort(int[] a) {
        int N = a.length;
        for(int h = N / 2; h > 0; h /= 2) { // h 从 N/2 逐渐减小到 1
          // 接下来间隔 h 是有序的，使用插入排序法
            InsertSort(a, h);
            }
        }

    /*
     * 为希尔排序法准备的插入排序法，对 a 数组的元素进行间隔 h 的排序，h = 1 为插入排序
     * @param a 原数组
     * @param h 间隔数
     * @effect a 数组中间隔 h 是升序的
     */
    private static void InsertSort(int[] a, int h) {
        int N = a.length;
        for (int i = 1; i < N; i++) { // 第一个元素不用排序
            int temp = a[i];//先把要排序的数取出来
            int leftindex = i - h; // 已排序数组的最后一个 index
            while(leftindex >= 0 && a[leftindex] > temp){//当比到最左边或者遇到比temp小的数据时，结束循环
                a[leftindex + h] = a[leftindex];
                leftindex-= h;
            }
            a[leftindex + h] = temp;//把temp放到空位上
        }
    }



    public static void main(String[] args) {
        int[] a = new int[]{1,5,6,3,5,3,2,6,32,4};
        ShellSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

原理.md

选择排序

• 找到最小的元素，将其与数组中第一个元素交换

插入排序

• 很适用于非随机数组
• 将每个元素插入到一个已经排序的数组
• 插入的元素之后的所有元素位置往后挪一位

希尔排序

• 解决插入排序中每次比较的都是相邻的问题
• 先使数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组
• 对于每个h，用插入排序将h个子数组独立地排序
• 逐渐减小h，直到h = 1
• 实现方法
  • 把插入排序改造为间隔为 h 的插入排序
  • 用一个 for 循环不断调整 h

归并排序

• 分治思想
• 把数组二分，左边和右边分别排序，然后合并
• mergeSort() -> sort(left) and sort(right) and merge(left,right)
  • 另一种思路是自底而上的思想，先两两合并小数组，依次增加（比如先合并1元素的数组，再合并2，再合并4...）
• sort(left) 这种输入参数需要包括 lo 和 hi
• merge 需要包括 lo、mid、hi, 实现过程中要开个全局变量辅助数组 aux（因为每次都开新数组空间利用很大），aux 与原来的 a[lo..hi] 相同，实现 merge 函数时，要给 aux 定义两个 index 变量 i,j。 利用 aux 辅助数组来替换 a 数组中的值

快速排序

• 分区，比它小的放左边 a[lo..lt-1]，等于它的放中间 a[lt..gt]，比它大的放右边 a[gt+1..hi]
• sort() -> 采用三向切分，遍历 a，用 i 来遍历 a,直到达到 gt`
  • 对于每次的 i, 满足 a[lo..lt - 1] < val,a[gt+1..hi] >val, a[lt..i-1] == val, a[i..gt] 未知
  • a[i] < v -> a[lt](a[lt]一直等于val) 与 a[i] 交换，lt 和 i 加 1
  • a[i] > v -> a[gt](a[gt]一直是未知) 与 a[i] 交换，gt - 1 (但 i 不变，因为每次锁定的是 a[lo..lt - 1]，a[gt + 1..hi]， a[lt..i-1]的变量)
  • a[i] = v -> i + 1