排序算法

1:冒泡排序


冒泡排序是的算法思路是将最小数值放在下标为0的位置,将最大值放在mao.length-1的位置

外层for循环开始计算层数,即mao.length-1为目标计划循环次数,当外层for完成一次后,总长度就会-1,也就是说最大值已经出来了并且放在了最后一位,那么在之后的循环中就不算这一项了,以此类推。

内层for循环从下标0开始,和下一角标比较,这里用第一项和第二项代表,如果第一项>第二项,那么两个就互换,否侧不换,然后第二项和第三项比较。直到完成这一次循环。// 简单排序--冒泡排序 int[] mao = { 120, 110, 100, 90, 80, 70, 45 }; // 外循环只是循环几次 for (int i = mao.length - 1; i > 1; i--) { // 内循环每循环一次就会有拍好一位,如最大值 System.out.println("第" + (mao.length - i) + "次循环"); for (int j = 0; j < i; j++) { if (mao[j] > mao[j + 1]) { // 如果第一个比第二大,那就换位子 int temp = mao[j]; mao[j] = mao[j + 1]; mao[j + 1] = temp; } for (int k = 0; k < mao.length; k++) { System.out.print(mao[k] + " , "); } System.out.println(); } }

第1次循环
110 , 120 , 100 , 90 , 80 , 70 , 45 , 
110 , 100 , 120 , 90 , 80 , 70 , 45 , 
110 , 100 , 90 , 120 , 80 , 70 , 45 , 
110 , 100 , 90 , 80 , 120 , 70 , 45 , 
110 , 100 , 90 , 80 , 70 , 120 , 45 , 
110 , 100 , 90 , 80 , 70 , 45 , 120 , 
第2次循环
100 , 110 , 90 , 80 , 70 , 45 , 120 , 
100 , 90 , 110 , 80 , 70 , 45 , 120 , 
100 , 90 , 80 , 110 , 70 , 45 , 120 , 
100 , 90 , 80 , 70 , 110 , 45 , 120 , 
100 , 90 , 80 , 70 , 45 , 110 , 120 , 
第3次循环
90 , 100 , 80 , 70 , 45 , 110 , 120 , 
90 , 80 , 100 , 70 , 45 , 110 , 120 , 
90 , 80 , 70 , 100 , 45 , 110 , 120 , 
90 , 80 , 70 , 45 , 100 , 110 , 120 , 
第4次循环
80 , 90 , 70 , 45 , 100 , 110 , 120 , 
80 , 70 , 90 , 45 , 100 , 110 , 120 , 
80 , 70 , 45 , 90 , 100 , 110 , 120 , 
第5次循环
70 , 80 , 45 , 90 , 100 , 110 , 120 , 
70 , 45 , 80 , 90 , 100 , 110 , 120 , 
第6次循环
45 , 70 , 80 , 90 , 100 , 110 , 120 , 

算法不变性

这里可以看出当比较到最后一次时,只剩下前两个比较了,也就是说在最右边一旦完成比较后就不会再进行任何比较操作,当然每个排序的不变性是不一样的。

冒泡排序的效率

在上面的例子结果中可以看出,7条数据的情况下,第一趟循环比较了6次,第二次比较了5次...,最后一次比较一次,公式为

(N-1)+(N-2)+(N-3)+...+1===N*(N-1)/==2====

比较算法结果:

学过高数的人都知道,数学中有叫趋向于某某某的说法,咱们的算法比较结果就是趋向于==N²/2==

。因为在N很大的情况下,N-1与N可以都看做为N,就算-1,-2也影响不大。

交换算法结果

由于在比较时不一定要交换,那么交换次数肯定是小于比较次数,有点的是从头到位都需要交换(逆向排序),则有的一次都不用换(已经排序好的),所以,这里排序算法取平均==N²/4==.

大O表示法

由于常数不算在表示法中,所以结果为O(N²)时间。在平常的代码中,如果那你看到双重for循环时,基本就可以判断运行时间效果为O(N²)了。

2:选择排序

// 选择排序
		System.out.println("选择排序");

		int[] selectInt = { 120, 110, 100, 90, 80, 70, 45 };
		/**
		 * 第一步: 原理是都和第一项(下标0)比较,小的则替换
		 * 
		 * 外层变量设置为outer,内层变量为inner,最小数据存放下标min。
		 * selectInt.length-1一共7个数比6次就可以了。selectInt.length内部是从下标1开始的,这里就不要再-1了,
		 * 否侧少比较一次
		 */
		int min;
		for (int outer = 0; outer < selectInt.length - 1; outer++) {
			min = outer;
			// 内循环每循环一次就会有拍好一位,如最大值
			System.out.println("第" + (outer + 1) + "次循环");
			for (int inner = outer + 1; inner < selectInt.length; inner++) {
				// 如果后六个数中,有小于第一项(下标0)的,就调换下标
				if (selectInt[inner] < selectInt[min]) {
					min = inner;
				}
			}
			int temp = selectInt[outer];
			selectInt[outer] = selectInt[min];
			selectInt[min] = temp;

			for (int k = 0; k < selectInt.length; k++) {
				System.out.print(selectInt[k] + " , ");
			}
			System.out.println();
		}
		/**
		 * 第1次循环 45 , 110 , 100 , 90 , 80 , 70 , 120 ,
		 * 
		 */
