搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 呲花是朵花 > 算法之冒泡排序

算法之冒泡排序

呲花是朵花 2020-06-30

冒泡排序

思路:我想把9移动到最后面的位置,通过两两判断,如果前面的元素>后面的元素,交换两个值,循环8次才能放到最后。

public static void main(String[] args) { int[] arr = {5, 9, 7, 1, 3, 8, 2, 6, 4}; for (int j = 0; j < 8; j++) { if (arr[j] > arr[j+1]) { swap(arr, j, j + 1); } } print(arr); }
5 7 1 3 8 2 6 4 9 

然后我再循环7次,就可以把8放到倒数第二位,以此类推,每次循环递减,最后循环1次的时候完成所有元素的排序,所以在这个循环上套一层循环,依次递减

/** * 冒泡排序 */public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 9, 7, 1, 3, 8, 2, 6, 4}; sort(arr); }
public static void sort(int[] arr) { for (int i = arr.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (arr[j] > arr[j+1]) { swap(arr, j, j+1); } } }
print(arr); }
/** * 交换元素位置 * @param arr 数组 * @param i 位置1 * @param j 位置2 */ static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
static void print(int arr[]) { Arrays.stream(arr).forEach(num->{ System.out.print(num + " "); }); System.out.println(); }}

但是这样写是有缺点的,假设我数组的值是这样的{1, 3, 2, 4, 5, 6, 7, 8, 9},从第三个位置开始,后面的元素都是有序的,那我第一次比较完发现没有交换过,那我下次就没必要再去比较了。

/** * 冒泡排序-优化 */public class BubbleSort1 { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
sort(arr); print(arr); }
public static void sort(int[] arr) { // 记录比较次数 int num = 0; // 记录交换次数 int swapNum = 0; // 初始化最后一次交换位置 默认为数组最后位置 int lastSwapedIndex = arr.length - 1; // lastSwapedIndex控制循环的边界,假如最后一次交换的位置是4,那我后面的位置就不去比较了 for (int i = lastSwapedIndex; i > 0; i--) { // 记录是否交换过,默认未交换 boolean swaped = false; for (int j = 0; j < i; j++) { if (arr[j] > arr[j+1]) { swap(arr, j, j + 1); // 标记交换过 swaped = true; // 更新最后交换的位置 lastSwapedIndex = j; swapNum ++; } num++; } if (!swaped) { break; } }
print(arr); System.out.println("比较"+(num)+"次"); System.out.println("交换"+(swapNum)+"次"); }
/** * 交换元素位置 * @param arr 数组 * @param i 位置1 * @param j 位置2 */ static void swap(int[] arr, int i, int j) { // 记录原最小值,用于和最小值互换 int temp = arr[i]; // 数组中原最小值换为新的最小值 arr[i] = arr[j]; // 最小值的位置换为原最小值 arr[j] = temp; }
static void print(int arr[]) { Arrays.stream(arr).forEach(num->{ System.out.print(num + " "); }); System.out.println(); }}

这样当数组有序的时候,节省很多判断,最好的情况时间复杂度为O(n),空间复杂度为O(1),因为不占用额外的空间。

推荐阅读

• • • 

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《算法之冒泡排序》的版权归原作者「呲花是朵花」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注呲花是朵花微信公众号

呲花是朵花微信公众号:youngj5788

呲花是朵花

手机扫描上方二维码即可关注呲花是朵花微信公众号

呲花是朵花最新文章

精品公众号随机推荐