選擇排序和冒泡排序是Java中常用的兩種排序算法。它們都是基于比較排序的思想,即通過比較元素之間的大小關系來對元素進行排序。
選擇排序是一種簡單直觀的排序算法,它的基本思路是從未排序的元素中找到最小值,然后將其放到已排序的元素序列的末尾,依此類推,直到所有元素都被排序。
public static void selectionSort(int[] arr) { if (arr == null || arr.length == 0) { return; } int len = arr.length; for (int i = 0; i< len - 1; i++) { int minIndex = i; for (int j = i + 1; j< len; j++) { if (arr[j]< arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }
冒泡排序也是一種簡單直觀的排序算法,它的基本思路是相鄰兩個元素進行比較,將大的元素往后放,一趟過后最后一個元素已經排好序,然后再從頭開始比較下一個元素,一直進行到所有元素都排好序為止。
public static void bubbleSort(int[] arr) { if (arr == null || arr.length == 0) { return; } int len = arr.length; for (int i = len - 1; i >0; i--) { for (int j = 0; j< i; j++) { if (arr[j] >arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
選擇排序和冒泡排序的時間復雜度都是O(n^2),但是在具體實現上卻有一些差別。選擇排序的交換次數比冒泡排序少,因為選擇排序每次只記錄最小元素的位置,不需要每次都交換元素。而冒泡排序每次都需要交換相鄰兩個元素,因此交換次數比較多。另外,當數據已經排好序時,選擇排序不需要進行任何比較和交換,而冒泡排序仍然要進行一次比較和交換操作,因此選擇排序在最優情況下的時間復雜度是O(n)。
總之,選擇排序和冒泡排序都有各自的優缺點,具體使用哪種排序算法要根據實際情況而定。