《Java语言程序设计与数据结构》编程练习答案（第二十三章）（一）

英文名：Introduction to Java Programming and Data Structures, Comprehensive Version, 11th Edition

23.1

public class book {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);


    }

    public static <T extends Comparable<T>> void bubbleSort(T[] list){
        for(int i=list.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(list[j].compareTo(list[j+1]) > 0){
                    T tmp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = tmp;
                }
            }
        }
    }

    public static <T> void bubbleSort (T[] list, Comparator<? super T> comparator){
        for(int i=list.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(comparator.compare(list[j],list[j+1]) > 0){
                    T tmp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = tmp;
                }
            }
        }
    }
}

23.2

public class book {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);


    }

    public static <T extends Comparable<T>> void mergeSort(T[] list){
        if(list.length > 1){
            ArrayList<T> tmpLeft = new ArrayList<>(Arrays.asList(list).subList(0, (int) (list.length / 2)));
            T[] firstHalf = (T[]) tmpLeft.toArray();
            mergeSort(firstHalf);

            ArrayList<T> tmpRight = new ArrayList<>(Arrays.asList(list).subList(list.length / 2, list.length));
            T[] secondHalf = (T[]) tmpRight.toArray();
            mergeSort(secondHalf);

            merge(firstHalf, secondHalf, list);
        }
    }

    public static <T extends Comparable<T>>void merge(T[] list1, T[] list2, T[]tmp){
        int current1 = 0;
        int current2 = 0;
        int current3 = 0;
        while(current1 < list1.length && current2 < list2.length){
            if(list1[current1].compareTo(list2[current2]) < 0){
                tmp[current3++] = list1[current1++];
            }else{
                tmp[current3++] = list2[current2++];
            }
        }

        while(current1 < list1.length)
            tmp[current3++] = list1[current1++];
        while(current2 < list2.length)
            tmp[current3++] = list2[current2++];
    }

    public static <T> void mergeSort(T[] list, Comparator<T> comparator){
        if(list.length > 1){
            ArrayList<T> tmpLeft = new ArrayList<>(Arrays.asList(list).subList(0, (int) (list.length / 2)));
            T[] firstHalf = (T[]) tmpLeft.toArray();
            mergeSort(firstHalf, comparator);

            ArrayList<T> tmpRight = new ArrayList<>(Arrays.asList(list).subList(list.length / 2, list.length));
            T[] secondHalf = (T[]) tmpRight.toArray();
            mergeSort(secondHalf, comparator);

            merge(firstHalf, secondHalf, list, comparator);
        }
    }

    public static <T>void merge(T[] list1, T[] list2, T[]tmp, Comparator<T> comparator){
        int current1 = 0;
        int current2 = 0;
        int current3 = 0;
        while(current1 < list1.length && current2 < list2.length){
            if(comparator.compare(list1[current1], list2[current2]) < 0){
                tmp[current3++] = list1[current1++];
            }else{
                tmp[current3++] = list2[current2++];
            }
        }

        while(current1 < list1.length)
            tmp[current3++] = list1[current1++];
        while(current2 < list2.length)
            tmp[current3++] = list2[current2++];
    }
}

23.3

