首页 > 代码库 > 插入排序之Java实现

插入排序之Java实现

2024-07-15 16:01:14   219人阅读

一、声明

　　算法思路部分借鉴于《算法导论》(第三版)，实现过程均属作者原创，转载或引用请注明出处。

 

二、算法概述

    插入排序算法适用于少量元素的排序。插入排序的过程就好比排序一副扑克牌。开始时，左手为空并且桌子上的牌面朝下。然后，每次从桌子上拿走一张扑克牌并将它插入左手中正确的位置。为了找到牌的正确位置，需要从右开始将它与已在手中的每张牌进行比较。每次插入结束后左手中的牌总是排序好的。

 

三、算法思路

1.位码实现

INSERTION-SORT(A)    for j = 2 to A.length        key = A[j]　　　　// 将桌面的牌拿至右手        i = j -1　　　　　// 左手中已经排序好的牌的数量        while i > 0 and A[i] > key　　　　// 将右手中的key牌与左手中的牌从右到左进行比较            A[i+1] = A[i]            i = i - 1        A[i+1] = key　　　　// 将右手中的牌插入到左手中

 

 

四、算法分析

　　最坏情况的运行时间为Θ(n^2)，所以不适合大量输入的排序。

 

五、算法实现

1.InsertionSort类

　　InsertSort是抽象类，需要实例化时需要实现public abstract int elemCompare(T a, T b)方法，此方法描述了比较类型T两个实例大小的策略。调用srot方法即可对ArrayList<T>进行插入排序。

import java.util.ArrayList;
/**
 * 作者原创，引用请注明出处
 * @author ChameleonChen
 */public abstract class InsertionSort<T> {        public static final int A_GREATER_THAN_B = 1;        public static final int A_LESS_THAN_B = 2;        public static final int A_EQUALS_B = 3;        /**     * 实现a b 两个元素的比较策略。     * ex:     *     int elemCompare(Integer a, Integer b) {     *         if (a > b) return InsertionSort.A_GREATER_THAN_B;     *         else if (a < b) return InsertionSort.A_LESS_THAN_B;     *         else return InsertionSort.A_EQUALS_B;     *     }     * @param a     * @param b     * @return a大于b，返回InsertionSort.A_GREATER_THAN_B；a小于b，返回InsertionSort.A_LESS_THAN_B     *         a等于b，返回InsertionSort.A_EQUALS_B.     */    public abstract int elemCompare(T a, T b);      public static final int NON_DECREASING_SORT = 1;    // 非递减排序        public static final int NON_INCREASING_SORT = 2;    // 非递增排序        /**     * 对elems进行排序，改变其在内存中的值。     * 实现算法如下：     * INSERTION-SORT(A)     *   for j = 2 to A.length     *       key = A[j]     *        *       i = j - 1     *       while i > 0 and A[i] > key     *           A[i+1] = A[i]     *           i = i - 1     *       A[i+1] = key     *      * @param elems     * @param sortType 排序的类型：非递减排序 InsertionSort.NON_DECREASING_SORT；     * 非递增排序InsertionSort.NON_INCREASING_SORT     */    public void sort(ArrayList<T> elems, int sortType) {        if (elems == null){            throw new NullPointerException("the elems can not be null");        }                int expected;        switch (sortType) {        case NON_DECREASING_SORT:            expected = A_GREATER_THAN_B;            break;        case NON_INCREASING_SORT:            expected = A_LESS_THAN_B;            break;        default :            throw new IllegalArgumentException("the sortType‘s value is illegal");        }                T temp;        for (int j=1,i; j<elems.size(); j++) {            temp = elems.get(j);                        i = j - 1;            while (i>=0 && elemCompare(elems.get(i), temp) == expected) {                elems.set(i+1, elems.get(i));                i = i - 1;            }            elems.set(i+1, temp);        }    }}

 


联系
我们