第1次循环
45 , 110 , 100 , 90 , 80 , 70 , 120 , 
第2次循环
45 , 70 , 100 , 90 , 80 , 110 , 120 , 
第3次循环
45 , 70 , 80 , 90 , 100 , 110 , 120 , 
第4次循环
45 , 70 , 80 , 90 , 100 , 110 , 120 , 
第5次循环
45 , 70 , 80 , 90 , 100 , 110 , 120 , 
第6次循环
45 , 70 , 80 , 90 , 100 , 110 , 120 , 

选择排序算法不变性

下标小于等于outer的位置的数据总是有序的,一旦放在前面后,就不会再动。

选择排序算法效率

上面结果可以说明,虽然也是比较了和冒泡一样多的次数,但是交换缺少了很多。所以时间为N²/2

比较次数和交换次数

比较次数:N²/2

交换次数:最多N-1,最少0次,取平均N/2

大O表示法

O(N²)

以上可看出选择排序是比冒泡排序快点的。

3:插入排序

概念:有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)

/**
		 * 从第二项开始,第一项默认为有序 
		 * 1:把第二项数据暂存,和第一项比较,如果第一项>第二项则调换,
		 * 2:把第三项数据暂存,和第二项比较,如果第二项>第三项则调换, 这时调换后的第二项还要和第一项比较,然后再判断调换,从当前下标开始向左遍历凡是大于temp的数据,下标
		 * 都均向右移动一位(调换)。
		 * 以此类推 ........
		 *
		 * 
		 * 很多人估计不理解为什么从第二项开始,而不是从第一项,
		 * 这里我稍微做一下解释,插入排序就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,
		 * 我们对于一个数组,不知道哪里是排序好的,可能是前三条,也可能不是有序的,我们这时就要假设一段已经排好序的数组,我们直接取前三项的话,
		 * 不一定是排序好的, 我们取前一项的话,就一个数据肯定是排序好的,所以就从第二项开始,默认第一项已经排序好了。这就是由来。
		 */
		int insertElems[] = { 23, 4, 5, 34, 56, 21 };
		int inner, outer;
		for (outer = 1; outer < insertElems.length; outer++) {
			int temp = insertElems[outer];// 把第二项暂存
			inner = outer;
			// (第一项>第二项)
			while (inner > 0 && insertElems[inner - 1] > temp) {
				insertElems[inner] = insertElems[inner - 1];
				inner--;
			}
			insertElems[inner] = temp;
			for (int k = 0; k < insertElems.length; k++) {
				System.out.print(insertElems[k] + " , ");
			}
			System.out.println();

		}
4 , 23 , 5 , 34 , 56 , 21 , 
4 , 5 , 23 , 34 , 56 , 21 , 
4 , 5 , 23 , 34 , 56 , 21 , 
4 , 5 , 23 , 34 , 56 , 21 , 
4 , 5 , 21 , 23 , 34 , 56 , 

插入排序的不变性

在每趟结束时,在temp位置插入后,比outer下标小(左边)的数据项都是有序的。

结论:插入排序比冒泡快一倍,优于选择排序

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

4 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

34811
来自专栏赵俊的Java专栏

搜索二维矩阵Ⅱ

1763
来自专栏服务端技术杂谈

map/reduce的先祖归并排序

归并排序是利用分治的思想进行排序的策略。 分:通过递归将一个大的数据集进行递归分割,直到只有两个元素进行比较。 治:将分的阶段的分割单元进行合并。 分 ? 可以...

2664
来自专栏灯塔大数据

每周学点大数据 | No.20序列有序的判定

No.19期 序列有序的判定0 数组的判 Mr. 王:这里我们再讲一个亚线性时间的判定问题——数组有序的判定问题。你来说一下问题定义,并想一想这个问题...

2675
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

662
来自专栏HTML5学堂

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

3295
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

2777
来自专栏技术碎碎念

递归与分治之快速排序

分治法就是把一个大问题分解为多个类型相同的子问题,最后把这些子问题的解合并起来就是问题的解。 快速排序(Quicksort)是对冒泡排序的一种改进,采用了分治的...

2736
来自专栏计算机视觉与深度学习基础

Leetcode 233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-nega...

2237
来自专栏机器学习算法全栈工程师

Sample K算法

0、题目来源    最近去国内某牛叉互联网公司面试,出了一道算法题,看似简单,但是真正的答案十分巧妙。故此回忆并将原题以及解题思路记录下来,供大家学习: 随机...

3398

扫码关注云+社区