进阶排序
一、说明二、算法归并排序快速排序
一、说明
进阶排序主要会展示归并排序算法和快速排序算法。归并排序算法由于不是原地排序算法所以它的空间复杂度不是O(1)，它的时间复杂度是O(nlogn)。整个算法如果采用递归方式去写的话是很简单的，具体可参看代码部分。 快速排序的思路和归并排序是一样的，就是把数组分成两部分分别使其有序最后在组合起来就整体有序了。不同的是快速排序并不是平均拆分数组，而是选择一个中心点，排序时让中心点左边的数都比中心点小，中心点右边数都比中心点大，这个排序算法的时间复杂度是O(n), 但是由于数组拆分是基于中心点的，所以它的拆分的时间复杂度和它选择的这个点有很大关系，具体情况可以看代码分析。
二、算法
归并排序
public function MergeSort(s
:Array
):void
{
Merge(s
,0, s
.length
- 1);
}
private function Merge(s
:Array
, m
:int
, n
:int
):Array
{
var temp
:Array
= [];
if(m
== n
)
{
temp
[0] = s
[m
];
return temp
;
}
var k
:int
= Math
.floor((m
+ n
) / 2);
var t1
:Array
= Merge(s
, m
, k
);
var t2
:Array
= Merge(s
, k
+ 1, n
);
var q
:int
= 0, p
:int
= 0;
for(var i
:int
= 0; p
<= k
- m
&& q
<= n
- k
- 1; i
++)
{
if(t1
[p
] < t2
[q
])
{
temp
[i
] = t1
[p
];
p
++;
}else
{
temp
[i
] = t2
[q
];
q
++;
}
}
while(p
<= k
-m
)
{
temp
[temp
.length
] = t1
[p
];
p
++;
}
while(q
<= n
- k
- 1)
{
temp
[temp
.length
] = t2
[q
];
q
++;
}
return temp
;
}
快速排序
public function QuickSort(s
:Array
):void
{
Quick(s
, 0, s
.length
- 1);
}
private function Quick(s
:Array
, m
:int
, n
:int
):void
{
if(m
>= n
)
{
return;
}
var j
:int
= m
;
var value
:int
;
for(var i
:int
= m
; i
< n
; i
++)
{
if(s
[i
] < s
[n
])
{
value
= s
[j
];
s
[j
] = s
[i
];
s
[i
] = value
;
j
++;
}else
{
}
}
value
= s
[j
];
s
[j
] = s
[n
];
s
[n
] = value
;
trace(s
);
Quick(s
, m
, j
- 1);
Quick(s
, j
+ 1, n
);
}
