DIV CSS 佈局教程網

Java 四種經典排序演算法完全解析
編輯:關於JavaScript     

排序是程式的基礎功。本文整理了 Java 中最經典的四種排序法:插入法、氣泡法、選擇法與 Shell 排序。其中選擇法是氣泡法的改良,Shell 排序則是插入法的改良,因此從本質上又可歸納為「插入」與「交換」兩大流派。

一、插入法:

遍歷排序集合,每到一個元素就把它與前面所有元素逐一比較,讓符合條件的元素往後挪,把當前元素放到它該在的位置。交換靠相鄰元素移動完成,用雙重迴圈控制。這就像整理一副撲克牌,每摸一張就插入到手中正確的位置。

 public void sort(int[] data) { int temp; for(int i=1; i〈data.length; i++){ for(int j=i; (j〉0)&&(data[j]〉data[j-1]); j--){ temp=date[j]; data[j]=data[j-1]; data[j-1]=temp; } } } 

二、氣泡法:

它的內層迴圈保證每遍歷一次,集合中最小(或最大)的元素就會浮到正確位置,下一次再處理次小元素,以此類推。無論資料分布如何,交換移動的次數大致固定,是四者中較慢的一種,同樣以雙重迴圈控制。

 public static int [] maopao(int[] data) { int temp; for(int i=0; i〈data.length-1; i++){ for(int j=i+1; j〈data.length; j++){ if(data[i]〈data[j]){ temp=data[i]; data[i]=data[j]; data[j]=temp; } } } return data; 

三、選擇法:

它只透過遍歷記錄最小(或最大)元素的位置,一整輪下來才做一次交換,比較過程中並不急著搬動元素。對於交換成本較高的資料特別合適——每一輪只處理當前範圍內最極端的那個值。

 public static void xuanze(int[] data) { int temp; for (int i = 0; i 〈 data.length; i++) { int lowIndex = i; for (int j = data.length - 1; j 〉 i; j--) { if (data[j] 〉 data[lowIndex]) { lowIndex = j; } } temp=data[i]; data[i]=data[lowIndex]; data[lowIndex]=temp; } } 

四、Shell 排序:

它是插入排序的改良版,會先將元素依某個增量分組,讓每一組在局部範圍內先變得大致有序,最後再對全體做一次插入排序。透過逐步縮小增量,大幅減少了元素移動的次數。

 public void sort(int[] data) { for(int i=data.length/2; i〉2; i/=2){ for(int j=0; j〈i; j++){ insertSort(data,j,i); } } insertSort(data,0,1); } private void insertSort(int[] data, int start, int inc) { int temp; for(int i=start+inc; i〈data.length; i+=inc){ for(int j=i; (j〉=inc)&&(data[j]〈data[j-inc]); j-=inc){ temp=data[j]; data[j]=data[j-inc] data[j-inc]=temp; } } } 

把這四種排序一起理解,你就能清楚看出「交換相鄰元素」與「記錄極值再搬移」兩種思維的差異,也能體會 Shell 排序如何用分組策略替插入排序加速。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved