我正在做一個項目,我手動創建排序算法。自定義排序算法的速度問題
經過多次測試,我發現我的堆排序比快速排序快(我認爲它應該是另一種方式),我的選擇排序也比插入排序更快。有人知道這裏有什麼問題嗎?我正在測試使用整數從-100到100,隨機生成,在數組中的5000個值(我修改了這個數字,幾次,仍然是同樣的問題)。 我的快速排序不在位。 我認爲也許flash的遞歸函數很慢?我的heapsort使用循環,不像quicksort。這只是一個假設。
這裏是我的代碼,如果他們幫助。我啓動一個計時器,運行該類的exec()函數,停止計時器並計算經過的時間。代碼來自維基百科。 問題堆排序VS快速排序:
public class Quick {
public static function exec(seq:Vector.<int>):Vector.<int> {
if (seq.length<=1) {
return seq;
}
var smallPart:Vector.<int>=new Vector.<int>
var bigPart:Vector.<int>=new Vector.<int>
var n:int=seq.length;
var pivotPosition:int=Math.floor(Math.random()*n);
var pivot:int=seq.splice(pivotPosition,1)[0];
for (var i:int=0; i<n-1; i++) {
if (seq[i]<=pivot) {
smallPart.push(seq[i]);
} else {
bigPart.push(seq[i]);
}
}
seq=exec(smallPart).concat(exec(bigPart),Vector.<int>([pivot]));
return seq;
}
}
public class Heap{
public static function exec(seq:Vector.<int>) {
var n:int=seq.length;
heapify(seq);
var end:int=n-1;
while (end > 0) {
var temp:int=seq[end];
seq[end]=seq[0];
seq[0]=temp;
siftDown(seq, 0, end-1);
end--;
}
return seq
}
public static function heapify(seq:Vector.<int>) {
var n:int=seq.length
var start:int=n/2-1
while (start >= 0) {
siftDown(seq, start, n-1);
start--;
}
}
public static function siftDown(seq:Vector.<int>, start:int, end:int) {
var root:int=start;
while (root * 2 + 1 <= end) {
var child:int=root*2+1;
var swap:int=root;
if (seq[swap]<seq[child]) {
swap=child;
}
if (child+1<=end&&seq[swap]<seq[child+1]) {
swap=child+1;
}
if (swap!=root) {
var temp:int=seq[root];
seq[root]=seq[swap];
seq[swap]=temp;
root=swap;
} else {
break;
}
}
}
}
問題插入排序VS選擇排序:
public class Insertion{
public static function exec(seq:Vector.<int>) {
var n:int=seq.length;
for (var i:int=1; i<n; i++) {
var holder:int=seq[i];
var j:int=i-1;
while (seq[j]>holder) {
seq[j+1]=seq[j];
j-=1;
if (j<0) {
break
}
}
seq[j+1]=holder;
}
return seq
}
}
public class Selection{
public static function exec(seq:Vector.<int>):void{
var currentMinimum:int;
var n:int=seq.length;
for (var i:int = 0; i < n-1; i++) {
currentMinimum=i;
for (var j:int = i+1; j < n; j++) {
if (seq[j]<seq[currentMinimum]) {
currentMinimum=j;
}
}
if (currentMinimum!=i) {
var temp:int=seq[i];
seq[i]=seq[currentMinimum];
seq[currentMinimum]=temp;
}
}
}
}
不要使用定時器,使用日期。我記得在某個地方聽到計時器可能會在錯誤的時間發生。 –