免费商城建站,兰州落地防疫,顾小北wordpress主题,深圳创业贷款文章目录 前言一、算法原理二、复杂度三、Java实现总结 前言
冒泡排序#xff08;Bubble Sort#xff09;,是一种比较简单的排序算法。
它重复地走访要排序的元素列#xff0c;依次比较两个相邻的元素#xff0c;如果它们的顺序错误#xff0c;则把它们交换位置。走访元… 文章目录 前言一、算法原理二、复杂度三、Java实现总结 前言
冒泡排序Bubble Sort,是一种比较简单的排序算法。
它重复地走访要排序的元素列依次比较两个相邻的元素如果它们的顺序错误则把它们交换位置。走访元素重复地进行直到没有相邻元素需要交换为止完成整个排序过程。
一、算法原理
比较相邻元素如果元素1大于元素2则交换。依次向后对每一个相邻元素做同样的工作直到队列末尾这时最大的元素就位于最后一个元素位置了。重复以上步骤直到最后一个元素位置的前一位为止因为最后一位已经排好了。持续每次对越来越少的元素重复上面步骤直到没有任何一个数字需要比较位置排序结束。
二、复杂度
如果数组的初始状态是正序的一趟扫描即可完成排序所以冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n²)冒泡排序总的平均时间复杂度为O(n²)。
由于冒泡排序是原址排序所以空间复杂度为O(1)。
三、Java实现
基础标准版本
public void bubbleSort(int[] arr){int i,j,t;int l arr.length;fow(i0;il-1;i){for(j0;jl-i-1;j){if(arr[j]arr[j1]){t arr[j];arr[j] arr[j1];arr[j1] t;}}}
}冒泡排序就是把小的元素往前调或者把大的元素往后调。相邻元素之间进行比较交换也发生在这两个元素之间所以相同元素的前后顺序并没有改变所以冒泡排序是一种稳定排序算法。
优化版本
冒泡排序可以有以下改进
执行完一轮排序后虽然可能数据已全部排序完毕但程序无法判断是否完成。为此我们可以设置一个标志位flag用它来表示是否是乱序状态每经过一轮排序之前我们都会设置flag状态为false如果本轮排序发生了元素位置交换则表示为乱序状态修改flag值为true但如果已经是顺序的则不会发生元素交换表示已排序完毕终止排序即可。
public void bubbleSort(int[] arr){int i,j,t;int l arr.length;boolean flag true;for(i0;il-1;i){flag false;for(j0;jl-i-1;j){if(arr[j]arr[j1]){t arr[j];arr[j] arr[j1];arr[j1] t;flag true;}}if(!flag){//提前终止排序避免了性能浪费break;}}
}总结
本文介绍了一种非常简单的排序方法——冒泡排序。
冒泡排序就是把小的元素往前调或者把大的元素往后调交换发生在相邻的两个元素之间走访元素重复地进行直到没有相邻元素需要交换为止完成整个排序过程。相同元素的前后顺序并没有改变所以冒泡排序是一种稳定排序算法。冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n²)冒泡排序总的平均时间复杂度为O(n²)。冒泡排序是原址排序所以空间复杂度为O(1)。我们可以设置一个标志位flag用它来表示是否是乱序状态每经过一轮排序之前我们都会设置flag状态为false如果本轮排序发生了元素位置交换则表示为乱序状态修改flag值为true但如果已经是顺序的则不会发生元素交换表示已排序完毕终止排序即可。
