算法面试题（二）-白红宇

初级

1package test; 2public class Test6 { 3 4    public static void main(String[] args) {             5        int[]arr=new int[]{15,2,21,6,4,25,77,43}; 6        int[] maoPao = maoPao(arr); 7        for (int i : maoPao) { 8            System.out.print(i+" "); 9        }10    }1112    /**13     * 冒泡排序方法14     * @param arr   要排序的数组15     * @return      排序之后的数组16     */17    public static int[] maoPao(int[] arr){18        //前一个元素19        for (int i = 0; i < arr.length-1; i++) {20            //后一个元素21            for (int j = i+1; j < arr.length; j++) {22                //如果后面的元素小于前边的元素，互换位置23                if(arr[j]

优化级

1package test; 2 3    public class Test6 { 4 5        public static void main(String[] args) { 6 7            int[]arr=new int[]{15,2,21,6,4,25,77,43}; 8 9            int[] maoPao2 = maoPao2(arr);10            for (int i : maoPao2) {11                System.out.print(i+" ");12            }13        }1415        /**16         * 如果数组已经排序好了，i只执行一次循环17         * @param arr18         * @return19         */20        public static int[] maoPao2(int[] arr){21            if(arr==null)22                return null;2324            boolean isSort;25            Long start = System.currentTimeMillis();26            for (int i = 0; i < arr.length; i++) {27                isSort=true;28                for (int j = 1; j < arr.length-i; j++) {29                    if(arr[j-1]>arr[j]){30                        int temp=arr[j-1];31                        arr[j-1] = arr[j];32                        arr[j] = temp;33                        isSort=false;34                    }35                }3637                Long end = System.currentTimeMillis();38                if(isSort)39                System.out.println("用时："+(end-start));40                    break;41            }42            return arr;43        }44    }

高逼格的代码

接口：

1import java.util.Comparator; 2/** 3 * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换) 4 */ 5public interface Sorter { 6   /** 7    * 排序 8    * @param list 待排序的数组 9    */10   public 
     
      > void sort(T[] list);11   /**12    * 排序13    * @param list 待排序的数组14    * @param comp 比较两个对象的比较器15    */16   public 
      
        void sort(T[] list, Comparator
       
         comp);17}

实现类：

1import java.util.Comparator; 2/** 3 * 冒泡排序 4 * 5 */ 6public class BubbleSorter implements Sorter { 7    @Override 8    public 
     
      > void sort(T[] list) { 9        boolean swapped = true;10        for (int i = 1, len = list.length; i < len && swapped; ++i) {11            swapped = false;12            for (int j = 0; j < len - i; ++j) {13                if (list[j].compareTo(list[j + 1]) > 0) {14                    T temp = list[j];15                    list[j] = list[j + 1];16                    list[j + 1] = temp;17                    swapped = true;18                }19            }20        }21    }22    @Override23    public 
      
        void sort(T[] list, Comparator
       
         comp) {24        boolean swapped = true;25        for (int i = 1, len = list.length; i < len && swapped; ++i) {26            swapped = false;27            for (int j = 0; j < len - i; ++j) {28                if (comp.compare(list[j], list[j + 1]) > 0) {29                    T temp = list[j];30                    list[j] = list[j + 1];31                    list[j + 1] = temp;32                    swapped = true;33                }34            }35        }36    }37}

原文发布时间为：2018-09-14

本文作者：

本文来自云栖社区合作伙伴"，了解相关信息可以关注“”。