之前為大家講解了一個簡單的二分法數組查找算法,一筆觸而無法停止,看看時間也不算怎麼晚,就再給大家講解一個排序的算法把,在這裡我講解的是選擇排序,也是最簡單與最基礎的排序方法,我想這些簡單與基礎的你把它耳熟能詳了,後面對稍微複雜的算法相對來說也不會有太多的問題,OK,廢話少說,跟到思路一步一步的走吧:
這裡需要注意的是,不管你做什麼,首先你需要去思考做你所需要做的前提是什麼,以至于它所可能産生的問題是什麼,這是必要的,算法嘛,不就是一個思考問題的過程嗎,即一個邏輯的實作過程,是以我要寫這樣一個算法,首先就得考慮,這個算法能達到的效果是什麼,好了,我在這裡就單針對一個對無序數組進行排序來講解吧:
首先,我需要定義一個資料:int[] arr = new int[]{2,4,7,4,8,3,2,4,1,4,0,6,4,3,2,6,77,43,232,43};它是無序的
其次,我們需要對其資料做排序,以便成為有序的數組,在這裡,我們需要思考,我們該怎麼去對這個數組進行排序呢,如果我們以小到大的順序排序或者是大到小的排序都需要對其位置進行兩次以上的交換來輪詢操作,如在數組中a[0]=2,a[1]=4,相對來說在數組中a[10]=0是最小的,這裡就需要有兩個循環進行操作,首先是在第一層循環數組長度為:for(int i=0;i<arr.length-1;i++){},這樣來一次可以對所有數組都進行一次取值來做比較,當然在這裡要假設第一個取值就是最小值,是以需要對其最小值進行儲存起來:int min = i;在第一層循環中我們隻需要循環都倒數第一個對其比較即可,因為在最後一個比較時是自己跟自己進行比較,是以沒必要,不然的話會增加計算過程,進而降低其效率,其次就是我們在固定第一層循環選值後會對目前值與其下一個值進行對比,如:a[0]需要與a[1]進行對比,如a[0]大于a[1]的話,就需要對其值位置進行交換,然而這是輪詢的,也就是說這種對比交換方式是依次都會對比一次,因為可能最小的值在這個數組的最後,是以就需要依次輪詢對比并進行交換後才能判斷得出它的最小值老儲存:for(int j=i;j<arr.length;j++){},再次就是需要在第二層對比後進行判斷,if(arr[min] > arr[j])時就需要對其位置進行交換:min = j;這是交換下标的位置,是以就需要對其儲存後對其值的位置進行交換:if(min != i){int tmp=arr[i];arr[i]=arr[min];arr[min]=tmp;}這裡我們對其算法進行優化,也就是說當min不等于i時才進行位置交換,否則就沒必要進行交換了,因為在這裡最小的小表與這min的下标本身就是同一個下标,是以就不需要進行羅列了,然後不等時就設定一個臨時變量對其初始對比值進行儲存,這是在當我們對比的結果a[n-1]>a[n]時需要對其位置進行交換,并把大的那個數使用臨時位置進行儲存,把小的數進行前移,然後再把放在臨時檔案裡的那個數放在已經前移後的那個資料的位置,依次來進行輪詢對比就可以得到外層第一次循環後内層多次循環比較出來的結果并置于最小值為最前位,當外層循環第二次循環的時候就從a[1]開始了,一次對内層循環進行比較,個得到第二個最小值,知道外層循環依次到最後一個循環位置,這樣就可以得到我們想要的數組排序結果了,OK,上面說的是以小到大的排序方式來做的,如果想要實作大到小的方式來排序的話我想這我拘沒必要再說了吧,下面我把完整的代碼寫在下面,并順以面向對象方式優化後進行展示:
public class SelectionSort{
public static void main(String args[]){
int[] arr = new int[]{3,4,7,2,23,3,4,5,66,7,89,43,23,2,2,43,67,8,9};
selectionSort(arr);
}
private static int selectionSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
int min = i;
for(int j=i;j<arr.length;j++){
if(arr[min] > arr[j]){
min = j;
}
}
if(min != i){
int tmp = arr[i];
int arr[i] = arr[min];
int arr[min] = tmp;
}
System.out.println("第"+i+"次");
for(int ele:arr){
System.out.println(ele+"/t");
}
System.out.println(" ");
}
System.out.println("最終: ");
for(int ele:arr){
System.out.println(ele);
}
return 0;
}
}
以上就是完整的源代碼,隻是這個實作都是在一個方法中執行的,如果這個方法你需要處理很多的資料的話,那樣這個方法相對來說是比較膨脹的,是以我們要對其重構:
public class ReconstructionSelectionSort{
public static void main(String args[]){
int[] arr = new int[]{3,4,7,2,23,3,4,5,66,7,89,43,23,2,2,43,67,8,9};
selectionSort(arr);
}
public static int selectionSort(int[] arr){
for(int i=0;i<arr.length;i++){
int min = i;
for(int j=i;j<arr.length;j++){
min = innerSort(arr,min,j);
}
swap(arr,i,min);
showArray("第"+i+"次",arr);
}
showArray("最終:",arr);
}
public static void showArray(int i,int[] arr){
System.out.print(i);
for(int ele:arr){
System.out.println(ele+"/t");
}
System.out.println(" ");
}
public static void swap(int[] arr,int i,int min){
if(i!=min){
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
public static int innerSort(int[] arr,int min,int j){
if(arr[min]>arr[j]){
min = j;
}
return min;
}
}
以上就是重構過後的代碼,希望能給初學者提供最詳細與完整的講解,如果有問題,自己來郵,本人會第一次回複:[email protected]
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)