【数据结构与算法】冒泡排序

我不是女神ヾ 2022-08-10 16:51 220阅读 0赞

排序算法是一种基本、常用的算法。排序算法分为内部排序和外部排序。

内部排序是指整个排序过程不需要访问外存就能完成。

外部排序是指党对大批量数据进行排序时，不可能一次性将全部数据装入内存，只能从外存读取一部分数据到内存中，将内存中的数据进行排序后，再存储到外存中，然后再从外存中读取下一部分数据到内存中，最后，对已经排序的子部分进行归并排序。

冒泡排序是一种相邻数据交换的排序方法。冒泡排序的特点是对于n个元素要进行n-1次扫描，那么有时候可能扫描一两次数据就已经排好序了，后面再扫描明显就是浪费计算资源了，所以可以对冒泡排序进行一些改进，代码如下：

public class BubbleSort {
    	public void bubbleSort(int[] in) {
    
    		boolean isBubble = false;
    		int inLength = in.length;
    		for (int i = 0; i < inLength; i++) {
    
    			System.out.print("第" + i + "遍: ");
    			for (int k : in) {
    				System.out.print(k + " ");
    			}
    			System.out.println();
    
    			for (int j = inLength - 1; j > i; j--) {
    				if (in[j] < in[j - 1]) {
    					isBubble = true;
    					int tmp = in[j];
    					in[j] = in[j - 1];
    					in[j - 1] = tmp;
    				}
    			}
    
    			if (!isBubble) {
    				break;
    			} else {
    				isBubble = false;
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		BubbleSort mBubbleSort = new BubbleSort();
    		int[] caseOne = { 6, 5, 4, 3, 2, 1, 10, 2 };
    		int[] caseTwo = { 1, 6, 5, 2, 4, 3 };
    		mBubbleSort.bubbleSort(caseOne);
    		for (int i : caseOne) {
    			System.out.print(i + " ");
    		}
    		System.out.println();
    		mBubbleSort.bubbleSort(caseTwo);
    		for (int i : caseTwo) {
    			System.out.print(i + " ");
    		}
    	}
    }