java中簡單的排序算法示例

這篇文章給大家分享的是有關(guān)java中簡單的排序算法示例的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。

算法也是一個爭論了很久的話題，程序員到底該不該掌握算法？不同的人有不同的答案，而事實上，很多公司都對算法有一定的要求，有些公司直接在面試的時候便會要求面試者手寫算法題。這就對程序員的技術(shù)要求產(chǎn)生了很大的考驗，所以面對如今的大環(huán)境，我們必須掌握算法，才能在今后的工作中占據(jù)一席之地。

那么接下來，我就簡單介紹一下幾個排序算法，希望對你們有所幫助。

冒泡排序

冒泡排序（Bubble Sort），是一種較簡單的排序算法。

它重復(fù)地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。

這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

演示：

代碼如下：

@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 統(tǒng)計比較次數(shù)
	int count = 0;
	// 第一輪比較
	for (int i = 0; i < arr.length - 1; i++) {
		boolean flag = true;
		// 第二輪比較
		for (int j = 0; j < arr.length - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				// 交換位置
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			count++;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("一共比較了:" + count + "次");
}

運行結(jié)果：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比較了:105次

選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪?。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。選擇排序是不穩(wěn)定的排序方法。

演示：

代碼如下：

@Test
public void SelectionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 0; i < arr.length - 1; i++) {
		int index = i;
		for (int j = 1 + i; j < arr.length; j++) {
			if (arr[j] < arr[index]) {
				index = j;// 保存最小元素的下標(biāo)
			}
		}
		// 此時已經(jīng)找到最小元素的下標(biāo)
		// 將最小元素與前面的元素交換
		int temp = arr[index];
		arr[index] = arr[i];
		arr[i] = temp;
	}
	System.out.println(Arrays.toString(arr));
}

運行結(jié)果：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

實現(xiàn)也非常的簡單，首先在外循環(huán)里定義了一個index變量存儲i的值，這是為了避免重復(fù)地比較，因為在每一輪的比較結(jié)束后，前i個元素是已經(jīng)排好序的，所以無需再次比較，只需從i開始即可。后面的比較都是基于index位置的元素進(jìn)行比較，倘若比較完后index位置的元素是最小值，那就無需交換，不動即可。而如果找到了比index位置的元素更小的元素，那就將該元素的索引賦值給index，然后繼續(xù)比較，直到比較完成，比較完成之后得到的index即為數(shù)組中的最小值，那此時只需要將index位置的元素和i位置的元素交換即可。

插入排序

插入排序（Insertion sort）是一種簡單直觀且穩(wěn)定的排序算法。如果有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法，插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外（讓數(shù)組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步將一個待排序的記錄，按其關(guān)鍵碼值的大小插入到前面已經(jīng)排序的數(shù)組中的適當(dāng)位置上，直到全部插入完為止。

演示：

代碼如下：

@Test
public void InsertionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 1; i < arr.length; i++) {
		// 定義待插入的數(shù)
		int insertValue = arr[i];
		// 找到待插入數(shù)的前一個數(shù)的下標(biāo)
		int insertIndex = i - 1;
		while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];
			insertIndex--;
		}
		arr[insertIndex + 1] = insertValue;
	}
	System.out.println(Arrays.toString(arr));
}

運行結(jié)果：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

那么在這里，因為數(shù)組元素我們并不確定，所以只能將數(shù)組的第一個元素看成是一個有序的序列，所以從數(shù)組的第二個元素開始才是我們需要去尋找插入位置的元素。所以外層循環(huán)從1開始，然后將arr[i]，也就是當(dāng)前的第二個元素先保存起來，然后找到待插入元素的前一個元素下標(biāo)，也就是i-1，此時通過一個while循環(huán)去比較。

當(dāng)insertIndex小于0時應(yīng)該退出循環(huán)，因為此時已經(jīng)與前面的所有元素比較完畢。在比較的過程中，如果待插入元素小于前一個元素，就將前一個元素后移，也就是將前一個元素的值直接賦值給待插入元素位置。因為在最開始已經(jīng)將待插入元素進(jìn)行了保存，所以只需將待插入元素的值賦值給它的前一個元素即可。因為在while循環(huán)中insertIndex執(zhí)行了自減操作，所以它的前一個元素下標(biāo)應(yīng)為insertIndex + 1。而如果待插入的元素值大于前一個元素，那么就不會進(jìn)入while循環(huán)，這樣insertIndex + 1之后的位置仍然是自己所在的位置，所以賦值后值不改變，后面的操作以此類推。

感謝各位的閱讀！關(guān)于java中簡單的排序算法示例就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！