冒泡排序和选择排序的源码和两者之间的复杂度简介
冒泡排序
冒泡排序算法原理
* 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
交换操作。从这个意义上讲,交换排序的性能略优于冒泡排序。
而且,交换排序比冒泡排序的思想更加直观。