1. 插入排序法
<?php
/**
* 插入排序
* 思路：從第二個數(shù)起，把當前數(shù)插入到前面已排好序的序列中
* 算法復(fù)雜度：
* 空間復(fù)雜度：原址操作
* 時間復(fù)雜度：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
/**
* 歸并排序法
* 思路：分治法，核心算法在合， 即總的數(shù)組的排序可由兩個已經(jīng)排好序的子數(shù)組的合并得到。
* 復(fù)雜度：
* 空間復(fù)雜度：合并時需要額外兩個子數(shù)組，O(n)
* 時間復(fù)雜度：O(nlogn) 穩(wěn)定排序法
* @param $arr 數(shù)組
* @param $start 初始下標
* @param $end 結(jié)束下標
*/
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);
}
}
/**
* 合并兩個子數(shù)組
* @param $arr 數(shù)組
* @param $start 初始下標
* @param $mid 兩個子數(shù)組的分割點
* @param $end 結(jié)束下標
*/
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. 快速排序
/**
* 快速排序法
* 思路：分治法，核心算法在分?？偟臄?shù)組的排序可以對子數(shù)組的排序得到，子數(shù)組的排序又可以由子子數(shù)組的排序得到...
* 復(fù)雜度：
* 空間復(fù)雜度：原址操作
* 時間復(fù)雜度：平均 O(nlogn)，最差 n^2， 不穩(wěn)定的排序法
* @param $arr 數(shù)組
* @param $start 初始下標
* @param $end 結(jié)束下標
*/
function QuickSort(&$arr, $start, $end)
{
if($start < $end) {
$mid = Partition($arr, $start, $end);
QuickSort($arr, $start, $mid - 1);
QuickSort($arr, $mid + 1, $end);
}
}
/**
* 將數(shù)組分為兩部分，小于基準數(shù)值的在左邊， 大于基準數(shù)值的在右邊，然后返回基準數(shù)值的位置
* @param $arr
* @param $start
* @param $end
*/
function Partition(&$arr, $start, $end)
{
$measure = $arr[$end]; //基準數(shù)值
$p = $start - 1; //p用于表示小于基準數(shù)值的數(shù)的下標，比如有一個比基準數(shù)值小，那么該數(shù)下標為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
/**
* 堆排序法
* 思路：最大堆，將頂點（即最大值）放到最后，然后最剩下的再運行保持最大堆特性，然后在取最大值到倒數(shù)第二... 直到將所有節(jié)點值取出。
* 復(fù)雜度：
* 空間復(fù)雜度：原址操作
* 時間復(fù)雜度：O(nlogn) 程序的空間局部性不好，不利于緩存，因為處理的數(shù)組元素都不是相鄰的
* @param $arr 數(shù)組
*/
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);
}
}
/**
* 父節(jié)點下標
* @param int $index
* @return int
*/
function Parent($index)
{
return (int)(($index - 1)/2);
}
/**
* 左子節(jié)點下標
* @param int $index
* @return int
*/
function Left($index)
{
return 2 * $index + 1;
}
/**
* 右子節(jié)點下標
* @param int $index
* @return int
*/
function Right($index)
{
return 2 * $index + 2;
}
/**
* 保持最大堆的性質(zhì)
* @param array $arr
* @param int $index 下標
* @param int $len 數(shù)組長度
*/
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 數(shù)組長度
*/
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實現(xiàn)
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用于表示小于基準數(shù)值的數(shù)的下標，比如有一個比基準數(shù)值小，那么該數(shù)下標為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
}
