关于排序算法, 常见的大致有: 冒泡排序, 插入排序, 选择排序, 快速排序, 归并排序, 桶排序, 计数排序等. 每一种排序算法都有它们各自的优劣和适用场景. 一般可以从这么几个角度来衡量排序算法:
1. 最好时间复杂度, 最坏时间复杂度, 平均时间复杂度
2. 是否是原地排序算法: 原地排序算法, 指空间复杂度为 O(1)
3. 是否是稳定排序算法: 稳定排序算法, 指如果待排序序列中有值相等的元素, 经过排序之后, 值相等元素的顺序保持不变
关于冒泡排序算法 (Bubble sort):
代码实现:
- /**
- * 冒泡排序算法实现:
- * 1. 它是基于比较, 与交换实现的排序算法
- * 2. 它是原地排序算法: 只涉及相邻两个数的交换操作, 常量级的临时空间 O(1)
- * 3. 它是稳定排序算法: 如果相邻两个元素值相等, 则不执行交换操作, 可以保证排序后的顺序不变
- * 4. 它的最好时间复杂度: O(n)
- * 5. 它的最后时间复杂度: O(n^2)
- * 6. 它的平均时间复杂度: O(n^2)
- *
- * 参数: a 是待排序序列, n 是序列大小
- */
- public static void bubbleSort_1(int[] a,int n){
- if(n <= 1) return;
- for(int i=0;i<n;i++){// 冒泡次数
- for(int j=0;j<n-i-1;j++){// 比较交换次数
- if(a[j]>a[j+1]){
- int tmp=a[j];
- a[j]=a[j+1];
- a[j+1]=tmp;
- }
- }
- }
- }
代码实现 (优化版本):
- /**
- * 优化思路:
- * 1. 每次冒泡操作, 都是先比较, 再交换
- * 2. 如果某次冒泡操作, 没有执行交换操作, 则说明数据已经有序, 不需要再进行剩下的冒泡操作
- *
- * @param a 待排序序列
- * @param n 序列大小
- */
- public static void bubbleSort_2(int[] a,int n){
- if(n <= 1) return;
- for(int i=0;i<n;i++){// 冒泡次数
- boolean flag = false;// 提前终止冒泡操作标识
- for(int j=0;j<n-i-1;j++){// 比较交换次数
- if(a[j]>a[j+1]){
- int tmp=a[j];
- a[j]=a[j+1];
- a[j+1]=tmp;
- flag=true;// 有交换操作
- }
- }
- if(!flag) break;// 没有交互操作, 提前终止余下的冒泡操作
- }
- }
来源: http://www.bubuko.com/infodetail-3066528.html