php实现7种常见排序
class test{
public function main()
{
$data = $this->createData();
$this->bubbleSort($data);
$this->selectSort($data);
$this->insertSort($data);
$this->shellSort($data);
$this->mergeSort($data);
$this->heapSort($data);
$this->fastSort($data);
}
public function createData()
{
$firtime = microtime();
$data = [];
for($i = 0; $i < 1000000;){
$val = ceil(rand(1,1000000));
if(!in_array($val, $data)){
$data[] = $val;
$i++;
}
}
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
return $data;
}
//归并排序开始
public function mergeSort($data)
{
$firtime = microtime();
$res = $this->mergeSortMain($data, 0, count($data)-1);
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
}
public function mergeSortMain(&$data, $from, $to){
if($from == $to){
return [$data[$to]];
}
$middle = floor(($to + $from)/2);
$left = $this->mergeSortMain($data, $from, $middle);
$right = $this->mergeSortMain($data, $middle+1, $to);
$res = $this->sortTwoSortArr($left, $right);
return $res;
}
public function sortTwoSortArr($arrA, $arrB){
$res = [];
$index = 0;
$indexA = 0;
$indexB = 0;
while (count($arrA)&&count($arrB)) {
if ($arrA[$indexA] < $arrB[$indexB]) {
$res[$index++] = $arrA[$indexA];
unset($arrA[$indexA++]);
} else {
$res[$index++] = $arrB[$indexB];
unset($arrB[$indexB++]);
}
}
if (count($arrA)) {
while (count($arrA)) {
$res[$index++] = $arrA[$indexA];
unset($arrA[$indexA++]);
}
} elseif (count($arrB)){
while (count($arrB)) {
$res[$index++] = $arrB[$indexB];
unset($arrB[$indexB++]);
}
}
return $res;
}
//归并排序结束
//快速排序开始
public function fastSort($data)
{
$firtime = microtime();
$this->fastSortMain(0, count($data) - 1, $data);
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
}
public function fastSortMain($start, $end, &$data){
if ($start >= $end) {
return;
}
$middle = $this->fastSortSwap($start, $end, $data);
$this->fastSortMain($start, $middle-1, $data);
$this->fastSortMain($middle+1, $end, $data);
}
//这个方法的作用是把 $data从start到end之间的部分 分成大于某值或者小于某值两部分，并且返回某值的位置
public function fastSortSwap($start, $end, &$data){
$flag = $data[$end];
$resust_key = $start;
for ($i=$start; $i < $end; $i++) {
if ($data[$i] > $flag) {
continue;
} else {
$temp = $data[$i];
$data[$i] = $data[$resust_key];
$data[$resust_key++] = $temp;
}
}
$data[$end] = $data[$resust_key];
$data[$resust_key] = $flag;
return $resust_key;
}
//快速排序结束
//选择排序开始
public function selectSort($data)
{
$firtime = microtime();
for ($i=0; $i <count($data) ; $i++) {
$minval = $data[$i];
$minkey = $i;
for ($j=$i; $j < count($data); $j++) {
if($data[$j]<$minval){
$minval = $data[$j];
$minkey = $j;
}
}
$temp = $data[$i];
$data[$i] = $minval;
$data[$minkey] = $temp;
}
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
}
//选择排序结束
//希尔排序开始
public function shellSort($data)
{
$firtime = microtime();
$jump = floor(count($data)/2);
while($jump >= 1){
for ($i = 0; $i < $jump; $i++) {
for ($j = $i + $jump; $j < count($data);) {
$temp = $data[$j];
$k = $j - $jump;
while ($k >= 0&&$data[$k] > $temp) {
$data[$k + $jump] = $data[$k];
$k = $k - $jump;
}
$data[$k + $jump] = $temp;
$j += $jump;
}
}
$jump = floor($jump/2);
}
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
}
//希尔排序结束
//冒泡排序开始
public function bubbleSort($data)
{
$firtime = microtime();
for ($i = count($data)-1; $i > 0; $i--) {
$flag = true;
for ($j=0; $j < $i; $j++) {
if($data[$j] > $data[$j+1]){
$temp = $data[$j];
$data[$j] = $data[$j+1];
$data[$j+1] = $temp;
$flag = false;
}
}
if($flag){
break;
}
}
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
}
//冒泡排序结束
//插入排序开始
public function insertSort($data){
$firtime = microtime();
for ($i = 1; $i < count($data); $i++) {
$temp = $data[$i];
$j = $i - 1;
while ($j > 0&&$data[$j] > $temp) {
$data[$j+1] = $data[$j];
$j--;
}
$data[$j+1] = $temp;
}
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
}
//插入排序结束
//堆排序开始
public function heapSort($data){
$firtime = microtime();
$this->initHeap($data);
$n = count($data);
for ($i = $n - 1; $i > 0; $i--) {
$this->swap($data, 0, $i);
$this->down($data, 0, $i - 1);
}
$sectime = microtime();
$this->getTimeLimit($firtime, $sectime);
}
public function initHeap(&$data){
$n = count($data);
for ($i = $n/2-1; $i >= 0; $i--) {
$this->down($data, $i, $n-1);
}
}
public function swap(&$data, $i, $j){
$n = count($data);
if ($i < 0||$j < 0||$i > $n||$j > $n) {
return;
} else {
$temp = $data[$i];
$data[$i] = $data[$j];
$data[$j] = $temp;
}
}
public function down(&$data, $head, $tail){
$left_child = $head * 2 + 1;
$right_child = $left_child + 1;
$next_head = $left_child;
$head_val = $data[$head];
while ($left_child <= $tail) {
if ($right_child <= $tail&&$data[$right_child] > $data[$left_child]) {
$next_head = $right_child;
}
if ($data[$next_head] > $head_val) {//无论何时都只和最上面的那个值比较
$data[$head] = $data[$next_head];
} else {
break;
}
$head = $next_head;
$left_child = $head * 2 + 1;
$right_child = $left_child + 1;
$next_head = $left_child;
}
$data[$head] = $head_val;
}
//堆排序结束
//获取花费时间开始
public function getTimeLimit($a, $b){
list($seconds1, $msecond1) = explode(' ', $a);
list($seconds2, $msecond2) = explode(' ', $b);
var_dump(($seconds2 - $seconds1)+($msecond2 - $msecond1));
}
//获取话费时间结束
}最后发现7种排序的效率从低到高依次为
冒泡排序
选择排序
插入排序
希尔排序
归并排序
堆排序
快速排序
将数据量增加到1000w，也没有看到堆排序的优势，还是快速排序效率最高，留坑待填//todo