Flash And Tool Share

Array.every
AS3 function every(callback:Function, thisObject:* = null):Boolean
function callback(item:*, index:int, array:Array):Boolean;
每個元素都去執行callback，只要有一個回傳false就終止。

Array.filter
AS3 function filter(callback:Function, thisObject:* = null):Array
function callback(item:*, index:int, array:Array):Boolean;
透過callback過濾元素，彙整callback回傳true的元素所組成的新陣列。

Array.forEach
AS3 function forEach(callback:Function, thisObject:* = null):void
function callback(item:*, index:int, array:Array):void;
每個元素都去執行callback，無回傳值。

Array.map
AS3 function map(callback:Function, thisObject:* = null):Array
function callback(item:*, index:int, array:Array):String;
使用callback處理每一個元素並返回，匯集返回結果組成新數組，函數返回類型為元素類型。

Array.some
AS3 function some(callback:Function, thisObject:* = null):Boolean
function callback(item:*, index:int, array:Array):Boolean;
每個元素都去執行callback，只要有一個回傳true就終止。

一、概論
對於數據的處理工作，排序是其最基本的運算之一。在當今的計算機系統中，花費在排序上的時間佔系統CPU運行時間的很大比重。有資料表明，在一些商用計算機上，在排序上的CPU時間達到20％至60％。為了提高計算機的工作效率，人們提出了各種各樣的排序方法和算法。這些算法有力地發展、並充分地展示了算法設計的某些重要原則和高超技巧。因此，對於計算專業人員來說掌握排序算法是十分重要的。

二、排序算法簡介
本次課程中我們將介紹六種排序方法：插入排序，選擇排序，冒泡排序，希爾排序，快速排序及二路歸併。

<1>直接選擇排序(Selection Sort)：簡單的選擇排序，它的比較次數一定：n(n-1)/2。也因此無論在序列何種情況下，它都不會有優秀的表現（從上100K的正序和反序數據可以發現它耗時相差不多，相差的只是數據移動時間），可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發現它在一般情況下將快於冒泡排序。

<2>直接插入排序(Insertion Sort)：簡單的插入排序，每次比較後最多移掉一個逆序，因此與冒泡排序的效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值移動，所以直接插入排序將要優於冒泡排序。直接插入法也是一種對數據的有序性非常敏感的一種算法。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較。

<3>冒泡排序(Bubble Sort)：將相鄰的兩個數據元素按關鍵字進行比較，如果反序，則交換。對於一個待排序的數據元素序列，經一趟排序後最大值數據元素移到最大位置，其它值較大的數據元素向也最終位置移動，此過程為一次起泡。然後對下面的記錄重複上述過程直到過程中沒有交換為止，則已完成對記錄的排序。

<4>快速排序(Quick Sort)：是冒泡排序的改進，它通過一次交換能消除多個逆序，這樣可以減少逆序時所消耗的掃描和數據交換次數。在最優情況下，它的排序時間複雜度為Ｏ(nlog2n)。即每次劃分序列時，能均勻分成兩個子串。但最差情況下它的時間複雜度將是Ｏ(n^2)。即每次劃分子串時，一串為空，另一串為m-1（程序中的100K正序和逆序就正是這樣，如果程序中採用每次取序列中部數據作為劃分點，那將在正序和逆時達到最優）。從100K中正序的結果上看“快速排序”會比“冒泡排序”更慢，這主要是“冒泡排序”中採用了提前結束排序的方法。有的書上這解釋“快速排序”，在理論上講，如果每次能均勻劃分序列，它將是最快的排序算法，因此稱它作快速排序。雖然很難均勻劃分序列，但就平均性能而言，它仍是基於關鍵字比較的內部排序算法中速度最快者。

<5>希爾排序(Shell Sort)：增量的選擇將影響希爾排序的效率。但是無論怎樣選擇增量，最後一定要使增量為１，進行一次直接插入排序。但它相對於直接插入排序，由於在子表中每進行一次比較，就可能移去整個經性表中的多個逆序，從而改善了整個排序性能。希爾排序算是一種基於插入排序的算法，所以對數據有序敏感。

<6>歸併排序(Merge Sort)：歸併排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸併，將有無比的優勢。其時間複雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數據的有序性不敏感。若數據節點數據量大，那將不適合。但可改造成索引操作，效果將非常出色。

三、排序方法的選擇
因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法很重要
(1)若n較小，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好，它會比選擇更少的比較次數；
但當記錄規模較大時，因為直接選擇移動的記錄數少於直接插人，所以宜用選直接選擇排序。
這兩種都是穩定排序算法。

