1. 插入排序法
<?php
/**
* 插入排序
* 思路：从第二个数起，把当前数插入到前面已排好序的序列中
* 算法复杂度：
* 空间复杂度：原址操作
* 时间复杂度：n^2
* @param array $arr
* @return array
*/
function InsertSort(Array $arr)
{
if(empty($arr)) {
return [];
}
$len =count($arr);
for($i = 1; $i < $len; $i++) {
$j = $i - 1;
$tmp = $arr[$i];
while ($tmp < $arr[$j] && $j > -1) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $tmp;
}
return $arr;
}
//测试
$arr = [8,32,12,35,66,77,2,4];
print_r(InsertSort($arr));
/**
* output:
* Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
*/
2. 归并排序法
<?php
/**
* 归并排序法
* 思路：分治法，核心算法在合， 即总的数组的排序可由两个已经排好序的子数组的合并得到。
* 复杂度：
* 空间复杂度：合并时需要额外两个子数组，O(n)
* 时间复杂度：O(nlogn) 稳定排序法
* @param $arr 数组
* @param $start 初始下标
* @param $end 结束下标
*/
function MergeSort(&$arr, $start, $end)
{
if($start < $end) {
$mid = (int)(($start + $end) / 2);
MergeSort($arr, $start, $mid);
MergeSort($arr, $mid + 1, $end);
Merge($arr, $start, $mid, $end);
}
}
/**
* 合并两个子数组
* @param $arr 数组
* @param $start 初始下标
* @param $mid 两个子数组的分割点
* @param $end 结束下标
*/
function Merge(&$arr, $start, $mid, $end)
{
$left = $right = [];
for($i = $start; $i <= $mid; $i++) {
$left[] = $arr[$i];
}
for($i = $mid+1; $i <= $end; $i++) {
$right[] = $arr[$i];
}
$lenLeft = $mid - $start + 1;
$lenRight = $end - $mid;
$l = $r = 0;
$j = $start;
while ($l < $lenLeft && $r < $lenRight) {
$arr[$j++] = $left[$l] < $right[$r] ? $left[$l++] : $right[$r++];
}
while ($l < $lenLeft) {
$arr[$j++] = $left[$l++];
}
while ($r < $lenRight) {
$arr[$j++] = $right[$r++];
}
}
//测试
$arr = [8,32,12,35,66,77,2,4];
MergeSort($arr, 0, count($arr) - 1);
print_r($arr);
/**
* output:
* Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
*/
3. 快速排序
/**
* 快速排序法
* 思路：分治法，核心算法在分。总的数组的排序可以对子数组的排序得到，子数组的排序又可以由子子数组的排序得到...
* 复杂度：
* 空间复杂度：原址操作
* 时间复杂度：平均 O(nlogn)，最差 n^2， 不稳定的排序法
* @param $arr 数组
* @param $start 初始下标
* @param $end 结束下标
*/
function QuickSort(&$arr, $start, $end)
{
if($start < $end) {
$mid = Partition($arr, $start, $end);
QuickSort($arr, $start, $mid - 1);
QuickSort($arr, $mid + 1, $end);
}
}
/**
* 将数组分为两部分，小于基准数值的在左边， 大于基准数值的在右边，然后返回基准数值的位置
* @param $arr
* @param $start
* @param $end
*/
function Partition(&$arr, $start, $end)
{
$measure = $arr[$end]; //基准数值
$p = $start - 1; //p用于表示小于基准数值的数的下标，比如有一个比基准数值小，那么该数下标为0，两个则是1，以此类推...
for($i = $start; $i <= $end; $i++) {
if($arr[$i] < $measure) {
$tmp = $arr[$i];
$arr[$i] = $arr[$p + 1];
$arr[$p + 1] = $tmp;
$p ++;
}
}
$arr[$end] = $arr[$p + 1];
$arr[$p + 1] = $measure;
return $p + 1;
}
//测试
$arr = [8,32,12,35,66,77,2,4];
QuickSort($arr, 0, count($arr) - 1);
print_r($arr);
/**
* output:
* Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
*/
4. 堆排序
<?php
/**
* 堆排序法
* 思路：最大堆，将顶点（即最大值）放到最后，然后最剩下的再运行保持最大堆特性，然后在取最大值到倒数第二... 直到将所有节点值取出。
* 复杂度：
* 空间复杂度：原址操作
* 时间复杂度：O(nlogn) 程序的空间局部性不好，不利于缓存，因为处理的数组元素都不是相邻的
* @param $arr 数组
*/
function HeapSort(&$arr)
{
$len = count($arr);
BuildMaxHeap($arr, $len);
for($i = $len - 1; $i > 0; $i--)
{
$tmp = $arr[$i];
$arr[$i] = $arr[0];
$arr[0] = $tmp;
MaxHeapify($arr, 0, --$len);
}
}
/**
* 父节点下标
* @param int $index
* @return int
*/
function Parent($index)
{
return (int)(($index - 1)/2);
}
/**
* 左子节点下标
* @param int $index
* @return int
*/
function Left($index)
{
return 2 * $index + 1;
}
/**
* 右子节点下标
* @param int $index
* @return int
*/
function Right($index)
{
return 2 * $index + 2;
}
/**
* 保持最大堆的性质
* @param array $arr
* @param int $index 下标
* @param int $len 数组长度
*/
function MaxHeapify(&$arr, $index, $len)
{
$left = Left($index);
$right = Right($index);
$largest = $index;
if($left < $len && $arr[$left] > $arr[$index]) {
$largest = $left;
}
if($right < $len && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
if($index != $largest) {
$tmp = $arr[$index];
$arr[$index] = $arr[$largest];
$arr[$largest] = $tmp;
MaxHeapify($arr, $largest, $len);
}
}
/**
* 建堆
* @param array $arr
* @param int $len 数组长度
*/
function BuildMaxHeap(&$arr, $len)
{
$start = (int)($len/2) - 1;
for($i = $start; $i >= 0; $i--) {
MaxHeapify($arr, $i, $len);
}
}
//测试
$arr = [8,32,12,35,66,77,2,4];
HeapSort($arr);
print_r($arr);
/**
* output:
* Array
(
[0] => 2
[1] => 4
[2] => 8
[3] => 12
[4] => 32
[5] => 35
[6] => 66
[7] => 77
)
*/
附上部分算法的go实现
package main
import "fmt"
func main() {
arr := []int{8,6,12,35,66,77,2,32}
//fmt.Println(InsertSort(arr))
//MergeSort(&arr, 0, len(arr) -1)
QuickSort(&arr, 0, len(arr) -1)
fmt.Println(arr)
}
func InsertSort(arr []int) []int {
total := len(arr)
if total == 0 {
return arr
}
for i:=1; i < total; i++ {
j := i - 1
tmp := arr[i]
for j >= 0 && tmp < arr[j] {
arr[j+1] = arr[j]
j--
}
arr[j+1] = tmp
}
return arr
}
func MergeSort(arr *[]int, start, end int) {
if start < end {
mid := (start + end) / 2
MergeSort(arr, start, mid)
MergeSort(arr, mid + 1, end)
Merge(arr, start, mid, end)
}
}
func Merge(arr *[]int, start, mid, end int) {
var left, right []int
for i := start; i <= mid; i++ {
left = append(left, (*arr)[i])
}
for i := mid + 1; i <= end; i++ {
right = append(right, (*arr)[i])
}
l, r := 0,0
lenLeft := len(left)
lenRight := len(right)
j := start
for l<lenLeft && r<lenRight {
if left[l] < right[r] {
(*arr)[j] = left[l]
j++
l++
} else {
(*arr)[j] = right[r]
j++
r++
}
}
for l < lenLeft {
(*arr)[j] = left[l]
j++
l++
}
for r < lenRight {
(*arr)[j] = right[r]
j++
r++
}
}
func QuickSort(arr *[]int, start, end int) {
if start < end {
mid := Partition(arr, start, end)
QuickSort(arr, start, mid - 1)
QuickSort(arr, mid + 1, end)
}
}
func Partition(arr *[]int, start, end int) int {
measure := (*arr)[end]
p := start - 1 //p用于表示小于基准数值的数的下标，比如有一个比基准数值小，那么该数下标为0，两个则是1，以此类推...
for i := start; i <= end; i++ {
if (*arr)[i] < measure {
if i > p+1 {
tmp := (*arr)[i]
(*arr)[i] = (*arr)[p+1]
(*arr)[p+1] = tmp
}
p++
}
}
(*arr)[end] = (*arr)[p+1]
(*arr)[p+1] = measure
return p+1
}
