排序算法
选择排序
从待排序的数据元素中选择最小(或最大)的一个元素作为第一个元素,然后再从剩下的元素中选择最小(或最大)的一个元素作为第二个元素,以此循环,直到所有元素排完为止。简单选择排序是不稳定排序。
复杂度为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;
}
}
快速排序
我以前想到过二分法排序和这个一样
-
先从数列中取出一个数作为基准数
-
分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
-
再对左右区间重复第二步,直到各区间只有一个数
参考链接
你尚未登录,无法进行回复。