包括插入排序、冒泡排序、快速排序、希尔排序、堆排序、归并排序和简单选择排序,用Java实现

  • 定义接口
public interface arrSorter {
    public static <T extends Comparable<T>> void insertSort(T[] t) {}
    public static <T extends Comparable<T>> void shellSort(T[] t) {}
    public static <T extends Comparable<T>> void BubbleSort(T[] t) {}
    public static <T extends Comparable<T>> void quickSort(T[] t) {}
    public static <T extends Comparable<T>> void selectSort(T[] t) {}
    public static <T extends Comparable<T>> void heapSort(T[] t) {}
    public static <T extends Comparable<T>> void mergeSort(T[] t) {}
}
  • 接口实现
public class arrSort implements arrSorter{

    /*
    * 插入排序 直接插入排序算法,稳定 升序
    * 
    * @param t 要排序的数组
    */
    public static <T extends Comparable<T>> void insertSort(T[] t) {
        if (t.length >= 2) {
            for (int i = 1; i < t.length; i++) {
                 T var1 = t[i];// 要插入的变量
                 for (int j = 0; j < i; j++) {
                     if (var1.compareTo(t[j]) < 0) {
                         for (int k = i; k > j; k--) {
                             t[k] = t[k - 1];
                         }
                         t[j] = var1;
                         break;
                      }
                  }
              }
      }
    }

    /*
     * 插入排序 希尔排序算法,不稳定 升序
     * 
     * @param t 要排序的数组
     */
    public static <T extends Comparable<T>> void shellSort(T[] t) {
        int gap;// 步长
        int n = t.length;
        for (gap = n / 2; gap > 0; gap /= 2) {
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < n; j += gap) {
                    if (t[j].compareTo(t[j - gap]) < 0) {
                        T temp = t[j];
                        int k = j - gap;
                        while (k >= 0 && t[k].compareTo(temp) > 0) {
                            t[k + gap] = t[k];
                            k -= gap;
                        }
                        t[k + gap] = temp;
                    }
                }
            }
        }
    }

    /*
     * 交换排序 冒牌排序 稳定 升序
     * 
     * @param t 要排序的数组
     */
    public static <T extends Comparable<T>> void BubbleSort(T[] t) {
        // boolean flag;
        for (int i = 1; i < t.length; i++) {
            for (int j = t.length - 1; j > i; j--) {
                if (t[j - 1].compareTo(t[j]) > 0) {
                    T temp = t[j];
                    t[j] = t[j - 1];
                    t[j - 1] = temp;
                }
            }
        }
    }

    /*
     * 交换排序 快速排序 不稳定 升序
     * 
     * @param t 要排序的数组
     */
    public static <T extends Comparable<T>> void quickSort(T[] t) {
        preQuickSort(t, 0, t.length - 1);
    }

    private static <T extends Comparable<T>> void preQuickSort(T[] t, int l, int r) {
        int left = l, right = r;
        if (left <= right) {
            T temp = t[left];// 以第一个元素为基准
            while (left != right) {
                while (right > left && t[right].compareTo(temp) >= 0)
                    right--;// 从右往左扫描,找到第一个比基准元素小的元素
                t[left] = t[right];
                while (left < right && t[left].compareTo(temp) <= 0)
                    left++;// 从左往右扫描,找到第一个比基准元素大的元素
                t[right] = t[left];
            }
            t[right] = temp;// 基准元素归位
            preQuickSort(t, l, left - 1); // 对基准元素左边的元素进行递归排序
            preQuickSort(t, right + 1, r); // 对基准元素右边的进行递归排序
        }
    }

    /*
     * 选择排序 简单选择排序 不稳定 升序
     * 
     * @param t 要排序的数组
     */
    public static <T extends Comparable<T>> void selectSort(T[] t) {
        for (int i = 0; i < t.length; i++) {
            int min = i;
            for (int j = i; j < t.length; j++) {
                if (t[min].compareTo(t[j]) > 0)
                    min = j;
            }
            T temp = t[min];
            t[min] = t[i];
            t[i] = temp;
        }
    }

    /*
     * 选择排序 堆排序,基于最小队 不稳定 升序
     * 
     * @param t 要排序的数组
     */
    public static <T extends Comparable<T>> void heapSort(T[] t) {
        for (int i = t.length / 2 - 1; i >= 0; i--)
            adjustHeap(t, i, t.length - 1);
        for (int i = t.length - 1; i > 0; i--) {
            T temp = t[0];
            t[0] = t[i];
            t[i] = temp;
            adjustHeap(t, 0, i - 1);
        }
    }

    /*
     * 最小堆的调整过程
     * 
     * @param t 要排序的数组
     * 
     * @param start 调节点的起始位置,一般为0,即从第一个节点开始
     * 
     * @param end 截止范围,一般为最后一个节点的索引
     */
    private static <T extends Comparable<T>> void adjustHeap(T[] t, int start, int end) {
        int cur = start, left = 2 * start + 1;
        T temp = t[cur];
        for (; left < end; cur = left, left = 2 * left + 1) {
            if (left < end && t[left].compareTo(t[left + 1]) <= 0)
                left++;
            if (temp.compareTo(t[left]) > 0)
                break;
            else {
                t[cur] = t[left];
                t[left] = temp;
            }
        }
    }

    /*
     * 二路归并排序 稳定 升序
     * 
     * @param t 要排序的数组
     */
    public static <T extends Comparable<T>> void mergeSort(T[] t) {
        T[] temp = t.clone();
        preMergSort(t, 0, t.length - 1, temp);

    }

    private static <T extends Comparable<T>> void preMergSort(T[] t, int first, int last, T[] temp) {
        if (first < last) {        
            int mid = (first + last) / 2;
            preMergSort(t, first, mid, temp);
            preMergSort(t, mid + 1, last, temp);
            mergeArr(t, first, mid, last, temp);
        }
    }

    private static <T extends Comparable<T>> void mergeArr(T[] t, int first, int mid, int last, T[] temp) {
        int i = first, j = mid + 1, m = mid, n = last, k = 0;
        while (i <= m && j <= n) {
            if (t[i].compareTo(t[j]) <= 0)
                temp[k++] = t[i++];
            else
                temp[k++] = t[j++];
        }
        while (i <= m)
            temp[k++] = t[i++];
        while (j <= n)
            temp[k++] = t[j++];
        for (i = 0; i < k; i++)
            t[first + i] = temp[i];
    }

}