`

排序算法复习 之 AS3

    博客分类:
  • AS3
 
阅读更多

 

以前在论坛的贴子,保存之。

 

原链接: http://uh.9ria.com/link.php?url=http://bbs.9ria.com%2Fviewthread.php%3Ftid%3D32369

 

排序算法复习,要求用ActionScript 3 实现不允许用 Array的sort sorton 方法

 

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.冒泡排序

http://zh.wikipedia.org/w/index.php?title=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&variant=zh-hans

 

/*        
        冒泡排序是这样实现的:
        
           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.插入排序

http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

 

/*        
        一般来说,插入排序都采用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.快速排序

 

http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

 

/*        
快速排序使用分治法(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.选择排序

 

http://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F

 

 

/*
    选择排序是这样实现的:
        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;
        }
 

 

分享到:
评论

相关推荐

    数据结构重要算法(含排序、查找)期末复习用

    **排序算法**是用于重新排列一组数据,使得数据按照特定顺序排列。排序的效率直接影响到程序的性能。常见的排序算法包括: 1. **快速排序**:由一次分划过程构成,通过选择一个基准元素并将数组分为小于和大于基准...

    VB复习程序

    欧几里得算法(辗转相除法)通常用于计算两个数的最大公约数。在VB中,`Function zdgy(X as integer, Y as integer) as integer`和`Function Gys(X as integer, Y as integer) as integer`分别展示了两种实现方式,...

    大数据高级工程师复习题

    "大数据高级工程师复习题" 大数据高级工程师复习题是对大数据相关知识的总结和测试,涵盖了Python编程语言、数据分析、数据可视化、数据处理等方面的知识点。 1. Python中的关键字检查元素是否为序列的成员是in。 ...

    大学vb复习提纲包括填空题判断题选择题和编程题

    5. 对数组进行升序排序。 6. 计算1到99的奇数之和。 7. 交换数组前10个元素与后10个元素的位置。 8. 计算特定模式的数列和。 9. 用迭代法计算e的近似值。 10. 判断输入的整数是奇数还是偶数。 熟悉并掌握以上知识点...

    浅谈javascript实现八大排序

    排序算法,分为内部排序和外部排序。内部排序要使用内存,这里只探讨内部排序。 1,插入排序:直接插入排序和希尔排序 2,选择排序:简单选择排序和堆排序 3,交换排序:冒泡排序和快速排序 4,归并排序 5,基数排序...

    计算机二级ACCESS复习资料.pdf

    5. **冒泡排序**:冒泡排序在最坏情况下需要进行n(n-1)/2次比较,适用于小规模数据排序。 6. **二叉树的性质**:对于二叉树,叶子节点的数量(记为L)和度为1的节点数量(记为D)之间的关系是总结点数N=L+D-1。所以...

    VB知识点复习总结PPT课件.pptx

    例如,在排序算法中,我们可以使用选择结构实现三数之中的最大值比较。 最后,循环结构在VB中主要有计数型循环,如`For...Next`循环,用于当循环次数已知时。数组的使用也经常涉及到循环,通过下标访问数组元素,...

    VB程序设计强化复习主题讲座2PPT教案学习.pptx

    VB程序设计强化复习主题讲座主要涵盖了数组的定义与操作,包括静态数组和动态数组的创建,以及基于数组的各种算法实现。以下是对这些知识点的详细解释: 1. **数组的定义**: 数组是一种可以存储多个相同类型数据...

    云计算导论期末复习(速成不挂科版)

    ### 云计算导论期末复习知识点总结 #### 一、大数据特征 - **4V+1C**:指大数据所具有的显著特征。 - **Volume(数据量大)**:数据规模庞大,传统数据处理方法难以应对。 - **Variety(多样)**:数据来源多样,...

    二级VB题型:一维数组元素排列

    一维数组元素排列涉及到数组的基本概念、声明、初始化、赋值以及排序算法。以下是对这些知识点的详细解释: 1. **数组的概念**: 数组是一种数据结构,它能存储相同类型的数据集合。一维数组就像一个线性的列表,...

    信息化管理与运作 复习题(1).doc

    这份国开、国家开放大学的《信息化管理与运作》考试复习资料涵盖了多项选择题、多选题和判断题,旨在帮助学生掌握信息化的核心概念和原理。 1. 信息(技术)革命的特征包括科学化、群体化、智能化和高新性。这意味...

    算法会考模拟判断题.pdf

    【算法会考模拟判断题.pdf】的文件内容涵盖了VB(Visual Basic)编程语言的基础知识,主要涉及程序设计、事件处理、对象属性、控件使用、数据类型、运算符、循环结构、递归、排序以及算法等多个方面。以下是相关知识...

    高一化学期中复习练习[精选].doc

    6. **元素性质的排序**:A选项错误,非金属性应该为F&gt;Cl&gt;S&gt;As;B选项正确,金属活动性从强到弱为Rb&gt;K&gt;Mg&gt;Al;C选项正确,稳定性HF&gt;H2S&gt;PH3&gt;AsH3;D选项正确,原子半径从大到小为Na&gt;P&gt;O&gt;F。 7. **元素周期律**:A和C...

    程序员面试题目,程序员即将面试用

    面试时,可能会要求现场实现一种排序算法,如快速排序,它具有较高的平均时间效率。 7. **三层架构** 三层架构包括表现层、业务逻辑层和数据访问层。这种架构有助于分离关注点,提高代码可维护性和可扩展性。但...

    四川大学 数据结构

    以上知识点仅为基础,数据结构还包括链表、栈、队列、树、图、哈希表、排序算法(如冒泡、插入、快速、归并排序等)、查找算法(如二分查找、哈希查找)等复杂主题。学习数据结构不仅要求理解各种数据结构的特性,...

    南开100题分类txt版 计算机三级上机考试

    2. **算法与数据结构**:排序算法(冒泡、选择、插入、快速、归并等)、查找算法(顺序、二分、哈希)以及栈、队列、链表、树等数据结构的运用。 3. **文件操作**:文件的打开、读写、关闭,以及文件流的处理。 4....

    计算机二级考试题库:VB填空题.pdf

    4. 数组操作和排序:涉及到数组的初始化、遍历和简单的排序算法(如冒泡排序)的实现。文档中通过随机生成数组元素并进行排序,展示了数组在VB中的应用。 5. 函数和子程序的使用:文档中定义了Public Sub和Public ...

    2_Python上机题库及答案.zip

    12. **算法与数据结构**:排序算法(冒泡排序、选择排序、插入排序、快速排序、归并排序)、搜索算法(线性搜索、二分查找)、图和树的数据结构。 13. **Python标准库应用**:网络请求(urllib模块)、JSON数据处理...

Global site tag (gtag.js) - Google Analytics