本文主要是介绍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))
- }
- }
- }
- }
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();//17786return 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;
- }
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排序算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!