蠻力法在排序算法中的應用

對于一個排序問題，我們能想到的最簡單的排序方法就是選擇和冒泡

1、選擇排序：時間復雜度O(n^2)

public class Main {public static void main(String[] args) {int[] a = {89, 45, 68, 90, 29, 34, 17};int min;for (int i = 0; i < a.length-1; i++) {min = i;for (int j = i+1; j < a.length; j++) {if (a[j] < a[min]) {min = j;}}int temp = a[i];a[i] = a[min];a[min] = temp;}for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}} }

選擇排序的思路就是如此，雖也有優化思路，例如每次迭代出最大值和最小值，放在開頭和結尾。但是選擇排序必然要編譯算真整個數組，所以最好的優化結果也是O(n^2)。

2、冒泡排序：時間復雜度O(n^2)

public class Main {public static void main(String[] args) {int[] a = {89, 45, 68, 90, 29, 34, 17};int min;for (int i = 0; i < a.length-1; i++) {for (int j = 0; j < a.length-1-i; j++) {if (a[j+1] < a[j]) {int temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}} } 發現問題：對于冒泡排序我們都知道，即使已經排好順序，循環還是會繼續進行，即使只比較不交換。

優化思路：當判斷到數組已經不再發生改變之后就終止循環。

當然，這就是蠻力法的一個應用，通過蠻力的解法來找到優化的思路

總結

以上是生活随笔為你收集整理的蛮力法在排序算法中的应用（JAVA）--选择排序、冒泡排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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