`

排序算法 之 AS3

    博客分类:
  • AS3
阅读更多

排序算法 之 AS3

 

package {
    import flash.display.Sprite;
    import flash.utils.getTimer;

    public class ActionscriptSortTest extends Sprite {
        //要求将radomArr安从小到大排序
        public function ActionscriptSortTest() {
            initRadomArr();
            
            getBubbleSortArr();
        }
/*        
        冒泡排序是这样实现的:
           1. 首先将所有待排序的数字放入工作列表中。
           2. 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。
           3. 重复2号步骤(倒数的数字加1。例如:第一次到倒数第二个数字,第二次到倒数第三个数字,依此类推...),直至再也不能交换。
        冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法
*/        
        public function getBubbleSortArr():Array {
            var result:Array = radomArr.concat();
            
            fucStart();
            var i:int = 1;
            var j:int = 0;
            var n:int = result.length;
            for(i=1;i<n;i++) {
                for(j=0;j<n-i;j++) {
                    if(result[j] > result[j+1]) {
                        var temp:Number = result[j];
                        result[j] = result[j+1];
                        result[j+1] = temp;
                    }
                }
            }
            
            fucEnd();//17786
            return result;
        }

        private var t:int;
        private function fucStart():void {
            t = getTimer();
        }
        
        private function fucEnd():void {
            trace(getTimer() - t);
        }
        
        private var radomArr:Array;
        private function initRadomArr():void {
            radomArr = [];
            for(var i:int=0;i<10000;i++) {
                radomArr.push(int(Math.random()*0xFFF))
            }
        }
    }
}

 

1.冒泡排序

 

/*        
        冒泡排序是这样实现的:
        
           1. 首先将所有待排序的数字放入工作列表中。
           2. 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。
           3. 重复2号步骤(倒数的数字加1。例如:第一次到倒数第二个数字,第二次到倒数第三个数字,依此类推...),直至再也不能交换。
        
        冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法
        
*/        
        public function getBubbleSortArr():Array {
            var result:Array = radomArr.concat();
            
            fucStart();
            var i:int = 1;
            var j:int = 0;
            var n:int = result.length;
            for(i=1;i<n;i++) {
                for(j=0;j<n-i;j++) {
                    if(result[j] > result[j+1]) {
                        var temp:Number = result[j];
                        result[j] = result[j+1];
                        result[j+1] = temp;
                    }
                }
            }
            
            fucEnd();//17786
            return result;
        }

 

2.插入排序

 

/*        
        一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

       1. 从第一个元素开始,该元素可以认为已经被排序
       2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
       3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
       4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
       5. 将新元素插入到该位置中
       6. 重复步骤2
*/

        public function getInsertionSortArr():Array {
            var result:Array = radomArr.concat();
            fucStart();
            
            var i:int = 1;
            var n:int = result.length;
            
            for(i=1;i<n;i++) {
                var temp:Number = result[i];
                var j:int = i - 1;
                
                while((j>=0) && (result[j] > temp)) {
                                 result[j+1] = result[j];        
                                 j--;
                         }
                         
                         result[j+1] = temp;
            }
            
            fucEnd();
            return result;
        }

 

 

       public function getInsertionSortArr():Array {
            var result:Array = radomArr.concat();
            fucStart();
            
            var i:int = 1;
            var j:int = 0;
            var n:int = result.length;
            
            for(i=1;i<n;i++) {
                for(j=0;j<i;j++) {
                    if(result[j] > result[i]) {
                        var temp:Number = result[j];
                        result[j] = result[i];
                        result[i] = temp;
                    }
                }
            }
            
            fucEnd();
            return result;
        }
 

 

        public function getInsertionSortArr():Array {
            var result:Array = radomArr.concat();
            fucStart();
            
            var i:int = 1;
            var j:int = 0;
            var n:int = result.length;
            
            for(i=1;i<n;i++) {
                var temp:Number = result[i];
                for(j=i;j>0 && temp<result[j-1];j--) {
                    result[j]=result[j-1];
                }
                result[j]=temp;
            }
            
            fucEnd();
            return result;
        }
 

 

3.快速排序

/*        
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤为:

   1. 从数列中挑出一个元素,称为 "基准"(pivot),
   2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
   3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个演算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
*/
        
        public function getQuickSortArr():Array {
            var result:Array = radomArr.concat();
            fucStart();
            
            var n:int = result.length;
            quickSort(result,0,n-1);
            
            fucEnd();
            return result;
        }
        
        private function quickSort(arr:Array,low:int,high:int):void {
            var i:int;
            var j:int;
            var x:int;
            
            if (low < high) { //这个条件用来结束递归
                
                i = low;
                j = high;
                x = arr[i];
            
                while (i < j) {
                    while (i < j && arr[j] > x) {
                       j--; //从右向左找第一个小于x的数
                    }
                    if (i < j) {
                       arr[i] = arr[j];
                       i++;
                    }
                
                    while (i < j && arr[i] < x) {
                       i++; //从左向右找第一个大于x的数
                    }
                
                    if (i < j) {
                       arr[j] = arr[i];
                       j--;
                    }
                 }

                arr[i] = x;
                quickSort(arr, low, i - 1);
                quickSort(arr, i + 1, high);
            }
        }
 

 

 

4.选择排序

/*
    选择排序是这样实现的:
        1.首先在未排序序列中找到最小元素,存放到排序序列的起始位置
        2.然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。
        3.以此类推,直到所有元素均排序完毕。
*/
        public function getSelectionSort():Array {
            var result:Array = radomArr.concat();
            
            fucStart();
            var i:int = 0;
            var j:int = 0;
            var n:int = result.length;
            
            for (i = 0; i < n - 1; i++) {
                var min:int = i;
                for (j = i+1; j < n; j++) {
                    if (result[j] < result[min]) {
                        min = j;
                    }
                }
                /* swap data[i] and data[min] */
                var temp:Number = result[i];
                result[i] = result[min];
                result[min] = temp;
            }

            fucEnd();//6214
            return result;
        }

 

 

 5.鸡尾酒排序

 

/*        
        鸡尾酒排序,也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 
        是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
*/        
        public function getCocktailSortArr():Array {
            var result:Array = radomArr.concat();
            
            fucStart();
            
            var i:int = 0;
            var n:int = result.length;
            var top:int = n - 1;
            var bottom:int = 0;
            var swapped:Boolean = true; 
            
            while(swapped) { // if no elements have been swapped, then the list is sorted
                swapped = false; 
                var temp:Number;
                for(i = bottom; i < top;i++) {
                    if(result[i] > result[i + 1]) {  // test whether the two elements are in the correct order
                        temp = result[i];// let the two elements change places
                        result[i] = result[i + 1];
                        result[i + 1] = temp;
                        swapped = true;
                    }
                }
                // decreases top the because the element with the largest value in the unsorted
                // part of the list is now on the position top 
                top = top - 1; 
                for(i = top; i > bottom;i--) {
                    if(result[i] < result[i - 1]) {
                        temp = result[i];
                        result[i] = result[i - 1];
                        result[i - 1] = temp;
                        swapped = true;
                    }
                }
                // increases bottom because the element with the smallest value in the unsorted 
                // part of the list is now on the position bottom 
                bottom = bottom + 1;  
            }
            
            fucEnd();//6214
            return result;
        }
 

 

分享到:
评论

相关推荐

    as3算法大全

    AS3中常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。其中,快速排序和归并排序在大数据量时表现优秀,但快速排序更易于实现。 三、搜索算法 搜索算法包括线性搜索、二分搜索、...

    AS3中的数据结构排序算法

    在ActionScript 3 (AS3)中,数据结构和排序算法是编程基础的重要组成部分,尤其在处理大量数据时,高效地组织和排序数据是至关重要的。这篇博客文章可能详细介绍了如何在AS3环境中实现各种排序算法,以优化性能并...

    flash选择排序算法.as

    失传己久的flash选择排序算法,效果超赞,赶快下载!失传己久的flash选择排序算法,效果超赞,赶快下载!

    排序算法.pdf

    陕西科技大学学校的排序算法实验,最近小咲写的: 一、实验目的 1. 熟练运用冒泡排序、选择排序、插入排序、希尔排序、快速排序、合并排序、堆排序等七种常见的内排序算法 2. 使用不同的数据结合计算各种算法的运行...

    AS3.0算法大全

    8.【AS功能代码教程10】数据结构排序算法,说明了在处理大量数据时如何通过排序算法优化性能,排序算法是编程中常见的基础算法之一。 9.【AS功能代码教程01】通用延迟代码及FPS概念,解释了如何在AS3.0中实现控制...

    VBA排序的十种算法.docx

    快速排序是一种高效的排序算法,采用分治法策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。 ### 5. 合并排序(Merge Sort) 合并排序是一种稳定的排序方法,采用分治法策略,将数组分成两...

    "As for Multiplayer Games and Virtual Worlds"中排序算法中文翻译

    《关于多人游戏和虚拟世界》一书中,排序算法部分主要探讨了在2.5D视角下的对象排序问题,这是在构建多人游戏或虚拟环境时一个关键的技术挑战。尤其是在等角视角下,正确地安排物体的前后关系对于提供逼真的视觉体验...

    Flash As3 A星寻路算法

    **Flash AS3 A* 寻路算法详解** 在游戏开发和路径规划中,A*(发音为"A-star")寻路算法是一种广泛应用的路径搜索算法,它基于Dijkstra算法但更高效,因为它考虑了启发式信息来指导搜索方向。在Flash AS3环境中,A*...

    vbs算法如何实现冒泡排序法

    冒泡排序法是一种基础但实用的排序算法,它通过不断地比较相邻元素并交换位置来将一个无序的序列逐步转化为有序。在这个过程中,较大的元素逐渐“冒”到序列的顶端,就像水底的气泡逐渐上升到水面一样,因此得名冒泡...

    七种常见的VB排序算法示例程序.rar

    起泡排序是最简单的排序算法之一,通过不断交换相邻的逆序元素来逐渐将最大或最小的元素“冒”到数组的一端。它的工作原理是进行多轮比较,每轮结束后最大的元素都会被推到正确的位置。虽然效率较低,但理解起来非常...

    常用排序算法分析与实现(Java版)

    归并排序也是一种采用分治法的排序算法。它将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 **实现步骤**: 1. **分解**...

    php-使用php开发的排序算法之ArrayKeysSort-排序算法实现.zip

    `ArrayKeysSort`是一种实用的自定义排序算法,它在保留键值对应关系的同时,允许我们根据键对数组进行排序。理解和掌握这种算法可以帮助我们更好地解决实际问题,特别是在处理关联数组时。在使用时,要根据项目需求...

    c语言经典排序算法(8种-含源代码)

    ### C语言经典排序算法 在计算机科学领域,排序算法是数据结构与算法中非常重要的一部分,它们不仅被广泛应用于各种实际场景中,而且对于理解和掌握算法原理也极为关键。本篇文章将详细介绍八种经典的排序算法,并...

    Astar算法as实现

    在AS3(ActionScript 3)中实现Astar算法,可以用于游戏开发中的路径规划、地图导航等问题。 首先,Astar算法的核心思想是维护一个优先级队列(通常是开放列表),用于存储待搜索的节点。每个节点包含当前节点的...

    AS3.0算法大全,非常有用。

    14. **数据结构排序算法**:这部分内容介绍了各种排序算法的实现,包括但不限于冒泡排序、快速排序等,并讨论了它们在AS3.0中的应用。 15. **AS文本计算器**:通过解析文本输入并执行计算操作,实现了一个简单的...

    VB冒泡法排序源码

    冒泡排序是一种基础且经典的排序算法,它通过不断交换相邻两个元素的位置,使得较大的(或较小的)元素逐渐“浮”到序列的尾部,从而达到排序的目的。在VB(Visual Basic)编程语言中实现冒泡排序,可以很好地帮助...

    as3射击小游戏

    AS3提供`trace`函数输出调试信息,同时要关注性能优化,如减少不必要的对象创建,缓存常量,优化算法等。 以上就是AS3射击小游戏的开发要点,对于新手来说,理解并实践这些概念是提升编程技能的有效途径。通过不断...

    VB 插入法排序

    插入法排序(Insertion Sort)是一种简单直观的排序算法,常用于教学和小规模数据的排序。在VB(Visual Basic)编程环境中,我们可以利用其结构和语法实现插入法排序。以下将详细介绍插入法排序的基本原理、步骤以及...

    as3corelib多版本

    标题提到的“as3corelib多版本”可能指的是AS3CoreLib的不同发布版本,包括.as3corelib-.93、.as3corelib-.92、.as3corelib-.92.1以及.corelib-.90。每个版本都可能包含不同的特性、性能提升或错误修复。例如,版本...

    A星寻路(AS3)

    4. **优先队列**:AS3中常用PriorityQueue数据结构来存储开放列表,按照F得分进行排序,确保每次都能取出F值最小的节点。 5. **邻居节点**:在网格环境中,每个节点有若干个相邻的邻居节点。算法会检查这些邻居,...

Global site tag (gtag.js) - Google Analytics