（2）排序算法——插入排序

港控/mmm° 2022-07-29 09:01 100阅读 0赞

插入排序算法是在已排好序的子数组中反复插入一个新元素，直到整个数组全部排好序。其时间复杂度为O(n\*n).

import java.util.ArrayList;
    import java.util.List;
    public class InsertSort { 
    
        /**对整型数组进行插入排序**/
        public static void sort(int[] list){
            int listLen=list.length;
            for(int i=1;i<listLen;i++){
                int currentElement=list[i];
                int k;
                for(k=i-1;k>=0&&list[k]>currentElement;k--){
                    list[k+1]=list[k];
                }
                list[k+1]=currentElement;
            }
        }
    
        /**对Comparable基本Number包装类型数组进行选择排序 * 利用泛型方法，通过先找出最大数来实现，将最大数放在后面**/
        public static <E extends Comparable<E>> void sort(E[] list) {
            for (int i = 1; i < list.length; i++) {
                /** insert list[i] into a sorted sublist list[0..i-1] so that list[0..i] is sorted. */
                E currentElement = list[i];
                int k;
                for (k = i - 1; k >= 0 && 
                        list[k].compareTo(currentElement) > 0; k--) {
                  list[k + 1] = list[k];
                }
                // Insert the current element into list[k+1]
                list[k + 1] = currentElement;
            }
        }  
    
        /**对List进行插入排序**/
        public static <E extends Comparable<E>> void sort(List<E> list) {
            int listLen=list.size();
            for (int i = 1; i < listLen; i++) {
                E currentElement = list.get(i);
                int k = 0;
                for (k = i - 1; k >= 0 && 
                        list.get(k).compareTo(currentElement) > 0; k--) {
                    list.set(k+1,list.get(k));
                }
                list.set(k+1,currentElement);
            }
        }  
    
        /**主函数测试**/
        public static void main(String[] args){
            Integer[] array={
       1,45,2,5,546,34};
            List<Integer> list=new ArrayList();
            for(int i: array){
                list.add(i);
            }
            sort(list);
            System.out.println(list);
            sort(array);
            print(array);
        }
    
        /**打印数组**/
        public static void print(Comparable[] list){
            for(int i=0;i<list.length;i++){
                System.out.print(list[i]+" ");
            }
            System.out.println();
        }
    
    }