public class book {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);


    }

    public static <T extends Comparable<T>> void quickSort(T[] list){
        quickSort(list, 0, list.length-1);
    }

    public static <T extends Comparable<T>> void quickSort(T[] list, int first, int last){
        if(last > first){
            int pivotIndex = partition(list,first, last);
            quickSort(list, first, pivotIndex-1);
            quickSort(list, pivotIndex+1, last);
        }
    }

    public static <T extends Comparable<T>>int partition(T[] list, int first, int last){
        T pivot = list[first];
        int low = first + 1;
        int high = last;
        while(high > low){
            while(low <= high && list[low].compareTo(pivot) <= 0)
                low++;

            while(low <= high && list[high].compareTo(pivot) > 0)
                high--;

            if(high > low){
                T tmp = list[high];
                list[high] = list[low];
                list[low] = tmp;
            }
        }

        while (high > first && list[high].compareTo(pivot) >= 0)
            high--;

        if(pivot.compareTo(list[high]) > 0){
            list[first] = list[high];
            list[high] = pivot;
            return high;
        }else{
            return first;
        }
    }

    public static <T> void quickSort(T[] list, Comparator<T> comparator){
        quickSort(list, 0, list.length-1, comparator);
    }

    public static <T> void quickSort(T[] list, int first, int last, Comparator<T> comparator){
        if(last > first){
            int pivotIndex = partition(list,first, last, comparator);
            quickSort(list, first, pivotIndex-1, comparator);
            quickSort(list, pivotIndex+1, last, comparator);
        }
    }

    public static <T>int partition(T[] list, int first, int last, Comparator<T> comparator){
        T pivot = list[first];
        int low = first + 1;
        int high = last;
        while(high > low){
            while(low <= high && comparator.compare(list[low], pivot) <= 0)
                low++;

            while(low <= high && comparator.compare(list[high],pivot) > 0)
                high--;

            if(high > low){
                T tmp = list[high];
                list[high] = list[low];
                list[low] = tmp;
            }
        }

        while (high > first && comparator.compare(list[high], pivot) >= 0)
            high--;

        if(comparator.compare(pivot, list[high]) > 0){
            list[first] = list[high];
            list[high] = pivot;
            return high;
        }else{
            return first;
        }
    }
}

23.4

public class book {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);


    }
    public static void quickSort(int[] list){
        quickSort(list, 0, list.length-1);
    }

    public static void quickSort(int[] list, int first, int last){
        if(last > first){
            int pivotIndex = partition(list, first, last);
            quickSort(list, first, pivotIndex-1);
            quickSort(list, pivotIndex+1, last);
        }
    }

    public static int partition(int[] list, int first, int last){
        int mid = (first + last) / 2;
        if((list[first]<list[last] && list[first]>list[mid])||(list[first]<list[mid] && list[first]>list[last])){

        }else if((list[mid]<list[first] && list[mid]>list[last])||(list[mid]<list[last] && list[mid]>list[first])){
            int tmp = list[first];
            list[first] = list[mid];
            list[mid] = tmp;
        }else{
            int tmp = list[first];
            list[first] = list[last];
            list[last] = tmp;
        }
        int pivot = list[first];
        int low = first + 1;
        int high = last;
        while(high > low){
            while(low <= high && list[low] <= pivot)
                low++;
            while(low <= high && list[high] > pivot)
                high--;

            if(high > low){
                int tmp = list[high];
                list[high] = list[low];
                list[low] = tmp;
            }
        }

        while(high > first && list[high] >= pivot)
            high--;

        if(pivot > list[high]){
            list[first] = list[high];
            list[high] = pivot;
            return high;
        }else{
            return first;
        }
    }
}

23.5

public class book {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);


    }

}

class HeapWithComparator<T> {
    private ArrayList<T> list = new ArrayList<>();
    private Comparator<? super T>comparator;


    public HeapWithComparator(){
        this.comparator = new Comparator<T>() {
            @Override
            public int compare(T o1, T o2) {
                return o1.toString().compareTo(o2.toString());
            }
        };
    }

    public HeapWithComparator(Comparator<? super T> comparator){
        this.comparator = comparator;
    }

    public void add(T newObject){
        list.add(newObject);
        int currentIndex = list.size()-1;
        while(currentIndex > 0){
            int parentIndex = (currentIndex-1) / 2;
            if(comparator.compare(list.get(currentIndex),list.get(parentIndex)) > 0){
                T tmp = list.get(currentIndex);
                list.set(currentIndex, list.get(parentIndex));
                list.set(parentIndex, tmp);
            }else{
                break;
            }
            currentIndex = parentIndex;
        }
    }

