天天看點
傳回

java資料結構和算法-03-簡單排序java資料結構和算法-03-簡單排序

java資料結構和算法-03-簡單排序

1.如何排序

學習排序的原因是因為排序有可能是檢索的第一個步驟,比如在第二章我們學到的二分法查找,它比線性查找要快的多,而二分法查找就是基于有序的資料.雖然本章學習的是簡單排序(冒泡,選擇和插入),算法比較簡單,執行速度相對而言也慢一點.但是在有些情況下,比如對于小規模的檔案以及基本有序的檔案,插入排序比快速排序更為高效.插入排序也是作為快速排序的一部分.

簡單排序的算法反複進行比較和交換這兩個步驟,直到全部的資料有序.

2.冒泡排序

冒泡排序是簡單排序中算法最簡單的,運作起來也是非常慢.

動圖感受一下:

java資料結構和算法-03-簡單排序java資料結構和算法-03-簡單排序

基本的原理:

假設一共有n個資料,第一次掃描從左到右掃描所有的資料,将最大的資料找出,放到最右邊.然後除了最右邊的最大數第二次從左到右掃描,找到第二大的數,放到最大數的左邊.依次循環直到最左邊的資料全部比較交換完,這個時候全部資料從左到右從小到大排列.

代碼:

package chap3_排序_冒泡;

/**
 * 冒泡排序
 * @author yangdandan
 *
 */
public class ArrayBub {
	private long[] a;
	private int nElems;
	public ArrayBub(int max) {
		a = new long[max];
		nElems = 0;
	}
	public void insert(long value){
		a[nElems] = value;
		nElems++;
	}
	public void display(){
		for(int j=0;j<nElems;j++){
			System.out.print(a[j]+" ");
			//System.out.println();
		}
	}
	public void bubbleSort(){
		int m = 0;
		for(int outer=nElems-1;outer>0;outer--){
			for(int inner=0;inner<outer;inner++){
				m++;
				if(a[inner]>a[inner+1]){
					swap(inner,inner+1);
				}
			}
			
		}
		System.out.println("m "+m);
	}
	private void swap(int left, int right) {
		long temp;
		temp = a[left];
		a[left] = a[right];
		a[right] = temp;		
	}
}

測試: 

package chap3_排序_冒泡;

/**
 * 測試冒泡排序
 * @author yangdandan
 *
 */
public class BubbleSortApp {
	public static void main(String[] args) {
		int max = 100;
		ArrayBub a = new ArrayBub(max);
		a.insert(77);
		a.insert(99);
		a.insert(44);
		a.insert(55);
		a.insert(22);
		a.insert(88);
		a.insert(11);
		a.insert(00);
		a.insert(66);
		a.insert(33);
		a.display();
		System.out.println();
		a.bubbleSort();
		a.display();
	}
}

不變性:

outer右邊有序.

效率:

可以看出對于N個資料的數組,(N-1)+(N-2)+(N-3)+...+1=N(N-1)/2,差不多做了N²次比較.如果資料是随機的,那麼差不多有一般的資料進行了資料交換,則交換的次數為N²/4.那麼冒泡排序算法的時間複雜度差不多是O(N²).

3.選擇排序

選擇排序改進了冒泡排序,比較的次數仍為O(N²),但是交換次數減少到O(N).因為交換的時候有大量的資料在記憶體中移動,是以交換的時間和比較的時間相比起來,交換的時間更為重要,但是java語言不一樣,隻是改變了引用,實際對象在記憶體中的位置不變.

動圖感受一下:

java資料結構和算法-03-簡單排序java資料結構和算法-03-簡單排序

基本原理:簡單來說,就是從左到右依次掃描除了之前找到的最小數,将剩餘部分中最小的數和開始掃描位置的數進行交換,直到最右邊的資料全部比較交換完成,這時候數組就是有序數組了.

代碼: 

package chap3_排序_選擇;

/**
 * 選擇排序
 * 
 * @author yangdandan
 *
 */
public class ArraySel {
	private long[] a;
	private int nElems;

	public ArraySel(int max) {
		a = new long[max];
		nElems = 0;
	}

	public void insert(long value) {
		a[nElems] = value;
		nElems++;
	}

	public void display() {
		for (int j = 0; j < nElems; j++) {
			System.out.print(a[j] + " ");
			// System.out.println();
		}
	}

