冒泡排序
由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。
冒泡排序算法的运作如下:
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
/** * 冒泡排序 * * @param ts */ public static <T extends Comparable<? super T>> void BubbleSort(T[] ts) { // 如果一次都没有交换,表示已经排好序 boolean isSorted = false; // 从0到i中找出最大值 for (int i = ts.length - 1; i > 0; i--) { isSorted = true; for (int y = 0; y < i; y++) { if (ts[y].compareTo(ts[y + 1]) > 0) { isSorted = false; T temp = ts[y + 1]; ts[y + 1] = ts[y]; ts[y] = temp; } } if (isSorted) break; } }
1. 时间复杂度:O(n^2)
冒泡排序耗时的操作有:比较 + 交换赋值。时间复杂度如下:
1) 最好情况:序列是升序排列,在这种情况下,需要进行的比较操作为(n-1)次。交换操
作为0次。即O(n)
2) 最坏情况:序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。交换操作数和比
较操作数一样。即O(n^2)
3) 渐进时间复杂度(平均时间复杂度):O(n^2)
2. 空间复杂度:O(1)
3. 稳定性
冒泡排序是稳定的,不会改变相同元素的相对顺序。
快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来
基本思想参考:http://ahalei.blog.51cto.com/4767671/1365285
本例中排序思想:补充快排的一些细节。
1)从ts[left]、ts[center]、ts[right]选出中间值作为基准值。
好处:三个元素中最小者被分在ts[left],而这正是分割阶段应该将它放到的位置。三
个元素中最大着被分在ts[right],这也是正确位置,因为它大于基准值。因此我
们可以把基准放到a[right-1]。
2)左面开始位置 i ,右面开始位置 j
3)经过第1步,left<基准,right>基准,基准位置在[right-1] 。因此 i = left+1 ,j = right-2
4)快排是用递归来实现的,所以到最后,会经常出现小数组排序的情况,即排序区域只有〈=20个元素。对于小的数组,快排不如插入排序。本例中采用一种好的截止范围是N=10,这种做法刚好避免了在三个元素取中值而实际上却只有一个或两个元素的情况。
/** * 快速排序 */ public static <T extends Comparable<? super T>> void quickSort(T[] ts) { quickSort(ts, 0, ts.length - 1); } /** * 主例程 */ private static <T extends Comparable<? super T>> void quickSort(T[] ts, int left, int right) { if (left + 10 <= right) { T pivot = median3(ts, left, right); int i = left, j = right - 1; for (;;) {// 开始i,j交换 while (ts[++i].compareTo(pivot) < 0) {}// i>=pivot stop while (ts[--j].compareTo(pivot) > 0) {}// j<=pivot stop if (i < j) swapRef(ts, i, j);// i,j交换 else break; } swapRef(ts, i, right - 1); // 恢复基准值位置 quickSort(ts, left, i - 1); // 排序小元素 quickSort(ts, i + 1, right);// 排序大元素 } else //排序元素个数小于10,采用直接插入排序 insertSort(ts, left, right); } /** * left\right\center 取中值=基准(pivot) */ private static <T extends Comparable<? super T>> T median3(T[] ts, int left, int right) { int center = (left + right) / 2; // 两步确定3个值中的最小,放到left位置 if (ts[center].compareTo(ts[left]) < 0) swapRef(ts, center, left); if (ts[right].compareTo(ts[left]) < 0) swapRef(ts, right, left); if (ts[right].compareTo(ts[center]) < 0) swapRef(ts, center, right); // 基准 位置 swapRef(ts, center, right - 1); return ts[right - 1]; } /** * 交换元素位置 */ private static <T extends Comparable<? super T>> void swapRef(T[] ts, int x, int y) { T temp = ts[x]; ts[x] = ts[y]; ts[y] = temp; } /** * 插入排序 */ private static <T extends Comparable<? super T>> void insertSort(T[] ts, int left, int right) { int y; for (int i = left + 1; i <= right; i++) { T temp = ts[i]; for (y = i; y > left && temp.compareTo(ts[y - 1]) < 0; y--) ts[y] = ts[y - 1]; ts[y] = temp; } }
1. 时间复杂度:O(n^2)
最差时间复杂:O(n^2)
最优时间复杂:O(nlogn)
平均时间复杂:O(nlogn)
2. 空间复杂度:
O(n log n)
3. 稳定性
不稳定。
简单性能测试
/** * 简单的 * * @param args */ public static void main(String[] args) { int num = 1000000; Integer[] inters = new Integer[num]; Random inter = new Random(); for (int i = 0; i < num; i++) { inters[i] = inter.nextInt(num); } long tims = System.currentTimeMillis(); quickSort(inters); tims -= System.currentTimeMillis(); System.err.println(tims * -1); // System.err.println(Arrays.toString(inters)); }
排序方法\数组大小 | 1000 | 5000 | 10000 | 50000 | 10w | 100w | 1000w |
直接插入排序 | 17 | 50 | 130 | 2.4s | 10s | 太长 | 太长 |
二分for循环 | 8 | 43 | 60 | 950 | 5s | 太长 | 太长 |
二分java本地copy | 1 | 10 | 23 | 165 | 470 | 50s | 太长 |
选择排序 | 29 | 45 | 104 | 2.3s | 10s | 太长 | 太长 |
冒泡排序 | 35 | 106 | 320 | 8s | 38s | 太长 | 太长 |
希尔增量排序 | 2 | 11 | 20 | 38 | 55 | 1s | 20s |
堆排序 | 3 | 15 | 20 | 28 | 40 | 600 | 10s |
快速排序 | 1 | 9 | 19 | 80(比较不稳定) | 130(不稳) | 250 | 3.7s |
相关推荐
其中实现了冒泡排序与快速排序
java实现插入排序,交换排序。插入排序包括直接插入排序,折半插入排序和希尔排序。交换排序包括冒泡排序。
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
实现了四类排序算法,插入排序、交换排序、选择排序、归并排序,详情请看文档,其中 树形选择排序算法--选择排序、 堆排序--选择排序 这两种算法还没实现,有兴趣的自行解决
Java中排序算法是非常重要的一部分,这里简单分析下冒泡排序和快速排序的实现思路及其代码实现。 常见排序算法时间复杂度表 排序法 平均时间复杂度 最差情形 稳定度 额外空间 备注 冒泡排序 O(n^2) O(n^2) ...
Java各种排序算法集合: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(箱排序、基数排序)
以下排序的Java代码实现: 插入排序(直接插入排序、二分法插入排序、希尔排序) 选择排序(简单选择排序、堆排序) 交换排序(冒泡排序、快速排序) 归并排序 基数排序
2冒泡排序 * 基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数, 自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。 即:每当两相邻的数比较后发现它们的排序与排序...
- 算法的种类:插入排序(直接插入排序,希尔排序,折半插入排序),选择排序(直接选择排序,堆排序(升序/最大堆)),交换排序(冒泡排序,快速排序),归并排序,分配排序(基数排序) - 算法的时间复杂度 - 算法的空间...
日常操作中常见的排序方法有:冒泡排序、快速排序、选择排序、插入排序、希尔排序,甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一...
1.插入排序(直接插入排序、折半插入排序、希尔排序); 2.交换排序(冒泡泡排序、快速排序); 3.选择排序(直接选择排序、堆排序); 4.归并排序;5.基数排序。
排序算法,JAVA中的快速排序,交换排序,冒泡排序,选择排序等算法的分析
java基本排序算法实现,包括快速 选择 插入 希尔 堆 冒泡 交换
2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(箱排序、基数排序) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 不...
交换排序(冒泡泡排序、快速排序); * 3.选择排序(直接选择排序、堆排序); * 4.归并排序; * 5.基数排序。 * * 关于排序方法的选择: * (1)若n较小(如n≤50),可采用直接插入或直接选择排序。 * 当记录...
交换排序(冒泡泡排序、快速排序); * 3.选择排序(直接选择排序、堆排序); * 4.归并排序; * 5.基数排序。 * 关于排序方法的选择: * (1)若n较小(如n≤50),可采用直接插入或直接选择排序。 * 当...
冒泡排序实际上是将数据从右至左排序完成(从右至左、从大到小进行交换排序),而快速排序是将数据从左到右排序完成(从左至右、从小到大进行交换排序),虽然选择排序相对于冒泡排序将交换次数从O(n2)O(n^2)O(n2)...
选择排序(直接选择排序,堆排序) 交换排序(冒泡排序,快速排序) 插入排序(直接插入排序,折半插入排序,Shell排序) 归并排序 桶式排序 基数排序
//冒泡排序 List bubbleSort(List list){ boolean change = true;//一个交换标志,当为false时,表示已排序好 int temp; for(int i = list.getLength();i >= 2 && change; i --){ change = false; ...