冒泡排序法

原创
2014/08/19 17:38
阅读数 182
package com.victor.sort.algorithms;

import java.util.ArrayList;
import com.victor.sort.seeds.*;

/**
 * 冒泡排序法
 * @author 黑妹妹牙膏
 *
 */
public class Bubble extends SortAlgorithms {

	/**
	Algorithm
	for i = 1:n,
	    swapped = false
	    for j = n:i+1, 
	        if a[j] < a[j-1], 
	            swap a[j,j-1]
	            swapped = true
	    → invariant: a[1..i] in final position
	    break if not swapped
	end
	
	Properties
	■Stable 
	■O(1) extra space 
	■O(n2) comparisons and swaps 
	■Adaptive: O(n) when nearly sorted 
	
	Discussion
	Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass). 
	*/
	
	@Override
	protected ArrayList<Integer> doSort(ArrayList<Integer> Alist) {
		ArrayList<Integer> a = Alist;
		int n = a.size();
		for(int i=0;i<n;i++)
		{
			boolean swapped = false;
			for(int j=n-1;j>i;j--)
			{
				if(a.get(j)<a.get(j-1))
				{
					int temp = a.get(j);
					a.set(j, a.get(j-1));
					a.set(j-1,temp);
					moveMentIncrease();
					swapped = true;
				}
				if(!swapped) continue;
			}
		}
		return a;
	}

	@Override
	public String getName() {
		return "Bubble";
	}
	
	public static void main(String[] args)
	{
		Seeds seed1 = new Random();
		Seeds seed2 = new NearSorted();
		Seeds seed3 = new Reversed();
		Seeds seed4 = new FewUniqueKeys();
		SortAlgorithms SA = new Bubble();
		SA.sort(seed1,10000);
		//SA.print();
		SA.sort(seed2,10000);
		SA.sort(seed3,10000);
		SA.sort(seed4,10000);
	}

}
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部