学步园

private function selectionSort(array:Array):void
{

   var len:int = array.length;

   for (var i:int = 0; i < len - 1; i++)

   {

       var min:int = array[i];

       var minIndex:int = i;

       for (var k:int = i + 1; k < len; k++)

       {

           if (array[k] < min)

           {

               min = array[k];

               minIndex = k;

           }

       }

       if (minIndex != i)

       {

           array[minIndex] = array[i];

           array[i] = min;

       }

   }
}

 

2、冒泡排序：依次交换，每次排序之后最大的数都到了最后

private function insertSort(array:Array):void
{

    var len:int = array.length;

   for (var i:int = 1; i < len; i++)

   {

       var temp:int = array[i];

       for (var k:int = i - 1; k >= 0 && array[k] > temp; k--)

       {

           array[k + 1] = array[k];

       }

       array[k + 1] = temp;

   }
}

3、插入排序（二分插入）:因为每次插入前前面的数组都已经排好序，所以可以通过二分法找到合适的插入位置

private function binaryInsertSort(array:Array):void
{

   var len:int = array.length;

   var low:int;

   var high:int;

   var mid:int;

   

   for (var i:int = 1; i < len; i++)

   {

       var temp:int = array[i];

       low = 0;

       high = i - 1;

       

       while (low <= high)

       {

           mid = (low + high) / 2;

            if (temp > array[mid])

           {

               low = mid  + 1;

           }else {

               high = mid - 1;

           }

       }

       for (var j:int = i - 1; j > high; j--)

       {

           array[j + 1] = array[j];

       }

       array[high + 1] = temp;

   }
}

 

4、希尔排序（简单实用的排序方法）:通过改进插入排序方法而来（有间隔的插入排序），虽然代码很好写，但是我一直都不是很懂为什么这样更快

private function shellSort(array:Array):void
{

   var len:int = array.length;

   var distance:int = len;

   

   while (distance > 1)

   {

       distance = distance / 3 + 1;

       for (var i:int = distance; i < len; i++)

       {

           var temp:int = array[i];

                     for (var k:int = i - distance; k >= 0 && array[k] > temp; k = k - distance)

           {

               array[k + distance] = array[k]; 

           }

           array[k + distance] = temp;

       }

   }
}

 

5、归并排序：利用分治的思想，通过递归，一句话，就是拆分拆分再拆分，合并合并再合并。

private function mergeSort(array:Array):void
{

   var len:int = array.length;

   if (len > 1)

   {

       var firstArray:Array = array.slice(0, len / 2);

       mergeSort(firstArray);

       var secondArray:Array = array.slice(len / 2, len);

       mergeSort(secondArray);

       var tempArray:Array = mergeArray(firstArray, secondArray);

       

       var length:int = array.length;

       for (var i:int = 0; i < length; i++)

       {

           array[i] = tempArray[i];

       }

   }
}

private function mergeArray(firstArray:Array, secondArray:Array):Array
{

   var firstIndex:int = 0; 

   var secondIndex:int = 0;

   var tempIndex:int = 0;

   

   var tempArray:Array = [];

   

   var firstLen:int = firstArray.length;

   var secondLen:int = secondArray.length;

   

   while (firstIndex < firstLen && secondIndex < secondLen)

   {

       if (firstArray[firstIndex] < secondArray[secondIndex])

       {

           tempArray[tempIndex++] = firstArray[firstIndex++];

       }

       else 

       {

           tempArray[tempIndex++] = secondArray[secondIndex++];

       }

   }

   

   while (firstIndex < firstLen)

   {

       tempArray[tempIndex++] = firstArray[firstIndex++];

   }

   

   while (secondIndex < secondLen)

   {

       tempArray[tempIndex++] = secondArray[secondIndex++];

   }

   

   return tempArray;
}

 

6、快速排序：把数组分成左小右大，递归，完事