(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜(這裡的隨機是指基準取值的隨機，原因見上的快速排序分析)；這裡快速排序算法將不穩定。

(3)若n較大，則應採用時間複雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸併排序序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分佈時，快速排序的平均時間最短；
堆排序雖不會出現快速排序可能出現的最壞情況。但它需要建堆的過程。這兩種排序都是不穩定的。
歸併排序是穩定的排序算法，但它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然後再合併，在效率上將有所提高。

(4)特殊的箱排序、基數排序
它們都是一種穩定的排序算法，但有一定的局限性：
1>關鍵字可分解。
2>記錄的關鍵字位數較少，如果密集更好
3>如果是數字時，最好是無符號的，否則將增加相應的映射複雜度，可先將其正負分開排序。

四、AS中排列數組
1.申請一個長度為n的數組A：
var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
A[i] = i;
}
trace(A);

2.將長度為n的數組打亂次序：
for (i=0; i < n; i++) {
var ran = int(Math.random()*n);
var temp = A[i];
A[i] = A[ran];
A[ran] = temp;
}
trace(A)

3.將數組中的所有元素倒排序：
A.reverse();
trace(A)

五、AS實現排序算法：

在執行各各排序算法之前，已經默認存在一個亂序的數組A[400]，默認代碼：

var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
 A[i] = i;
}
for (i=0; i < n; i++) {
 var ran = int(Math.random()*n);
 var temp = A[i];
 A[i] = A[ran];
 A[ran] = temp;
}
 

1.直接插入排序

for (i = 0; i < n; i++) {
 var temp = A[i];
 for (j = i; j > 0 && temp < A[j - 1]; j--) {
  A[j] = A[j - 1];
  A[j - 1] = temp;
 }
}


2.直接選擇排序

for (i = 0; i < n - 1; i++) {
 var s:Number = i;
 for (j = s + 1; j < n; j++) {
  if (A[j] < A[s]) {
   s = j;
  }
 }
 var temp = A[i];
 A[i] = A[s];
 A[s] = temp;
}


3.冒泡排序

for (i = 0; i < n; i++) {
 for (j = i; j < n; j++) {
  if (A[i] > A[j]) {
   var temp = A[i];
   A[i] = A[j];
   A[j] = temp;
  }
 }
}


4.希爾排序

var increment = 6;
while (increment > 1) {
 increment = int(increment / 3 + 1);
 Shellpass(increment);
}
function Shellpass(c) {
 for (i = c; i < n; i++) {
  if (A[i] < A[i - c]) {
   var temp = A[i];
   j = i - c;
   do {
    A[j + c] = A[j];
    j = j - c;
   } while (j > 0 && temp < A[j]);
   A[j + c] = temp;
  }
 }
}


5.快速排序

function QuickSort(A, low, hig) {
 var i = low, j = hig;
 var mid = A[int((low + hig) / 2)];
 do {
  while (A[i] < mid) {
   i++;
  }
  while (A[j] > mid) {
   j--;
  }
  if (i <= j) {
   var temp = A[i];
   A[i] = A[j];
   A[j] = temp;
   i++;
   j--;
  }
 } while (i <= j);
 if (low < j) {
  arguments.callee(A,low,j);
 }
 if (i < hig) {
  arguments.callee(A,i,hig);
 }
}
QuickSort(A,0,n - 1);


6.二路歸併

var B:Array = new Array(A.length);
for (k = 1; k < n; k *= 2) {
 MergePass(k);
}
function MergePass(len) {
 for (i = 0; i + 2 * len < n; i = i + 2 * len) {
  MergeA(i,i + len - 1,i + 2 * len - 1);
 }
 if (i + len < n) {
  MergeA(i,i + len - 1,n - 1);
 }
}
function MergeA(low, m, hig) {
 var i = low, j = m + 1, z = 0;
 while (i <= m && j <= hig) {
  B[z++] = (A[i] <= A[j]) ? A[i++] : A[j++];
 }
 while (i <= m) {
  B[z++] = A[i++];
 }
 while (j <= hig) {
  B[z++] = A[j++];
 }
 for (z = 0, i = low; i <= hig; z++, i++) {
  A[i] = B[z];
 }
}

Flash And Tool Share

搜尋部落格文章

2012年7月31日星期二

FlashDevelop無法執行debug解決方法

2012年7月27日星期五

Array 各項過濾方法參數

2012年6月19日星期二

資料結構排序演算法

2012年6月15日星期五

Object資料的深複製

ActionScript 命名規則定義

2012年6月11日星期一

Adobe Flash CS6 CS5.5 本機Help文件

2012年5月23日星期三

TweenMax用法統整

搜尋部落格文章

2012年7月31日 星期二

2012年7月27日 星期五

2012年6月19日 星期二

2012年6月15日 星期五

2012年6月11日 星期一