選擇排序法和冒泡法是兩種經典的簡單排序算法,都是用來將一組數據按照從小到大或從大到小的順序排列。
選擇排序法的核心思想是每次選出序列中最小的元素,放在最前面,然后再在剩余的元素中選出最小的元素,放在第二個位置,以此類推,直到整個序列排列完成。
public static void selectionSort(int[] arr) { if (arr == null || arr.length< 2) { return; } for (int i = 0; i< arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j< arr.length; j++) { minIndex = arr[j]< arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
冒泡法的核心思想是比較相鄰的兩個元素,如果順序不對就交換位置,每輪比較選出的最大元素沉到序列的最后面。
public static void bubbleSort(int[] arr) { if (arr == null || arr.length< 2) { return; } for (int i = arr.length - 1; i >0; i--) { for (int j = 0; j< i; j++) { if (arr[j] >arr[j + 1]) { swap(arr, j, j + 1); } } } }
兩種排序算法的時間復雜度都是O(n^2),但選擇排序法更有效率。這是因為選擇排序法每次只需要交換一次元素,而冒泡法可能每次都需要進行交換操作。
選擇排序法和冒泡法都是簡單排序算法中的經典方法,但是在實際應用中都已不太常用。因為隨著數據規模的增大,它們的時間復雜度會越來越高,效率越來越低。