private function quickSort(array:Array, low:int, high:int):void
{

   if (low < high)

   {

       var pivotIndex:int = halfArray(array, low, high);

       quickSort(array, low, pivotIndex - 1);

       quickSort(array, pivotIndex + 1, high);

   }
}

private function halfArray(array:Array, low:int, high:int):int
{

   var pivot:int = array[low];

   

   while (low < high)

   {

       while (low < high && array[high] >= pivot)

       {

           high--;

       }

       array[low] = array[high];

       while (low < high && array[low] <= pivot)

       {

           low++;

       }

       array[high] = array[low];

   }

   array[low] = pivot;

   return low;
}

 

7、堆排序：利用堆的思想对数组进行排序（最大堆就是父节点比子节点都大）

private function heapSort(array:Array):void
{

   var len:int = array.length;

   for (var i:int = 1; i < len; i++)

   {

       makeHeap(array, i);

   }

   for (var k:int = len - 1; k > 0; k--)

   {

       var temp:int = array[k];

       array[k] = array[0];

       array[0] = temp;

       updateHeap(array, k - 1);

   }
}

private function makeHeap(array:Array, last:int):void
{

   var currentIndex:int = last;

   while (currentIndex > 0)

   {

             if (array[currentIndex] > array[int((currentIndex - 1) / 2)])

       {

           var temp:int = array[currentIndex];

                                      array[currentIndex] = array[int((currentIndex - 1) / 2)];

           array[int((currentIndex - 1) / 2)] = temp; 

           

           currentIndex = (currentIndex - 1) / 2;

       }

       else 

       {

           break;

       }

   }
}

private function updateHeap(array:Array, last:int):void
{

   var currentIndex:int = 0; 

   var isHeap:Boolean = false;

   

   while (!isHeap)

   {

       var leftIndex:int = 2 * currentIndex + 1;

       var rightIndex:int = 2 * currentIndex + 2;

       var maxIndex:int = currentIndex;

       

             if (leftIndex <= last && array[currentIndex] < array[leftIndex])

       {

           maxIndex = leftIndex;

       }

             if (rightIndex <= last && array[maxIndex] < array[rightIndex])

       {

           maxIndex = rightIndex;

       }

       

       if (maxIndex != currentIndex)

       {

           var temp:int = array[currentIndex];

           array[currentIndex] = array[maxIndex];

           array[maxIndex] = temp;

           currentIndex = maxIndex;

       }

       else

       {

           isHeap = true;            

       }

   }
}

 

8、基数排序（利用桶的思想，遍历把数组项装进不同的桶，再组合，在装桶，循环几次即可（跟最大位数跟所选基数有关））

/**
* 基数排序
* @param array    待排序的数组
* @param base    基数
*/        
private function radixSort(array:Array, base:int = 10):void
{

   var maxLen:int = findLen(array, base);

   var arrLen:int = array.length;

   var temp:int = 1;

   

   var container:Array = [];

   for (var i:int = 0; i < base; i++)

       container[i] = [];

   

   while (maxLen--)

   {

       //    放到相应的容器中

       for (var j:int = 0; j < arrLen; j++)

       {

           container[int(array[j] / temp) % base].push(array[j]);

       }

       temp *= base;

       //    重新排列

       array.length = 0;

       var containerLen:int = container.length;

       for (var k:int = 0; k < containerLen; k++)

       {

           if(container[k].length)

           {

               var len:int = container[k].length;

               for (var m:int = 0; m < len; m++)

               {

                   array.push(container[k][m]);

               }

               

               container[k].length = 0;

           }

       }

   }
}

/**
* 找出数组项最大长度
* @param array    待排序的数组
* @param base    基数
* @return 
*/        
private function findLen(array:Array, base:int):int
{

   var maxLen:int = 1;

   var temp:int = base;

   var len:int = array.length;

   for (var i:int = 0; i < len; i++)

   {

       while (array[i] >= temp)

       {

           maxLen++;

           temp *= base;

       }

   }

   

   return maxLen;
}

 

over！