算法--冒泡排序--java

45 阅读 0 评论 30 点赞

我是靠谱客的博主无奈美女，最近开发中收集的这篇文章主要介绍算法--冒泡排序--java，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

基本思想

所谓冒泡排序就是依次将两个相邻的数进行比较，大的在前面，小的在后面。

即先比较第一个数和第二个数，大数在前，小数在后，然后比较第 2 个数和第 3 个数，直到比较最后两个数
- 第一趟排序结束后，最小数的数一定在最后
- 第二趟排序在第一趟的基础上重复上述操作

由于排序过程中总是大数在前，小数在后，相当于气泡上升，所以叫冒泡排序。

大数在前，小数在后排序后得到的是降序
小数在前，大数在后排序后得到的是升序结果

排序过程(降序)

  初始数据：4 5 6 1 2 3
  第一趟：
  比较前两个数，   4比5小，交换位置     5 4 6 1 2 3
  比较第2第3个数， 4比6小，交换位置     5 6 4 1 2 3
  比较第3第4个数， 5比1大，位置不变     5 6 4 1 2 3
  比较第4第5个数， 1比2小，交换位置     5 6 4 2 1 3
  比较最后两个数， 1比3小，交换位置     5 6 4 2 3 1
  第一趟结束

  第二趟重复第一趟过程得到 6 5 4 3 2 1
  排序完毕。

可以发现，第二趟排序结束后，所有数据已经排好序了。实际上，我们在对于一组数据进行冒泡排序时，假如需要排列的数据个数为 n 个，那么 n-1 趟一定能排好序，比如因为第 2 趟都会有前 2 个小的数排序好，n-1 趟前 n-1 小的数已排好序，最后一个数自然也排好序了。

package Sort;
//降序过程
public class 冒泡排序 {
	public static void main(String[] args) {
		int[] a = {9,3,1,4,6,8,7,5,2};
		sort(a);
		print(a);
	}
	static void sort(int[] a) {
		for (int i = a.length-1; i > 0 ; i--) {
			for (int j = 0; j < i; j++) {
				if (a[j] < a[j+1]) {
					swap(a, j, j+1);
				}
				
			}
			
		}
	}
	//排序
	static void swap(int[] a,int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	//打印数组的方法
	static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
			
		}
	}
}

package Sort;
//升序过程
public class 冒泡排序 {
	public static void main(String[] args) {
		int[] a = {9,3,1,4,6,8,7,5,2};
		sort(a);
		print(a);
	}
	static void sort(int[] a) {
		for (int i = a.length-1; i > 0 ; i--) {
			for (int j = 0; j < i; j++) {
				if (a[j] > a[j+1]) {
					swap(a, j, j+1);
				}
				
			}
			
		}
	}
	//排序
	static void swap(int[] a,int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	//打印数组的方法
	static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
			
		}
	}
}

复杂度

时间复杂度为 O(n^2)

空间复杂度为 O(1)