簡單的排序演算法

現在的IT產業並不像以前那麼好混了，從業人員過多，導致初級程式設計師過剩，這也間接導致了公司的招募門檻越來越高，要求程式設計師掌握的知識也越來越多。

演算法也是一個爭論了很久的話題，程式設計師到底該不該掌握演算法？不同的人有不同的答案，而事實上，很多公司都對演算法有一定的要求，有些公司直接在面試的時候便會要求面試者手寫演算法題。這對程式設計師的技術要求產生了很大的考驗，所以面對如今的大環境，我們必須掌握演算法，才能在未來的工作中佔有一席之地。

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

冒泡排序

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

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

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

示範：

程式碼如下：

@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 统计比较次数
	int count = 0;
	// 第一轮比较
	for (int i = 0; i  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 + "次");
}

執行結果：

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

選擇排序

選擇排序（Selection sort）是一種簡單直覺的排序演算法。它的工作原理是：第一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小（大）元素，然後放到已排序的序列的末端。以此類推，直到全部待排序的資料元素的數量為零。選擇排序是不穩定的排序方法。

示範：

程式碼如下：

@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 <p>執行結果：</p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

實作也非常的簡單，首先在外循環裡定義了一個index變數儲存i的值，這是為了避免重複地比較，因為在每一輪的比較結束後，前i個元素是已經排好序的，所以無需再次比較，只需從i開始即可。後面的比較都是以index位置的元素比較，倘若比較完後index位置的元素是最小值，那就不需要交換，不動即可。而如果找到了比index位置的元素更小的元素，那就將該元素的索引賦值給index，然後繼續比較，直到比較完成，比較完成之後得到的index即為數組中的最小值，那此時只需要將index位置的元素和i位置的元素交換即可。

插入排序

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

插入排序的基本概念是：每個步驟將一個待排序的記錄，按其關鍵碼值的大小插入到前面已經排序的陣列中的適當位置上，直到全部插入完為止。

示範：

程式碼如下：

@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 = 0 && insertValue <p>運行結果：</p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

那麼在這裡，因為陣列元素我們並不確定，所以只能將陣列的第一個元素看成是一個有順序的序列，所以從陣列的第二個元素開始才是我們需要去尋找插入位置的元素。所以外層循環從1開始，然後將arr[i]，也就是當前的第二個元素先保存起來，然後找到待插入元素的前一個元素下標，也就是i-1，此時通過一個while循環去比較。

當insertIndex小於0時應該退出循環，因為此時已經與前面的所有元素比較完畢。在比較的過程中，如果待插入元素小於前一個元素，就將前一個元素後移，也就是將前一個元素的值直接賦值給待插入元素位置。因為在最開始已經將待插入元素進行了保存，所以只需將待插入元素的值賦值給它的前一個元素即可。因為在while循環中insertIndex執行了自減操作，所以它的前一個元素下標應為insertIndex 1。而如果待插入的元素值大於前一個元素，那麼就不會進入while循環，這樣insertIndex 1之後的位置仍然是自己所在的位置，所以賦值後值不改變，後面的操作以此類推。

以上是簡單的排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！