摘要:插入排序就這么簡單從上面已經講解了冒泡和選擇排序了,本章主要講解的是插入排序,希望大家看完能夠理解并手寫出插入排序的代碼,然后就通過面試了如果我寫得有錯誤的地方也請大家在評論下指出。
插入排序就這么簡單
從上面已經講解了冒泡和選擇排序了,本章主要講解的是插入排序,希望大家看完能夠理解并手寫出插入排序的代碼,然后就通過面試了!如果我寫得有錯誤的地方也請大家在評論下指出。
插入排序介紹來源百度百科:
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據,算法適用于少量數據的排序,時間復雜度為O(n^2)。是穩定的排序方法。
將一個數據插入到已經排好序的有序數據中
將要排序的是一個亂的數組int[] arrays = {3, 2, 1, 3, 3};
在未知道數組元素的情況下,我們只能把數組的第一個元素作為已經排好序的有序數據,也就是說,把{3}看成是已經排好序的有序數據
一、第一趟排序用數組的第二個數與第一個數(看成是已有序的數據)比較
如果比第一個數大,那就不管他
如果比第一個數小,將第一個數往后退一步,將第二個數插入第一個數去
int temp; if (arrays[1] > arrays[0]) { //如果第二個數比第一個數大,直接跟上 } else { //如果第二個數比第一個數小,將第一個數后退一個位置(將第二個數插進去) temp = arrays[1]; arrays[1] = arrays[0]; arrays[0] = temp; } System.out.println("公眾號Java3y" + arrays);二、第二趟排序
用數組的第三個數與已是有序的數據{2,3}(剛才在第一趟排的)比較
如果比2大,那就不管它
如果比2小,那就將2退一個位置,讓第三個數和1比較
如果第三個數比1大,那么將第三個數插入到2的位置上
如果第三個數比1小,那么將1后退一步,將第三個數插入到1的位置上
//第二趟排序-------------------- if (arrays[2] > arrays[1]) { //如果第三個數比第二個數大,直接跟上 } else { //如果第三個數比第二個數小,將第二個數往后退一個位置,讓第三個數跟第一個數比 temp = arrays[2]; arrays[2] = arrays[1]; //如果第三個數比第一個大,那就插入到第二個數中 if (temp > arrays[0]) { arrays[1] = temp; } else { //如果第三個數比第一個小,將第三個數插入到第一個數前面 int swapTemp = arrays[0]; arrays[0] = temp; arrays[1] = swapTemp; } } System.out.println("公眾號Java3y" + arrays);
....
從前兩趟排序我們可以摸出的規律:
首先將已排序的數據看成一個整體
一個數組是需要n-1趟排序的,總是用后一位跟已排序的數據比較(第一趟:第二位跟已排序的數據比,第二趟:第三位跟已排序的數據比)
用第三位和已排序的數據比,實際上就是讓第三位數跟兩個數比較,只不過這兩個數是已經排好序的而已。而正是因為它排好序的,我們可以使用一個循環就可以將我們比較的數據插入進去
//臨時變量 int temp; //外層循環控制需要排序的趟數(從1開始因為將第0位看成了有序數據) for (int i = 1; i < arrays.length; i++) { temp = arrays[i]; //如果前一位(已排序的數據)比當前數據要大,那么就進入循環比較[參考第二趟排序] while (arrays[i - 1] > temp) { //往后退一個位置,讓當前數據與之前前位進行比較 arrays[i] = arrays[i - 1]; //不斷往前,直到退出循環 i--; } //退出了循環說明找到了合適的位置了,將當前數據插入合適的位置中 arrays[i] = temp; }
上面的代碼還缺少了一個條件:如果當前比較的數據比已排序的數據都要小,那么while中的arrays[i - 1]會比0還要小,這會報錯的。
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Main.main(Main.java:61)
我們應該加上一個條件:i>=1時才可以,如果i=1了下次再進去的時候就退出循環,讓當前數據插入到[0]的位置上
復用i變量的話會導致多幾次無謂的比較的,所以我們使用另一個變量j。完整的代碼是這樣的:
public static void sort(int[] arrays) { //臨時變量 int temp; //外層循環控制需要排序的趟數(從1開始因為將第0位看成了有序數據) for (int i = 1; i < arrays.length; i++) { temp = arrays[i]; //如果前一位(已排序的數據)比當前數據要大,那么就進入循環比較[參考第二趟排序] int j = i - 1; while (j >= 0 && arrays[j] > temp) { //往后退一個位置,讓當前數據與之前前位進行比較 arrays[j + 1] = arrays[j]; //不斷往前,直到退出循環 j--; } //退出了循環說明找到了合適的位置了,將當前數據插入合適的位置中 arrays[j + 1] = temp; } System.out.println("公眾號Java3y" + arrays); }四、插入排序優化
二分查找插入排序的原理:是直接插入排序的一個變種,區別是:在有序區中查找新元素插入位置時,為了減少元素比較次數提高效率,采用二分查找算法進行插入位置的確定。
參考資料:http://www.cnblogs.com/heyuquan/p/insert-sort.html
五、擴展閱讀C語言實現第一種方式:
void InsertSortArray ( int arr[], int n) { //int arr[]={2,99,3,1,22,88,7,77,54}; for (int i = 1; i < n; i++)// 循環從第二個數組元素開始 { int temp = arr[i];//temp標記為未排序的第一個元素 while (i >= 0 && arr[i - 1] > temp) //將temp與已排序元素從大到小比較,尋找temp應插入的元素 { arr[i] = arr[i - 1]; i--; } arr[i] = temp; } }
C語言實現第二種方式:
void insert ( int arr[], int n) { int key = arr[n]; int i = n; while (arr[i - 1] > key) { arr[i] = arr[i - 1]; i--; if (i == 0) break; } arr[i] = key; } void insertionSort ( int arr[], int n) { int i; for (i = 1; i < n; i++) { insert(arr, i); } }
測試代碼:
main() { int arr[] = {99, 2, 3, 1, 22, 88, 7, 77, 54}; int i; insertionSort(arr, 9); for (int i = 0; i < 9; i++) cout << arr[i] << endl; return 0; }
參考資料:
https://www.cnblogs.com/xiaoming0601/p/5862793.html
http://blog.csdn.net/jianyuerensheng/article/details/51254415
如果文章有錯的地方歡迎指正,大家互相交流。習慣在微信看技術文章,想要獲取更多的Java資源的同學,可以關注微信公眾號:Java3y
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68878.html
摘要:不斷執行這個操作代碼實現快速排序用遞歸比較好寫如果不太熟悉遞歸的同學可到遞歸就這么簡單。 前言 大概花了一周的時間把八大基礎排序過了一遍,這篇博文主要是用來回顧一下八大基礎排序的要點和一些總結~ 回顧: 冒泡排序就這么簡單 選擇排序就這么簡單 插入排序就這么簡單 快速排序就這么簡單 歸并排序就這么簡單 堆排序就這么簡單 希爾排序就這么簡單 基數排序就這么簡單 總的來說:快速排序是用...
摘要:比較函數應該具有兩個參數和,其返回值如下若小于,在排序后的數組中應該出現在之前,則返回一個小于的值。把這個安排好,再繼續之前的冒泡排序。 受大學室友的鼓動,我也打算利用公眾平臺來記錄自己的前端知識積累,同時呢,自己總結的東西,總歸會有局限性,希望小伙伴能給我指點迷津。知識就是一張巨大的網,作為一名摸不清頭緒的入學者,唯一能做的事情就是吐好每一根絲,絲擰成線,線再織成網。好啦,開機儀式o...
摘要:插入排序的過程就是將待插元素一個個插入初始有序部分的過程。而直接插入排序就是把未排序的序列里的第一位數與前面的有序數列進行比較,凡是比它大的都向后移動一位,直到找到正確的位置進行交換。 1.前言 從上大學開始,算法與數據結構這東西我是一直心心念念,奈何又懶又蠢,這么基礎科目一直沒啥成效。但是如鯁在喉,如果再不學的話可能就成為一塊心病了。所以雖然和現在工作沒啥關系但還是決定學一下基礎,聊...
閱讀 1648·2019-08-30 15:44
閱讀 2570·2019-08-30 11:19
閱讀 400·2019-08-30 11:06
閱讀 1565·2019-08-29 15:27
閱讀 3082·2019-08-29 13:44
閱讀 1627·2019-08-28 18:28
閱讀 2357·2019-08-28 18:17
閱讀 1986·2019-08-26 10:41