排序思想
一.幾種排序思想
1.交換排序:氣泡排序與快速排序
氣泡排序:
思想:比較相鄰元素,違反排序順序則交換,每次冒出一個最大值,直到所有相對的最大值冒出,完成排序。
最基本的排序,不必多說。
複雜度:最壞:O(n*n);最好:O(n);O(n*n)。
1 private static void bubblesort(int[] arr) { 2for (int i = 0; i < arr.length - 1; i++) { // n-1趟 3for (int j = 0; j < arr.length - 1 - i; j++) { // 每趟比n-1-i次 4if (arr[j] > arr[j + 1]) { 5int temp = arr[j + 1]; // 交換 6arr[j + 1] = arr[j]; 7arr[j] = temp; 8} 9} 10} 11 }
快速排序:
思想:
通過一趟排序將要排序的資料分割成獨立的兩部分,其中一部分的所有資料都比另外一部分的所有資料都要小,
然後再按此方法對這兩部分資料分別進行快速排序,整個排序過程可以遞迴進行,以此達到整個資料變成有序序列。
複雜度:最壞:O(n*n);最好:O(n*logn);平均:O(n*logn)。
1 private static void quickSort(int[] arr, int start, int end) { 2if (start > end)// 出口 3return; 4 5int stard = arr[start];// 將陣列的首值設為參照值 6 7int low = start;// 記錄需要排序的下標 8int high = end; 9 10while (low < high) {// 迴圈找出比參照值大和小的數 11while (low < high && stard <= arr[high]) {// 右邊的數比參照大 12high--; 13} 14arr[low] = arr[high];// 此時跳出內層迴圈遇到arr[high]<stard;用右邊的數替換左邊的數 15while (low < high && stard >= arr[low]) {// 左邊的數比參照小 16low++; 17} 18arr[high] = arr[low];// 此時arr[low]>atard 19} 20arr[low] = stard;// 將參照賦給low位置的數 21quickSort(arr, start, low - 1);// 處理所有的小的數字 22quickSort(arr, low + 1, end);// 處理所有的大的數字 23 24}
1.插入排序:簡單插排與希爾排序
簡單插排:
思想:
假設待插入元素之前的元素已經是排序完成的,則每一步將一個待排序的元素,按其值的大小插入前面已經排序的序列中適當位置上,直到全部插入完為止。
其中插入具體是指:對於待插入元素temp,如果i位置還不是插入合適的位置,則把i-1位置的元素填到i位置,直到找到合適的位置,或者遍歷到0位置,將temp填在i位置。
複雜度:最壞:O(n*n);最好:O(n*n);平均:O(n*n)。
1 private static void insertSort(int[] arr) { 2for (int i = 1; i < arr.length; i++) {// 從第二個元素開始遍歷 3if (arr[i] < arr[i - 1]) { // 遇到當前元素比前一個元素小的情況 4int temp = arr[i]; // 儲存當前元素 5int j;//用於遍歷前面所有的情況 6for (j = i - 1; j >= 0 && arr[j] > temp; j--) { // 往前遍歷,找到合適的插入位置 7arr[j + 1] = arr[j]; 8} 9arr[j + 1] = temp; // 將儲存的值存入,即插入到合適的位置,完成排序 10} 11} 12}
希爾排序:又稱縮小增量排序
思想:
按除2遞減的步長將序列分組,每組使用直接插排,直到每組都進行插排後完成排序。
複雜度:最壞:O(n*logn*logn);最好:O(n);平均:取決於間隔序列。
1 private static void shellSort(int[] arr) { 2// 遍歷步長 3for (int step = arr.length / 2; step > 0; step /= 2) { 4// 每次進行直接插入排序 5for (int i = step; i < arr.length; i += step) { 6if (arr[i] < arr[i - step]) { 7int temp = arr[i]; 8int j; 9for (j = i - step; j >= 0 && arr[j] > temp; j -= step) { 10arr[j + step] = arr[j]; 11} 12arr[j + step] = temp; 13} 14} 15} 16}
3.