冒泡排序算法实现与分析

基本思想：
    从第0个数据开始，将其与后面的每一个数据比较，如果比其大则调整两个的位置直到最后一个。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

图示：
   


JAVA代码具体实现

package com.leiht.sort;

/**
 * 冒泡排序算法JAVA简单实现
 * 
 * @author Leiht
 * @date 2015-11-11
 */
public class SortBubble {

	public static void main(String[] args) {

		int[] numbersUp = { 56, 45, 78, 67, 99, 13, 34, 49, 55, 34, 12, 77, 1 };
		int[] numbersDown = { 56, 45, 78, 67, 99, 13, 34, 49, 55, 34, 12, 77, 1 };
		SortBubble sort = new SortBubble();
		
		//向上冒泡排序
		sort.sort4Up(numbersUp);
		
		//向下冒泡（下沉）排序
		sort.sort4Down(numbersDown);

	}
	
	private void sort4Up(int[] numbers) {
		System.out.println("排序之前：");
		for (int i = 0; i < numbers.length; i++) {
			System.out.print(numbers[i] + " ");
		}

		// 排序主体
		for (int i = 0; i < numbers.length - 1; i++) {
			// 将第i个元素依次与后面所有元素比较 如果比其大则交换两个的位置
			for (int j = i + 1; j < numbers.length; j++) {
				int temp = numbers[i];
				if (numbers[i] > numbers[j]) {
					numbers[i] = numbers[j];
					numbers[j] = temp;
				}
			}
		}

		System.out.println();
		System.out.println("排序之后：");
		for (int i = 0; i < numbers.length; i++) {
			System.out.print(numbers[i] + " ");
		}
	}
	
	private void sort4Down(int[] numbers) {
		System.out.println("排序之前：");
		for (int i = 0; i < numbers.length; i++) {
			System.out.print(numbers[i] + " ");
		}
		// 冒泡排序
		for (int i = 0; i < numbers.length; i++) {
			for (int j = 0; j < numbers.length - i - 1; j++) {
				// 这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了
				if (numbers[j] > numbers[j + 1]) {
					int temp = numbers[j];
					numbers[j] = numbers[j + 1];
					numbers[j + 1] = temp;
				}
			}
		}
		System.out.println();
		System.out.println("排序之后：");
		for (int i = 0; i < numbers.length; i++) {
			System.out.print(numbers[i] + " ");
		}
		
	}
	
}

分析
   冒泡排序是一种稳定的排序方法。　

   •若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
  •若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)
  •起泡排序平均时间复杂度为O(n2)

评论

3 楼 a2008933024 2015-11-14  

leihongtai2010 写道

大神指点，刚刚研究

...

2 楼 leihongtai2010 2015-11-12  

大神指点，刚刚研究

1 楼 somefuture 2015-11-12  

文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动。

的确是这样，不过你写的算法似乎没有标志位，不能实现这个功能，即使已经完成排序，仍然需要比较到最后