排序算法复习 之 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;
} 相关推荐
randy0 2020-11-17
lixiaotao 2020-10-07
美丽的泡沫 2020-09-08
nongfusanquan0 2020-08-18
hang0 2020-08-16
earthhouge 2020-08-15
算法改变人生 2020-07-28
troysps 2020-07-19
Broadview 2020-07-19
chenfei0 2020-07-18
风吹夏天 2020-07-07
yangjingdong00 2020-07-05
数据与算法之美 2020-07-05
shawsun 2020-07-04
数据与算法之美 2020-07-04
要知道时间复杂度只是描述一个增长趋势，复杂度为O的排序算法执行时间不一定比复杂度为O长，因为在计算O时省略了系数、常数、低阶。实际上，在对小规模数据进行排序时，n2的值实际比 knlogn+c还要小。
Evankaka 2020-07-04
田有朋 2020-06-28