1. 排序算法


  • 内部排序:归并排序、交换排序(冒泡、快排)、插入排序等
  • 外部排序:利用内存和外部存储处理超大数据集。
  • 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

1.1. 约定

待排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo()方法,可以用它来判断两个元素的大小关系。使用辅助函数 less() 和 swap() 来进行比较和交换的操作,使得代码的可读性和可移植性更好。排序算法的成本模型是比较和交换的次数。

public abstract class Sort<T extends Comparable<T>> {

    public abstract void sort(T[] nums);
    // v<w:true or false
    protected boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }
    // 交换
    protected void swap(T[] a, int i, int j) {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

1.2. 交换排序

遍历整个数组,找到最小的那个数,让它和第一个数进行交换。后面依次采用此操作。

public class Selection<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = i; // 当前位置的索引
            for (int j = i + 1; j < nums.length; j++) {
                if (less(nums[j], nums[min])) {//找到最小值的索引
                    min = j;
                }
            }
            swap(nums, min, i);
        }
    }
}

1.3. 冒泡排序

遍历数组,两两交换。

public class Selection<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        // 从最后一位进行
        for (int i = nums.length ; i > 0; i--) {
            // 找到最大的
            for (int j = 1; j < i; j++) {
                if (less(nums[j], nums[j-1])) {
                    swap(nums,j,j-1);
                }
            }
        }
    }
}

results matching ""

    No results matching ""