3
冒泡排序的简单理解 - 程序员翔仔
source link: https://www.cnblogs.com/fatedeity/p/16387905.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
冒泡排序是一种交换排序，基本思想是在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
即每当两个相邻的数比较后发现它们的顺序与排序要求相反时，就将它们互换。
冒泡排序详细的执行步骤如下：
- 从第一个元素开始，比较相邻的元素，如果前一个比后一个大，就交换它们两个；
- 从前往后，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就会是最大的数；
- 将这次找出的最大元素放在最后一个元素位置上，然后针对除这个最大元素以外的其他所有元素重复以上 1~2 步骤；
- 重复以上步骤，直到最后第一个元素和第二个元素完成比较、交换，则排序完成。
冒泡排序是原地排序算法吗？
冒泡排序是一个原地排序算法，过程只涉及相邻数据的交换操作，只需要常量级的临时空间，它的空间复杂度是 O(1)。
冒泡排序是稳定的排序算法吗？
为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等时可以不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
冒泡排序的时间复杂度是多少？
使用最优时间复杂度解法，原序列是有序时的时间复杂度是 O(n)；最坏情况时间复杂度为 O(n2)；平均时间复杂度是 O(n2)。
package cn.fatedeity.sort; public class BubbleSort { private static void swap(int[] numbers, int src, int target) { int temp = numbers[src]; numbers[src] = numbers[target]; numbers[target] = temp; } public static int[] sort(int[] numbers) { for (int i = 0; i < numbers.length - 1; i++) { boolean doSwap = false; for (int j = 0; j + 1 < numbers.length - i; j++) { if (numbers[j] > numbers[j + 1]) { swap(numbers, j, j + 1); doSwap = true; } } // 优化基础冒泡排序的步骤 if (!doSwap) { // 如果遍历整个序列无需交换，则表示整个序列已经完全有序 return numbers; } } return numbers; }}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK