#排序算法總結

1.冒泡排序

解釋：

? 所謂冒泡排序，就是如同水里的泡泡一樣，將合適的值一次次往上冒，直到所有數據全部處理完成。
在數據中的解釋就是：從第一個數開始，每次都將前一個數與后一個數作比較，如果前一個數大于后一個數，則將兩者交換位置（否則不交換），此時，后一個數值已變化，然后再將后一個數與后后一個數作比較，重復操作，直到所有的數都比較完成。

算法過程：

? 先定義一個外循環，控制整個排序次數（排序次數為數據的個數），然后再內嵌一個內循環，在內循環中進行每次排序的比較，內循環的比較次數為：數據個數-當前排序次數，因為，比如說，在第一次比較時，比較得出的結果一定是數據中的最大值，并排在最后，此時，最大值已知，不用再進行比較了，以此類推，每次都會減少一次比較。

時間復雜度：

? 第一次循環n，第二次循環n，綜合為O(n^2)。

算法實現：

public class test1 {public static void main(String[] args) {int[] nums = {5,2,1,4,3,};//下面進行冒泡排序for(int i = 0;i < nums.length-2;i++) { //外層循環控制排序次數for(int j = 0;j < nums.length-1-i;j++) { //內存循環控制每趟比較次數if(nums[j] > nums[j+1]) { //交換位置操作int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;}}}for(int x : nums) {System.out.print(x + " ");}} }

?

2.選擇排序

解釋：

? 所謂選擇排序，就是每次選擇出當前比較數據的最小值，然后將其傳遞到數據的前面。

算法過程：

? 第一步：定義一個外層循環，控制排序次數，循環次數為數據個數-1。
? 第二步：定義一個變量k，這個變量等于外層循環的次數的起始值 i ,目的是存放當前需要操作的數據的第一個數，以便與后面的數比較。
? 第三步：定義一個內層循環，這個內層循環代表著當前需要比較的次數，起始值為k+1，因為k是當前數據的第一個位置，不需要讓自己比自己，結束位置為數據末端，即數據的長度。
? 第四步：將k位置的數與數據比較，如果比較的數小于k位置的數，則將這個索引賦給k，以此類推，最后每次比較結束都會找到當前數據的最小值。
? 第五步，將第i的位置的數據與k的數據交換，即將最小值放到前面。
? 第六步：再次操作以上步驟，直到數據全部完成。

時間復雜度：

? O(n^2)

算法實現：

public class test1 {public static void selectSort01(int[] nums) {for(int i = 0;i < nums.length-1;i++) { //外層循環定義排序次數int k = i; //獲取每次操作的數據的第一個數據的索引，也就是每次從需要比較的第一個數開始（已經比較出的最小數不需要再比較）for(int j = i + 1;j < nums.length;j++) {//內層循環將從第一個數開始往后比較。if(nums[j] < nums[k]) { //判斷前一個數和后一個數之間的大小k = j; //后一個數如果小于前一個數，則將二者的索引交換}}//上述得出當前比較數據的最小值//下方較當前的最小值，與當前比較數據的開頭數據進行交互，最小值將會傳遞到開始的位置，這個數及位置將不會參與下次比較int temp = nums[i]; nums[i] = nums[k];nums[k] = temp;}} public static void main(String[] args) {int[] nums = {2,5,6,3,0,-4};selectSort01(nums);for(int x : nums) {System.out.print(x + " ");} } }

3.插入排序

解釋：

? 所謂插入排序，就是將后面的數與前面的數比較，如果后面的數小于前面的數，就將后面的數插入到前面的數的前面。

算法過程：

? 所謂插入排序，就是從第二個數開始，依次向前比較，如果前面一個數小于這個數，那么就將前面一個數右移，將前面一個數的位置賦空（看了代碼就明白），然后再比較這個數與前前一個數，如果前前一個數大于這個數，則將這個前前的數賦給這個空位置，前前一個數的原位置則就代表了空，重復以上操作，最后將空位置補上當前操作的數即可，直到全部比較完成。

時間復雜度：

? O(n^2);

代碼實現：

public static void insertSort(int[] nums) {for(int i = 1;i < nums.length;i++) {int target = nums[i]; //獲得需要放到確定位置的元素int j = i;while(j > 0 && target < nums[j-1]) { //判斷所要比較的數的索引是否到了最開始的位置，并且比較的數是否小于其前面一個數nums[j] = nums[j-1]; //如果判斷成立，則將前一個數的數據右移，此時前一個數的位置為空，目的是用來存放目標值。j--; //將索引-1，即再比較前面一個數(先減再比較）}nums[j] = target;} } public static void main(String[] args) {// TODO Auto-generated method stubint[] nums = {1,5,3,6,7};insertSort(nums);for(int num : nums) {System.out.print(num);} } }

4.快速排序

解釋：

? 一個效率極其高的排序算法。

算法過程：

? 先設定一個基準（一般為數組最左邊的數）。一個從左往右開始檢索的起始索引，一個從右往左開始檢索的起始索引（如果左索引大于有索引，則被認定為不合法，無需進行一下操作，須提前判斷）。
? 然后先從數組右邊開始向左邊檢索，直到檢索的數小于基準（前提是該索引不能小于左邊的索引），即先暫停，取出這個位置的索引 j。
? 然后再從左往右檢索，直到檢索的數大于基準（前提是該索引不能大于當前右邊的索引），即先暫停。取出這個位置的索引 i。
? 交換兩個索引位置的數。（在兩種索引不相等的前提下，繼續循環上述操作）。
? 當兩個索引相遇時，此時索引右邊的數就是全部大于基準的數，索引左邊的數就是全部小于基準的數。
? 然后將相遇索引位置的數與基準交換。
? 然后分別遞歸相遇索引右邊的數組和左邊的數組（不含索引）
? 最終排序成功。

時間復雜度：

? O(nlogn)；

注意問題：

? 每次檢索時，必須先從右邊開始檢索，因為j在變，i < j始終需要成立。當然還得根據具體情況而定，這是個注意點。

代碼實現：

public static void quickSort(int[] arr,int left,int right) {if(left > right) { //判斷左索引是否大于右索引，如果是，則不合法。直接返回退出排序。return;}int base = arr[left]; //設置基準，一般為最左邊的數int i = left; //設定從左往右檢索角標的實時位置int j = right; //設定從有往左檢索角標的實時位置while(i != j) {//從右往左檢索比基準小的數，找到即先停下，且必須先從右往左執行while(arr[j] >= base && i < j) {j--;}//從左往右檢索比基準大的數，找到即先停下while(arr[i] <= base && i < j) {i++;}//通過上述兩個循環必定找到指定數，然后將兩個數交換int temp = arr[j];arr[j] = arr[i];arr[i] = temp;}//上述循環結束代表i==j了，即兩個角標重合//此時將基準與重合位置的數交換arr[left] = arr[i];arr[i] = base;//遞歸繼續執行上述操作//遞歸排序左邊的數quickSort(arr, left, i - 1);//遞歸排序有邊的數quickSort(arr, i+1, right); }

?

?

#查找算法總結

1.二分查找（折半查找）

解釋：

? 在一個事先排好序的數組中，查找一個數所在的索引位置。

算法過程：

? *提前準備：
? 定義一個方法，設定兩個參數，第一個為排好序的數組，第二個為需要查詢的數。在方法內部定義三個變量，分別為top(代表每次查找部分的第一個數的索引)，bottom(代表每次查找部分的最后一個數的索引)，mid(代表每次查找部分的中間位置的數，mid=(top+bottom)/2)。
? *過程：
? 首判斷我們每次執行后的top和bottom是否不在同一位置，如果不在，則代表全部查完了也沒找到，此時須返回查詢失敗標志，反之，代表還有數可查，繼續查詢。
? 每次查詢的時候mid都會變成當前查詢部分的中間值索引，然后判斷該中間值是否與查詢的數相等，若相等，則返回該中間值索引，查詢成功。否則，判斷，該中間值是大于查詢值還是小于查詢值。如果大于查詢值，則代表查詢的值一定在中間值索引的左邊，否則，在其右邊。此時，目標數組就會變成需要查詢的部分，然后改變top和bottom及mid到對應的新值。重復執行以上過程，直到查詢成功或失敗。

代碼實現：

public static int search(int[] nums,int num) {int top = 0;int bottom = nums.length - 1;while(top <= bottom) {int mid = (top + bottom)/2;if(num == nums[mid]) {return mid;}else if(num < nums[mid]) { //代表目標數num在數組的左邊bottom = mid - 1;mid = (top + bottom)/2;}else { //代表目標數num在數組的右邊top = mid + 1;mid = (top + bottom)/2;}}return -1; //查詢失敗返回值}

?

總結

以上是生活随笔為你收集整理的排序算法和查找算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。