一文帶你瞭解Java排序算法
一、選擇排序
選擇排序是一種簡單直觀的排序算法,無論什麼數據進去都是 O(n²) 的時間復雜度。所以用到它的時候,數據規模越小越好。唯一的好處可能就是不占用額外的內存空間瞭吧
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。
重復第二步,直到所有元素均排序完畢。
public static void selectSort(int[] arr) { //選擇排序 if(arr == null || arr.length < 2) { return; } int n = arr.length; for (int i = 0; i < n; i++) { int minValueIndex = i; for (int j = i+1; j < n; j++) { minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex; } swap(arr,i,minValueIndex); } } public static void swap(int[] arr,int i,int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println(); } public static void main(String[] args) { int[] arr = {7,5,1,9,4,2,6}; printArray(arr); selectSort(arr); printArray(arr); }
二、冒泡排序
**冒泡排序算法的原理如下: **
1.比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
2.對每一對相鄰元素做同樣的工作,從開始第一對到結尾的最後一對。在這一點,最後的元素應該會是最大的數。
3.針對所有的元素重復以上的步驟,除瞭最後一個。
4.持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較。
public static void bubbleSort(int[] arr) { if(arr == null || arr.length < 2) { return; } int n = arr.length; for (int i = n-1; i >= 0; i--) { for (int j = 0; j < i; j++) { if(arr[j] > arr[j+1]) { swap(arr,j,j+1); } } } } public static void swap(int[] arr,int i,int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr = {14,6,3,10,2}; printArray(arr); bubbleSort(arr); printArray(arr); }
三、插入排序
插入排序是指在待排序的元素中,假設前面n-1(其中n>=2)個數已經是排好順序的,現將第n個數插到前面已經排好的序列中,然後找到合適自己的位置,使得插入第n個數的這個序列也是排好順序的。按照此法對所有元素進行插入,直到整個序列排為有序的過程,稱為插入排序
public static void insertSort(int[] arr) { if(arr == null || arr.length < 2) { return; } int n = arr.length; for (int i = 1; i < n; i++) { int currIndex = i; while(currIndex - 1 >= 0 && arr[currIndex-1] > arr[currIndex]) { swap(arr,currIndex,currIndex-1); currIndex--; } } } public static void swap(int[] arr,int i,int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr = {3,6,1,5,2}; printArray(arr); insertSort(arr); printArray(arr); }
插入排序優化
public static void insertSort1(int[] arr) { if(arr == null || arr.length < 2) { return; } int n = arr.length; for (int i = 1; i < n; i++) { for (int j = i-1; j >= 0; j--) { if(arr[j] > arr[j+1]) { swap(arr,j,j+1); }else { break; } } } }
到此這篇關於一文帶你瞭解Java排序算法的文章就介紹到這瞭,更多相關Java排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!