[AS3]as3排序方法和算法(3)

四、AS中排列数组
1.申请一个长度为n的数组A：
var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {

A[i] = i;
}
trace(A);



2.将长度为n的数组打乱次序：
for (i=0; i < n; i++) {
var ran = int(Math.random()*n);
var temp = A[i];
A[i] = A[ran];
A[ran] = temp;
}
trace(A)



3.将数组中的所有元素倒排序：
A.reverse();
trace(A)


五、AS实现排序算法：

在执行各各排序算法之前，已经默认存在一个乱序的数组 A[400]，默认代码：

var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {

A[i] = i;
}
for (i=0; i < n; i++) {

var ran = int(Math.random()*n);
var temp = A[i];
A[i] = A[ran];
A[ran] = temp;
}



1.直接插入排序

for (i = 0; i < n; i++) {
var temp = A[i];
for (j = i; j > 0 && temp < A[j - 1]; j--) {
A[j] = A[j - 1];
A[j - 1] = temp;
}
}

2.直接选择排序


for (i = 0; i < n - 1; i++) {
var s:Number = i;
for (j = s + 1; j < n; j++) {
if (A[j] < A[s]) {
s = j;
}
}
var temp = A[i];
A[i] = A[s];
A[s] = temp;
}

3.冒泡排序

for (i = 0; i < n; i++) {
for (j = i; j < n; j++) {
if (A[i] > A[j]) {
var temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}

4.希尔排序

var increment = 6;
while (increment > 1) {
increment = int(increment / 3 + 1);
Shellpass(increment);
}
function Shellpass(c) {
for (i = c; i < n; i++) {
if (A[i] < A[i - c]) {
var temp = A[i];
j = i - c;
do {
A[j + c] = A[j];
j = j - c;
} while (j > 0 && temp < A[j]);
A[j + c] = temp;
}
}
}

5.快速排序


function QuickSort(A, low, hig) {
var i = low, j = hig;
var mid = A[int((low + hig) / 2)];
do {
while (A[i] < mid) {
i++;
}
while (A[j] > mid) {
j--;
}
if (i <= j) {
var temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
} while (i <= j);
if (low < j) {
arguments.callee(A,low,j);
}
if (i < hig) {
arguments.callee(A,i,hig);
}
}
QuickSort(A,0,n - 1);

6.二路归并

var B:Array = new Array(A.length);
for (k = 1; k < n; k *= 2) {
MergePass(k);
}
function MergePass(len) {
for (i = 0; i + 2 * len < n; i = i + 2 * len) {
MergeA(i,i + len - 1,i + 2 * len - 1);
}
if (i + len < n) {
MergeA(i,i + len - 1,n - 1);
}
}
function MergeA(low, m, hig) {
var i = low, j = m + 1, z = 0;
while (i <= m && j <= hig) {
B[z++] = (A[i] <= A[j]) ? A[i++] : A[j++];
}
while (i <= m) {
B[z++] = A[i++];
}
while (j <= hig) {
B[z++] = A[j++];
}
for (z = 0, i = low; i <= hig; z++, i++) {
A[i] = B[z];
}
}