package
{
import flash.display.Sprite; public class Sort extends Sprite
{
private var arr:Vector.<int>;
public function Sort()
{
arr=new Vector.<int>();
arr.push(34,50,4,1,68,300,15,32,40,3,20,6);
trace("排序前:"+arr);
//BubbleSort();//冒泡排序
//SelectionSort();//选择排序
//QuickSort();//快速排序
//ShellSort();//希尔排序
//InsertionSort();//插入排序
//MergeSort();//归并排序
HeapSort();//堆排序
trace("排序后:"+arr); } /**
* 冒泡排序
* 如设要排序的数组中有N个数据，从 数组第一个数据开始相邻两个数据两两比较，将大的数据排在小的数据前面，
* 直到第n-1和第n个比较并排序完成，这样比较完了一趟排序，第n数是数组中最大的数。
* 接着以相同的方法比较从第一个数据起两两比较直到第n-2和第n-1比较完成，这样依次比较的长度递减直到比较 完成
* 共需要n-1趟比较。
*
*/
private function BubbleSort():void{
var len:int=arr.length;
for(var i:int=len-1;i>=1;i--){ //冒泡排序每趟比较的最后一位数
for(var j:int=0;j<i;j++){//每趟都从第一个开始，每趟结束完成arr[i]为第len-i大
if(arr[j]>arr[j+1]){
swap(j,j+1);
}
}
}
} /**
* 选择排序
* 如设要排序的数组中有n个数据,从第1个数据开始先记录其索引，然后依次与其他数据比较并更新索引为最小的索引，
* 直到比较一趟后将第1个数和记录索引的数交换
*/
private function SelectionSort():void{
var len:int=arr.length;
var tempIndex:int=0;
for(var i:int=0;i<len-1;i++){
tempIndex=i;
for(var j:int=i+1;j<len;j++){
if(arr[tempIndex]>arr[j]){
tempIndex=j;
}
}
if(i!=tempIndex){
swap(i,tempIndex);
}
}
} /**
*快速排序
* 快速排序是数组中任意取一个数作为关键数据，数组其他数与关键数据比较，小的放在关键数据前面，大的放在关键数据
* 后面，经过一趟后关键数据前面的数据都比关键数据小，后面的都比关键数据大，然后再递归比较前面部份和比较后面的部份
* 数组a[0,n-1],设start为0,end为n-1,取start与end的中间数据作为关键数据key
* 然后将比key小的数放在关键数据的前面，比key大的数放在关键数据后面,得到三部分[low]、key、[large],然后再递归[low]部分名
* 和[large]部分
*
*
*/
private function QuickSort():void{
QuickSort2(arr,0,arr.length-1);
}
private function QuickSort2(arr:Vector.<int>,start:int,end:int ):void{
if(start>=end)return;
var mid:int=int(start+end)/2;
var key:int=arr[mid];
var l:int=start;
var r:int=end;
while(l<r){
while(arr[l]<key&&l<end){
l++;
}
while(arr[r]>key&&r>start){
r--;
}
if(l<r){
swap(l,r);
} }
//swap(l,r);
if(r-start>1){
QuickSort2(arr,start,r-1);
}
if(end-r>1){
QuickSort2(arr,r+1,end);
} } /**
* 希尔排序
* 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
* 所有距离为d1的倍数的记录放在同一个组中，先在各组内进行直接插入排序；
* 然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，
* 即所有记录放在同一组中进行直接插入排序为止。
*
*/
private function ShellSort():void{
var len:int=arr.length;
var d:int=int(len/2);
var i:int,j:int,temp:int;
while(d>=1){
for(i=d;i<len;i++){ temp=arr[i];
for (j = i; j >= d; j -= d) {
if(temp<arr[j - d]){
arr[j] = arr[j - d];
}else{
break;
}
}
arr[j] = temp;
}
d=int(d/2);
}
} /**
* 插入排序
* 插入排序（Insertion Sortion）的基本思想是：把n个待排序的元素看成一个有序表和一个无序表，
* 开始有序表只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，
* 把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
*/
private function InsertionSort():void{
var len:int=arr.length;
var i:int,j:int,insertVal:int;
for(i=1;i<len;i++){
insertVal=arr[i];
for(j=i-1;j>=0;j--){
if(insertVal<arr[j]){
arr[j+1]=arr[j];
}else{
break;
}
}
arr[j+1]=insertVal;
}
} /**
*归并排序
* 归并排序将已有序的子序列合并形成一个新的有序的序列，然后再将新的有序序列与另外一个有序序列合并
* 直到所有数据都合并排序完成。
*
*/
private function MergeSort():void{
MergeSort2(0,arr.length-1);
}
private function MergeSort2(l:int,r:int):void{
if(l<r){
var mid:int=int(l+r)/2;
MergeSort2(l,mid);
MergeSort2(mid+1,r);
Merge(l,mid,mid+1,r);
}
} private var tempArr:Vector.<int>=new Vector.<int>();
private function Merge(ls:int,le:int,rs:int,re:int):void{
var l:int=ls;
var r:int=rs;
tempArr.length=0;
while(l<=le&&r<=re){
if(arr[l]<arr[r]){
tempArr.push(arr[l++]); }else{
tempArr.push(arr[r++]);
}
} while(l<=le){
tempArr.push(arr[l++]);
}
while(r<=re){
tempArr.push(arr[r++]);
} for(var i:int=ls,k:int=0;i<=re&&k<tempArr.length;i++,k++){
arr[i]=tempArr[k];
} } /**
*堆排序
* 一个数组如果符合二叉树的性质，即非叶子节点均不大于（或不小于）其左右孩子（若存在）结点的关键字，则称为堆
* 如果一个序列是堆，并且非叶子节点大于（小于）其子节点则称为最大堆（最小堆）
* 堆排序是利用堆的这一性质去序列进行排序，将一个序列建堆，根节点最大（最小），然后将根节点与最后一个数交换，
* 除最后一个数之外其余数所形成的序列a[0.....n-2]就可能违反了堆的性质，所以将该序列建堆再将其根节点与a[n-2]交换，
* 循环建堆交换根节点直到序列排列完成
*
*/
private function HeapSort():void{
HeapSort1(arr.length);
} private function HeapSort1(len:int):void{
if(len>1){
BuildHeap(len);
swap(0,len-1);
HeapSort1(--len);
}
}
private function BuildHeap(len:int):void{ for(var i:int=(len-1)/2;i>=0;i--){
maxHeapify(len,i);
} } /**
* 比较非叶子节点与左右孩子节点的值，如果节点不全大于左右两孩子，则将左右孩子中较的数和父节点交换
* 交换值后可能破坏了被交换的孩子节点子堆性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。
* 有了初始堆之后就可以进行排序了。
* @param len
* @param index
*
*/
private function maxHeapify(len:int,index:int):void{
var ti:int=0,larget:int,l:int,r:int;
l=getChildLeftIndex(index);
r=getChildRightIndex(index);
larget=index;
if(l<len&&arr[index]<arr[l]){
larget=l;
}
if(r<len&&arr[larget]<arr[r]){
larget=r;
}
if(index!=larget){
swap(index,larget);
maxHeapify(len,larget);
}
}
private function getChildLeftIndex(index:int):int{
return 2*index+1;
} private function getChildRightIndex(index:int):int{
return 2*(index+1);
} /**
* 交换数组两位数的数据
* @param i
* @param j
*
*/
private function swap(i:int,j:int):void{
var temp:int=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}