	public void selectionSort() {
		int min, out, in;
		int m = 0;
		for (out = 0; out < nElems - 1; out++) {
			min = out;
			for (in = out + 1; in < nElems; in++) {
				m++;
				if (a[in] < a[min]) {
					min = in;
				}
			}
            swap(out, min);
		}
		System.out.println("m: "+ m);
	}

	private void swap(int left, int right) {
		long temp;
		temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
}

測試: 

package chap3_排序_選擇;

public class SelectSortApp {
	public static void main(String[] args) {
		int max = 100;
		ArraySel a = new ArraySel(max);
		a.insert(77);
		a.insert(99);
		a.insert(44);
		a.insert(55);
		a.insert(22);
		a.insert(88);
		a.insert(11);
		a.insert(00);
		a.insert(66);
		a.insert(33);
		a.display();
		System.out.println();
		a.selectionSort();
		a.display();
	}
}

不變性:

小于等于outer的資料項,或者說左邊到outer位置總是有序的.

效率:

對于有N個資料項的數組,進行了N*(N-1)/2次比較,小于N次的資料交換.當N比較小,但是交換的次數比較多的時候,選擇排序實際上是相當快的.

4.插入排序

大多數情況下,在簡單排序裡面,插入排序是最好的.它幾乎比冒泡排序快一點,比選擇排序還要快一點.它的時間複雜度差不多還是O(N²),常常被用在複雜排序的最後,例如快速排序.

動圖感受一下:

java資料結構和算法-03-簡單排序java資料結構和算法-03-簡單排序

基本原理:

這裡比較好的了解就是平時打撲克,拿到的牌插在比它小的右邊,比它大的左邊.我們将索引為1的資料取出開始比較,從比它索引小的左邊開始,比目前資料大,則将左邊的資料一次向右邊移動.直到不滿足比目前資料大,再将取出的資料插入.然後在一次将索引為2的資料取出同樣的循環.直到取到最大索引即最右邊的資料比較交換直到最後資料就是有序數組了.

代碼: 

package chap3_排序_插入;

/**
 * 插入排序
 * 
 * @author yangdandan
 *
 */
public class ArrayIns {
	private long[] a;
	private int nElems;

	public ArrayIns(int max) {
		a = new long[max];
		nElems = 0;
	}

	public void insert(long value) {
		a[nElems] = value;
		nElems++;
	}

	public void display() {
		for (int j = 0; j < nElems; j++) {
			System.out.print(a[j] + " ");
			// System.out.println();
		}
	}

	public void insertSort() {
		for (int out = 1; out < nElems; out++) {
			int in = out;
			long temp = a[out];
			while (in > 0 && a[in - 1] > temp) {
				a[in] = a[in - 1];
				in--;
			}
			a[in] = temp;
		}
	}
}

測試: 

package chap3_排序_插入;

public class InsertSortApp {
	public static void main(String[] args) {
		int max = 100;
		ArrayIns a = new ArrayIns(max);
		a.insert(77);
		a.insert(99);
		a.insert(44);
		a.insert(55);
		a.insert(22);
		a.insert(88);
		a.insert(11);
		a.insert(00);
		a.insert(66);
		a.insert(33);
		a.display();
		System.out.println();
		a.insertSort();
		a.display();
	}
}

不變性:

每趟結束後,在将temp位置插入資料後,比outer變量下标符号小的資料項都是局部有序的.

效率:

比較了N*(N-1)/4,複制的次數差不多等于比較的次數.時間複雜度差不多還是O(N²).對于有序或者基本有序的資料來說,while循環中的條件總是為假,是以它隻需要執行外層的循環,這個時候,算法隻需要O(N)的時間.對于逆序的資料,插入排序不必冒泡排序快.

5.對象排序

這裡和插入排序類似,省略.

6.幾種簡單排序的使用場景

排序方式 優點 缺點
冒泡排序 算法最簡單,資料量小有使用價值 效率最差,一般不推薦
選擇排序 資料量少,交換次數多時,效率高 比較次數大
插入排序 資料量少且基本有序,最好的選擇 比較次數大
Java資料結構和算法 java 資料結構 算法 簡單排序
上一篇: 資料結構與算法03-時間複雜度、空間複雜度分析
下一篇: 資料結構與算法分析

繼續閱讀