冒泡排序和选择排序的源码和两者之间的复杂度简介

冒泡排序

冒泡排序算法原理
* 1 比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置。
* 2 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
* 3针对所有的元素重复以上的步骤,除了最后一个。
* 4持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

实例:

例子: 4 3 8 5 (按递增排)
* 第1轮: 3 4 8 5 3 4 8 5 3 4 5 8
* 第2轮: 3 4 5 8 3 4 5 8
* 第3轮: 3 4 5 8

实现代码:

public void maoPaoSort(int arr[]){
		for(int i=1;i<arr.length;i++){//外 、
			//层循环定义循环轮数
			//内层循环 定义比较次数
			for(int j=0;j<arr.length-i;j++){
				//如果条件改成arr[j] >= arr[j+1],则变为不稳定的排序算法
				if(arr[j]>arr[j+1]){
					int t=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=t;
				}
			}
		}
	}

时间复杂度分析:

*其外层循环执行 N-1次。

* 内层循环最多的时候执行N次,最少的时候执行1次,平均执行 (N+1)/2次。
* 所以循环体内的比较交换约执行 (N-1)(N+1)/2 = (N^2-1)/2
* 按照计算复杂度的原则,去掉常数,去掉最高项系数,其复杂度为O(N^2)。

选择排序算法:

原理:

*1 首先在未排序的序列里找到最小(大)元素,放到序列的首端,
*2 再从剩余元素中找到最小(大)的元素,放到序列的尾端。
*3 依次循环,直到排序完成。

实例:

*例子: 5, 4, 8, 9, 2, 1
*第1轮 1, 4, 8, 9, 2, 5(1 5交换)
*第2轮 1, 2, 8, 9, 4, 5(2 4交换)
*第3轮 1, 2, 4, 9, 8, 5 (4 8交换)
*第4轮 1, 2, 4, 5, 8, 9 (5 9交换)

代码实现:

public void xuanZeSort(int []arr){
		int min,temp;
		for(int i=0;i<arr.length-1;i++){
			min=i;
			for(int j=i+1;j<arr.length;j++){
				if(arr[j]<arr[i]){
					min=j;
				}
			}
			if(min!=i){
				temp=arr[i];
				arr[i]=arr[min];
				arr[min]=temp;
			}
			
		}
	}

时间复杂度分析:


选择排序的复杂度分析。第一次内循环比较N - 1次,然后是N-2次,N-3次,……,最后一次内循环比较1次。
共比较的次数是(N - 1) + (N - 2) + ... + 1,求等差数列和,得(N - 1 + 1)* N / 2 = N^2 / 2
舍去最高项系数,其时间复杂度为O(N^2)

选择排序和冒泡排序的效率问题。

虽然选择排序和冒泡排序的时间复杂度一样,但实际上,选择排序进行的交换操作很少,最多会发生 N - 1次交换。
而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲,交换排序的性能略优于冒泡排序。
而且,交换排序比冒泡排序的思想更加直观。