目录
十大排序算法总结
一、冒泡排序
- 身世曰：冒泡排序可以誉为程序员跨入算法门槛的第一步，相信大家一定被冒泡排序一直萦绕在耳边。【且听冒泡吟】，冒泡乃排序家族之太上长老，掌门人不为过之。
- 闻之也：冒泡排序（Bubble Sort），乃计算机科学领域排序算法的简简易者。
- 知其身：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。【百度百科】
- 名由来：这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。【百度百科】
附实录
/*
* 对数组a中的元素排序，改良时间复杂度，空间换时间，冗余flag变量
*/
public static void bubbleSort(Integer[] a) {
for (int i = 0; i < a.length - 1; i++) { // 外层循环，负责控制比较趟数
// 标志位，记录本趟循环是否进行了交换（即是否整体已经有序）
boolean flag = false;
for (int j = 0; j < a.length - 1 - i; j++) { // 内层循环，比较为冒泡的数
if (greater(a[j], a[j + 1])) {
exch(a, j, j + 1);
flag = true; // 记录已经交换过
}
}
if (!flag) break; // 本趟未交换，已经有序退出外层循环
}
}
知论之
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
赞曰
- 时间复杂度
- 最优：O(n) ，若待排序序列和期望序列顺序一致，则只许挨着扫描
- 最坏：O(n^2)
二、选择排序
- 身世曰：冒泡排序可以誉为程序员跨入算法门槛的第一步，相信大家一定被冒泡排序一直萦绕在耳边。【且听冒泡吟】，冒泡乃排序家族之太上长老，掌门人不为过之。
- 闻之也：冒泡排序（Bubble Sort），乃计算机科学领域排序算法的简简易者。
- 知其身：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。【百度百科】
- 名由来：这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。【百度百科】
附实录
附录
具者类也：排序算法公用（交换和比较）
public static class CommonSortUtils {
/*
数组元素 i 和 j 交换位置方法
* */
public static void exch(Comparable[] a, int i, int j) {
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/*
* 比较是否a > b的方法
* */
public static boolean greater(Comparable a, Comparable b) {
return a.compareTo(b) > 0;
}
/*
* 比较是否a < b的方法
* */
public static boolean less(Comparable a, Comparable b) {
return b.compareTo(a) > 0;
}
}