    public T remove(){
        if(list.size() == 0)
            return null;
        T removeObject = list.get(0);
        list.set(0, list.get(list.size()-1));
        list.remove(list.size()-1);

        int currentIndex = 0;
        while(currentIndex < list.size()){
            int leftChildIndex = 2*currentIndex + 1;
            int rightChildIndex = 2*currentIndex + 2;

            if(leftChildIndex >= list.size())
                break;
            int maxIndex = leftChildIndex;
            if(rightChildIndex < list.size()){
                if(comparator.compare(list.get(maxIndex), list.get(rightChildIndex)) < 0){
                    maxIndex = rightChildIndex;
                }
            }
            
            if(comparator.compare(list.get(currentIndex), list.get(maxIndex)) < 0){
                T tmp = list.get(maxIndex);
                list.set(maxIndex, list.get(currentIndex));
                list.set(currentIndex, tmp);
                currentIndex = maxIndex;
            }
            else{
                break;
            }
        }
        return removeObject;
    }
    
    public int getSize(){
        return list.size();
    }

}

23.6

public class book {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);


    }
    public static boolean ordered(int[] list){
        boolean isOrdered = true;
        for(int i=0;i<list.length-1;i++){
            if(list[i] > list[i+1]){
                isOrdered = false;
                break;
            }
        }
        return isOrdered;
    }

    public static boolean ordered(int[] list, boolean ascending){
        boolean isOrdered = true;
        if(ascending){
            for(int i=0;i<list.length-1;i++){
                if(list[i] > list[i+1]){
                    isOrdered = false;
                    break;
                }
            }
        }else{
            for(int i=0;i<list.length-1;i++){
                if(list[i] < list[i+1]){
                    isOrdered = false;
                    break;
                }
            }
        }
        return isOrdered;
    }

    public static boolean ordered(double[] list){
        boolean isOrdered = true;
        for(int i=0;i<list.length-1;i++){
            if(list[i] > list[i+1]){
                isOrdered = false;
                break;
            }
        }
        return isOrdered;
    }

    public static boolean ordered(double[] list, boolean ascending){
        boolean isOrdered = true;
        if(ascending){
            for(int i=0;i<list.length-1;i++){
                if(list[i] > list[i+1]){
                    isOrdered = false;
                    break;
                }
            }
        }else{
            for(int i=0;i<list.length-1;i++){
                if(list[i] < list[i+1]){
                    isOrdered = false;
                    break;
                }
            }
        }
        return isOrdered;
    }

    public static <T extends Comparable<T>> boolean ordered(T[] list){
        boolean isOrdered = true;
        for(int i=0;i<list.length-1;i++){
            if(list[i].compareTo(list[i+1]) > 0){
                isOrdered = false;
                break;
            }
        }
        return isOrdered;
    }

    public static <T extends Comparable<T>> boolean ordered(T[] list, boolean ascending){
        boolean isOrdered = true;
        if(ascending){
            for(int i=0;i<list.length-1;i++){
                if(list[i].compareTo(list[i+1]) > 0){
                    isOrdered = false;
                    break;
                }
            }
        }else{
            for(int i=0;i<list.length-1;i++){
                if(list[i].compareTo(list[i+1]) < 0){
                    isOrdered = false;
                    break;
                }
            }
        }
        return isOrdered;
    }

    public static <T> boolean ordered(T[] list, Comparator<? super T> comparator){
        boolean isOrdered = true;
        for(int i=0;i<list.length-1;i++){
            if(comparator.compare(list[i], list[i+1]) > 0){
                isOrdered = false;
                break;
            }
        }
        return isOrdered;
    }

    public static <T> boolean ordered(T[] list, Comparator<? super T> comparator, boolean ascending){
        boolean isOrdered = true;
        if(ascending){
            for(int i=0;i<list.length-1;i++){
                if(comparator.compare(list[i], list[i+1]) > 0){
                    isOrdered = false;
                    break;
                }
            }
        }else {
            for(int i=0;i<list.length-1;i++){
                if(comparator.compare(list[i], list[i+1]) < 0){
                    isOrdered = false;
                    break;
                }
            }
        }
        return isOrdered;
    }
}