算法（第4版）

2.2.1

2.2.2

2.2.3

package edu.algorithms.sort;

import StdLib.StdIn;
import StdLib.StdOut;

public class Merge {

    // This class should not be instantiated.
    private Merge() { }

    //记录访问数组次数
    private static int N = 0;
    // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    	
        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
            N = N + 2; //复制
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
        	N = N + 2;
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i]))
            	{
            	N = N + 2;
            	a[k] = aux[j++];
            	}
            else                           a[k] = aux[i++];
        }

        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) 
       	 return;

        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);
    }


   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }


   /***********************************************************************
    *  Index mergesort
    ***********************************************************************/
    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = index[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                    index[k] = aux[j++];
            else if (j > hi)                     index[k] = aux[i++];
            else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
            else                                 index[k] = aux[i++];
        }
    }

    /**
     * Returns a permutation that gives the elements in the array in ascending order.
     * @param a the array
     * @return a permutation <tt>p[]</tt> such that <tt>a[p[0]]</tt>, <tt>a[p[1]]</tt>,
     *    ..., <tt>a[p[N-1]]</tt> are in ascending order
     */
    public static int[] indexSort(Comparable[] a) {
        int N = a.length;
        int[] index = new int[N];
        for (int i = 0; i < N; i++)
            index[i] = i;

        int[] aux = new int[N];
        sort(a, index, aux, 0, N-1);
        return index;
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, index, aux, lo, mid);
        sort(a, index, aux, mid + 1, hi);
        merge(a, index, aux, lo, mid, hi);
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; mergesorts them; 
     * and prints them to standard output in ascending order. 
     */
    public static void main(String[] args) {
//        String[] a = StdIn.readAllStrings();
//        Merge.sort(a);
//        show(a);
    	for(int i = 1 ; i<=512 ; i++)
    	{
    		Double[] a = new Double[i];
    		for(int j = 0 ; j < a.length ;j++)
    		{
    			a[j] = Math.random();
    		}
    		Merge m  = new Merge();
    		m.sort(a);
    		System.out.println("N:" + i + "， 访问数组次数:" + m.N + ",访问次数/Nlog(N):" + m.N/(6*N *  Math.log(N)));
    	}
    }
}

private static void merge(Comparable[] a, int lo, int mid, int hi) { 
   for (int i = lo; i <= mid; i++)
      aux[i] = a[i]; 

   for (int j = mid+1; j <= hi; j++)
      aux[j] = a[hi-j+mid+1]; //将另一个数组按降序排到j=mid + 1开始

   int i = lo, j = hi;  //现在aux[hi] 是之间的a[mid +1],之后的就好理解了
   for (int k = lo; k <= hi; k++) 
      if (less(aux[j], aux[i]))  a[k] = aux[j--];
      else                           a[k] = aux[i++];
} 

package edu.algorithms.sort;

import StdLib.StdIn;
import StdLib.StdOut;

public class MergeX {
    private static final int CUTOFF = 7;  // cutoff to insertion sort

    // This class should not be instantiated.
    private MergeX() { }

    private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {

        // precondition: src[lo .. mid] and src[mid+1 .. hi] are sorted subarrays
        assert isSorted(src, lo, mid);//检测数组是否已经有序
        assert isSorted(src, mid+1, hi);

        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              dst[k] = src[j++];
            else if (j > hi)               dst[k] = src[i++];
            else if (less(src[j], src[i])) dst[k] = src[j++];   // to ensure stability
            else                           dst[k] = src[i++];
        }

