首页 > 代码库 > 冒泡、选择、插入排序

冒泡、选择、插入排序

发明的秘诀在不断的努力。——牛顿


本讲内容:冒泡、选择、插入排序


一、冒泡排序

原理:将相邻的两个数比较,将较小的数调到前头;有n个数就要进行n-1趟比较,第一次比较中要进行n-1次两两比较,在第j趟比较中,要进行n-j次两两比较。(值比较大的元素沉下去后,只把剩下的元素中的最大值再沉下去就可以

void bubbleSort(int[] arr) {
		//冒泡法要排序n-1次
		for(int i=0;i<arr.length-1;i++){
			//值比较大的元素沉下去后,只把剩下的元素中的最大值再沉下去就可以啦
			for(int j=0;j<arr.length-1-i;j++){
				if(arr[j]>arr[j+1]){// 把值比较大的元素沉到底
					int temp;
					temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
	}

二、选择排序

原理: 首先以第一个元素为基准,从一个方向开始扫描,比如从左到右扫描,以A[0]为基准,接下来从A[0]….A[9]中找出最小的元素,将其与A[0]交换。然后将其基准位置右移一位,重复上面的动作,比如,以A[1]为基准,找出A[1]~A[9]中最小的,将其与A[1]交换。一直进行到将基准位置移到数组最后一个元素时排序结束。

<span style="font-size:18px;">void SelectSort(int[] arr) {
		for(int i=0;i<arr.length;i++){
			//从j往前的数据都是排好的,所以从j开始往下找剩下的元素中最小的
			for(int j=i+1;j<arr.length;j++){//以此元素为基准
				if(arr[i]>arr[j]){//arr[i]以此元素为基准
					int temp;
					temp=arr[j];
					arr[j]=arr[i];
					arr[i]=temp;
				}
			}
		}
	}</span>

三、 插入排序:

原理:把n个等排序的元素看成一个有序列表和一个无序列表,开始时有序列表只有一个元素,无序列表有n-1个元素,排序过程中每次从无序列表中拿出一个数与有序列表比较,将它插入有序列表中使之成为新的有序列表。

void InsertSort(int[] arr) {
		for(int i=1;i<arr.length;i++){
			int insertVal=arr[i];//操作当前元素,先保存在其它变量中
			int index=i-1;//记录插入值的前一个数
			//从当前元素的上一个元素开始查找合适的位置,一直查找到首元素
			while(index>=0&&insertVal<arr[index]){
				arr[index+1]=arr[index];
				index--;//再跟前面一个比较
			}
			arr[index+1]=insertVal;
		}
	}

本讲就到这里,Take your time and enjoy it


          


冒泡、选择、插入排序