ALGO基礎（一）—— 排序
ALGO基礎（一）—— 排序
- 冒選插希快歸堆，以下均為從小到大排
1 冒泡排序
-
描述：
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
- 針對所有的元素重複以上的步驟，除了最後一個；
- 重複步驟1~3，直到排序完成。
public void bubbleSort(int[] nums){ //每次從頭開始把最大的放到最後 int len = nums.length; for(int i = 0;i<len-1;i++){ [0，len-1) for(int j = 0;j<len-i-1;j++){ [0，len-i-1) if(nums[j]>nums[j+1]){ int tmp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = tmp; } } } }
2 選擇排序
-
在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然後在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最後一個數比較為止。
public void select(int[] nums){ int len = nums.length-1; for(int i = 0;i<len-1;i++){ [0.len-1) int index = i; //最小值下標 for(int j = i+1;j<len;j++) [i+1,len) if(nums[j]<nums[index]) index = j; //交換 int tmp = nums[i]; nums[i] = nums[index]; nums[index] = tmp; } }
3 插入排序
-
一次插一個，插一個排一次
public void insert(int[] nums){ int len = nums.length; // 從下標為1的元素開始選擇位置插入，因為下標為0的只有一個元素，默認是有序的 for (int i = 1; i < len; i++) { [1,len) int temp = nums[i]; // 記錄要插入的數據 // 從已經排序的序列最右邊的開始比較，找到比其小的數 for (int j = i; j > 0&&nums[j-1] > temp; j--) [i.0) j-- && nums[j] = nums[j-1]; nums[j] = temp; } }
4 希爾排序(最小增量排序)
-
先將要排序的一組數按某個增量step（n/2,n為要排序數的 個數）分成若干組，每組中記錄的下標相差d.對每組中全部元素進行插入排序，然後再用一個較小的增量（step/2）對它進行分組，在每組中再進行直接插入 排序。當增量減到1時，進行直接插入排序後，排序完成
-
希爾排序為什麼效率高？
- 插入排序如果在後面來了一個特別小的元素，需要全部移動，那麼排序的效率特別低。
- 希爾排序最重要的就是步長，讓步長不斷地除以二，直到步長為1，優點是如果在數組最後加入一個小元素，他會被很快移到最前面。
public static void shellSort(int[] nums) { int len = nums.length; int temp; for (int step = len / 2; step >= 1; step /= 2) { // 從下標為step的元素開始選擇位置插入，因為前面的魅族只有1個，默認是有序的 for (int i = step; i < len; i++) { [step,len) temp = nums[i]; // 記錄要插入的數據 // 從已經排序的組序列最右邊的開始比較，找到比其小的數 for (int j = i; j > 0&&nums[j-step] > temp; j-=step) [i.0) j- && nums[j] = nums[j-step]; nums[j] = temp; } } }
5 快速排序
-
選擇一個基準元素,通常選擇第一個元素或者最後一個元素,通過一趟掃描，將待排序列分成兩部分,一部分比基準元素小,一部分大於等於基準元素,此時基準元素在其排好序後的正確位置,然後再用同樣的方法遞歸地排序劃分的兩部分。
public void quick(int[] nums, int low, int high) { if (low < high) { int middle = getMiddle(nums, low, high);// 將數組進行一分為二 quick(nums, low, middle - 1); // 對低字表進行遞歸排序 quick(nums, middle + 1, high);// 對高字表進行遞歸排序 } } private int getMiddle(int[] nums, int low, int high) { int tmp = nums[low]; // 數組的第一個作為中軸 while (low < high) { while (low < high && nums[high] >= tmp) { high--; } nums[low] = nums[high]; // 比中軸小的記錄移到低端 while (low < high && nums[low] <= tmp) { low++; } nums[high] = nums[low]; // 比中軸大的記錄移到高端 } nums[low] = tmp; // 中軸記錄到尾 return low; // 返回中軸的位置 }
6 歸併排序
-
歸併（Merge）排序法是將兩個（或兩個以上）有序表合併成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列。自上而下的遞歸。
public void mergeSort(int[] nums,int left,int right){ if(left<right){ //找出中間索引 int center=(left+right)/2; //對左邊數組進行遞歸 mergeSort(nums,left,center); //對右邊數組進行遞歸 mergeSort(nums,center+1,right); //合併 merge(nums,left,center,right); } } private void merge(int[] nums, int left, int center, int right) { int [] tmpArr=new int[nums.length]; int mid=center+1; //third記錄中間數組的索引 int third=left; int tmp=left; while(left<=center&&mid<=right){ //從兩個數組中取出最小的放入中間數組 if(nums[left]<=nums[mid]){ tmpArr[third++]=nums[left++]; }else{ tmpArr[third++]=nums[mid++]; } } //剩餘部分依次放入中間數組 while(mid<=right){ tmpArr[third++]=nums[mid++]; } while(left<=center){ tmpArr[third++]=nums[left++]; } //將中間數組中的內容複製回原數組 while(tmp<=right){ nums[tmp]=tmpArr[tmp++]; } }
