排序算法

Author Avatar ZTFtrue 发表于 • 2018年03月06日 10:40 • 共 • 559 • 次浏览

选择排序

从待排序的数据元素中选择最小(或最大)的一个元素作为第一个元素,然后再从剩下的元素中选择最小(或最大)的一个元素作为第二个元素,以此循环,直到所有元素排完为止。简单选择排序是不稳定排序。

复杂度为O(n2)

冒泡排序

 对相邻的元素进行两两比较,如果大小与预期的相反则进行交换,这样,每一趟会将最小或最大的元素放到末端,最终达到排序

插入排序

每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。

public static <T extends Comparable<? super T>> void insertSort(T[] array) {
    int j;
    // 前i个元素是已排序的
    for (int i = 1; i < array.length; i++) {
        T tmp = array[i]; // 暂存第i个元素
        // 第i个元素和依次和之前的元素比较, 比 tmp 小就"上滤"
        for (j = i; j > 0 && tmp.compareTo(array[j - 1]) < 0; j--) {
            array[j] = array[j - 1];
        }
        array[j] = tmp;
    }
}

以上内容参考

快速排序

我以前想到过二分法排序和这个一样

  1. 先从数列中取出一个数作为基准数

  2. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边

  3. 再对左右区间重复第二步,直到各区间只有一个数
    参考链接

最后编辑于 • 2018年03月06日 11:17 •  

你尚未登录,无法进行回复。