算法基础01——排序之冒泡&插入&选择排序

排序定义

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

进一步讲排序就是求最大有序度的过程

有序度:数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样:

有序元素对:a[i] <= a[j], 如果i < j。

同理,对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是 n*(n-1)/2,也就是 15。我们把这种完全有序的数组的有序度叫作满有序度
image.png
逆序度与有序度相反(默认从小到大为有序)

关于这三个概念,我们还可以得到一个公式:逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度,减少逆序度的过程,最后达到满有序度,就说明排序完成了。

排序问题有许多有趣的算法解决方案,体现了许多计算机科学的想法:

比较与非比较策略,
迭代与递归实现,
分而治之
最佳/最差/平均情况时间复杂性分析,
随机算法等

基本概念

原地排序算法:就是特指空间复杂度是 O(1) 的排序算法。

稳定性:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变,就称之为稳定排序。

比如4,5,666,3,2,1这里待排序数组中有3个6,而倘若排序后这3个6的彼此顺序不变,如:1,2,3,4,5,666就是稳定排序。如对订单创建时间排序等情况下对原顺序位置有要求就只能用稳定排序了。

另外基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种是元素交换或移动。所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。

冒泡排序

最基本的排序算法,我想在学任何一门编程语言时都应该写过吧?

官方定义:
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

简单的说就是两两比较,交换大小。

场景:在喝可乐时,如果我们把可乐疯狂摇动,这时会出现很多气泡。其中大的气泡最先从底部浮到上面来。

冒泡排序可视化过程
image.png

image.png

/**
 * 冒泡排序
 * @author yixunfei
 *
 */
public class BubbleSort {

	public static int[] bubbleSort(int[] arr) {
		if (arr.length <= 1) {
			return arr;
		}
		for (int i = 0; i < arr.length; ++i) {
			// 提前退出冒泡循环的标志位
			boolean flag = false;
			for (int j = 0; j < arr.length - i - 1; ++j) {
				if (arr[j] > arr[j + 1]) {
					// 交换
					int tmp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = tmp;
					// 表示有数据交换
					flag = true; 
				}
			}
			if (!flag) {
				break;				
			}
		}
		return arr;
	}
}

插入排序

插入排序(Insertion sort)是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,算法适用于少量数据的排序,时间复杂度O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是:每步将一个待排序的记录,按大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

类似斗地主或者打麻将摸牌,插入的过程。只是在数组中后面的元素全部后移。

插入排序可视化过程
image.png

image.png

/**
 * 插入排序
 * @author yixunfei
 *
 */
public class InsertSort {

	public static int[] insertionSort(int[] arr) {
		if (arr.length <= 1) {
			return arr;
		}
		for (int i = 1; i < arr.length; ++i) {
			int value = arr[i];
			int j = i - 1;
			// 查找插入的位置
			for (; j >= 0; --j) {
				if (arr[j] > value) {
					 // 数据移动
					arr[j + 1] = arr[j];
				} else {
					break;
				}
			}
			// 插入数据
			arr[j + 1] = value; 
		}
		return arr;
	}
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

对比数组中前一个元素跟后一个元素的大小,如果后面的元素比前面的元素小则用一个变量k来记住他的位置,接着第二次比较,前面“后一个元素”现变成了“前一个元素”,继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标),等到循环结束的时候,我们应该找到了最小的那个数的下标了,然后进行判断,如果这个元素的下标不是第一个元素的下标,就让第一个元素跟他交换一下值,这样就找到整个数组中最小的数了。然后找到数组中第二小的数,让他跟数组中第二个元素交换一下值,以此类推。

选择排序算法的实现思路每次找最小的和待排序的第一个交换。

选择排序可视化过程

public static void selectionSort(int[] nums) {

for(int i = 0; i < nums.length-1; i++) {
    int location = i;
    for(int j = i; j < nums.length-1; j++) {
        if(nums[j+1] < nums[location]) {
            location = j+1;//记录下最小值的位置
        }
    }
    //交换两个位置的值
    if(location != i) {
        int temp = nums[i];
        nums[i] = nums[location];
        nums[location] = temp;
    }
}
}

image.png

更新时间:2020-02-15 11:29:57

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法基础01排序之冒泡插入选择
最后更新:2020-02-15 11:29:57

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×