        // postcondition: dst[lo .. hi] is sorted subarray
        assert isSorted(dst, lo, hi);
    }

    private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
        // if (hi <= lo) return;
        if (hi <= lo + CUTOFF) { //利用插入排序来加快小叔子的排序速度
            insertionSort(dst, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(dst, src, lo, mid);
        sort(dst, src, mid+1, hi);

        // if (!less(src[mid+1], src[mid])) {
        //    for (int i = lo; i <= hi; i++) dst[i] = src[i];
        //    return;
        // }

        // using System.arraycopy() is a bit faster than the above loop
        if (!less(src[mid+1], src[mid])) {
            System.arraycopy(src, lo, dst, lo, hi - lo + 1);//利用java库函数来加快数组的复制
            return;
        }

        merge(src, dst, lo, mid, hi);
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        Comparable[] aux = a.clone();
        sort(aux, a, 0, a.length-1);  
        assert isSorted(a);
    }


    // sort from a[lo] to a[hi] using insertion sort
    private static void insertionSort(Comparable[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && less(a[j], a[j-1]); j--)
                exch(a, j, j-1);
    }


    // exchange a[i] and a[j]
    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    // is a[i] < a[j]?
    private static boolean less(Comparable a, Comparable b) {
        return (a.compareTo(b) < 0);
    }

   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; mergesorts them
     * (using an optimized version of mergesort); 
     * and prints them to standard output in ascending order. 
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        MergeX.sort(a);
        show(a);
    }
}

public class Selection {
	public static void sort(Comparable[][] a)
	{
		int N = a.length;
		for(int i = 0; i < N; i++)
		{
			int min = i;
			for(int j = i ; j < N ; j++)
			{
				if(less(a[0][j],a[0][min]))
				{
					min = j;
				}
				exch(a,i,min);
				
				
			}
		}
	}
	
	private static boolean less(Comparable v,Comparable w)
	{
		return v.compareTo(w) < 0;
	}
	private static void exch(Comparable[][] a ,int i ,int j)
	{
		Comparable t = a[0][i];
		a[0][i] = a[0][j];
		a[0][j] = t ;
	}
	private static void show(Comparable[] a )
	{
		for(int i = 0; i < a.length ; i++)
		{
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	public static boolean isSorted(Comparable[] a)
	{
		for(int i = 1 ; i < a.length ; i++)
		{
			if(less(a[i],a[i-1]))
			{
				return false;
			}
		}
		return true;
	}
	
	
}

package edu.algorithms.sort;

public class Twelve {
	public static void main(String[] args) {
		int N = 16;
		Double[] a = new Double[N];
		int M = 4;
		for(int i = 0 ; i < N ;i++)
		{
			a[i] = Math.random();
		}
	
		Double aux1[] = {a[0],a[1],a[2],a[3]};
		Double aux2[] = {a[4],a[5],a[6],a[7]};
		Double aux3[] = {a[8],a[9],a[10],a[11]};
		Double aux4[] = {a[12],a[13],a[14],a[15]};
		Double[][] aux = {aux1,aux2,aux3,aux4};
		Selection.sort(aux);
		
		for(int i =0 ; i < aux.length ; i++)
		{
			for(int j = 0 ; j < M ; j++)
			{
				
			}
		}
		
		System.arraycopy(aux1, 0, a, 0, M-1);
		System.arraycopy(aux2, 0, a, M, 2*M-1);
		System.arraycopy(aux3, 0, a, 2*M, 3*M-1);
		System.arraycopy(aux4, 0, a, 3*M, 4*M-1);
		
		
		
		
		
		for(int i = 0 ; i < M;i++)
		{
			Merge.merge(a[i], a[i], i, i + M, i + 2*M);
		}
		
	}
}

希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序

希尔排序的思想是使数组中任意间隔为h的元素都是有序的.

基于用数组表示的完全三叉树构造堆并修改相应的代码并不困难.对于数组中1至N的N个元素,位置k的节点大于等于位于3k-1,3k,3k+1的节点,小于等于位于(k+1)/3的节点.

甚至对于给定的d,将其修改为任意的d叉树也并不困难,我们需要在树高(log(d)N)和在每个节点的d个子节点找到最大者的代价之间找到折中

a%b定义是(a/b)*b+a%b=a