冒泡排序
冒泡排序算法的运作如下:(从后往前)
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后
- 在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
Java代码实现
/**
* 冒泡排序
* 相邻两个元素相比较,符合条件就交换位置
* 所以循坏一次能找到一个最值
* @param arr
* @return
*/
public int[] bubbleSort(int[] arr){
for(int i = 0;i<arr.length-1;i++){
//-i是因为循坏一次就有一个最值确定了不需要参与比较
for(int j = 0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
算法时间复杂度:冒泡排序的最坏时间复杂度为
点击图片右击查看图片可看大图
选择排序
/**
* 选择排序
* 内循环完成一次最值出现在0角标位置
* 第一次0角标元素与其他元素进行比较,找到最值放在0位置
* 第二次1角标元素与其他元素进行比较,找到最值放在1位置
* 一直到所有元素比较完毕
* @param arr
* @return
*/
public int[] selectSort(int[] arr){
//减一是因为最后一个元素不用比较了
for(int i = 0;i<arr.length - 1;i++){
//从1开始是因为0和0比较没有意义
for(int j = 1+i;j<arr.length;j++){
if(arr[i]>arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
比较操作的时间复杂度为O(n2)。
点击图片右击查看图片可看大图