对数组的排序是平时可能经常用到的，也是面试中经常考察的知识点，下面介绍几种常见的排序
一、排序算法
冒泡排序
原理
两两相邻的数进行比较，如果反序就交换，否则不交换
复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)
代码实现
Go：
// 冒泡排序
func bubbleSort(arr []int) []int {
count := len(arr)
if 1 >= count {
return arr
}
for i := 0; i < count; i++ {
for j := 0; j < count-1; j++ {
// 从小到大
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
// 从大到小
// if arr[j] < arr[j+1] {
// arr[j], arr[j+1] = arr[j+1], arr[j]
// }
}
}
return arr
}PHP：
<?php
/**
* 快速排序.
* @param array $arr 待排序数组
* @return array
*/
function bubblesort($arr) {
$len = count($arr);
//从小到大
for($i = 1; $i < $len; $i++){
for ($j = $len-1; $j >= $i; $j--) {
if ($arr[$j] < $arr[$j-1]) {//如果是从大到小的话，只要在这里的判断改成if($b[$j]>$b[$j-1])就可以了
$tmp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $tmp;
}
}
}
return $arr;
}快速排序
原理
选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。
复杂度
时间复杂度：O(nlog2n)，最差：O(n^2)
空间复杂度：O(n)，最差：O(log2n)
代码实现
GO:
func partition(arr []int, left int, right int) int {
temp := arr[left]
i := left
j := right
for i != j {
// 哨兵 j 向左移动，查找小于基准数 temp 时停下
for arr[j] >= temp && i < j {
j--
}
// 哨兵 i 向右移动，查找大于基准数 temp 时停下
for arr[i] <= temp && i < j {
i++
}
// 交换 i,j 位置
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
// 将基准数归位
arr[left], arr[i] = arr[i], arr[left]
return i
}
func quickSort(arr []int, left int, right int) {
if left < right {
p := partition(arr, left, right)
quickSort(arr, left, p-1)
quickSort(arr, p+1, right)
}
}
func main() {
arr := []int{4, 5, 8, 1, 7, 2, 6, 3}
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}Go：
// 快速排序
func quickSort(arr []int, left int, right int) {
if left > right {
return
}
temp := arr[left]
i := left
j := right
for i != j {
// 哨兵 j 向左移动，查找小于基准数 temp 时停下
for arr[j] >= temp && i < j {
j--
}
// 哨兵 i 向右移动，查找大于基准数 temp 时停下
for arr[i] <= temp && i < j {
i++
}
// 交换 i、j 位置
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
// 将基准数归位
arr[left], arr[i] = arr[i], arr[left]
quickSort(arr, left, i-1)
quickSort(arr, j+1, right)
}PHP：
<?php
/**
* 快速排序
*
* @param array $value 待排序数组
* @param array $left 左边界
* @param array $right 右边界
* @return array
*/
function quickSort(&$value, $left, $right) {
// 左右重合，跳出
if ($left >= $right) {
return;
}
$base = $left;
do {
// 最右边开始找第一个小于基准点的值，然后互换位置
for ($i = $right; $i > $base; --$i) {
if ($value[$base] > $value[$i]) {
$tmp = $value[$i];
$value[$i] = $value[$base];
$value[$base] = $tmp;
$base = $i;
break;
}
}
// 最左边开始找第一个大于基准点的值，互换位置
for ($j = $left; $j < $base; ++$j) {
if ($value[$base] < $value[$j]) {
$tmp = $value[$j];
$value[$j] = $value[$base];
$value[$base] = $tmp;
$base = $j;
break;
}
}
} while ($i > $j);// 直到索引重合
// 开始递归
// 以当前索引为分界
// 开始排序左部分
quicksort($value, $left, $i - 1);
quicksort($value, $i + 1, $right);
}
// $value = [1,4,2,7,6,4,2];
// quickSort($value,0,count($value) - 1);
// print_r($value);选择排序
原理
每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列起始位置，直到全部排序的数据元素排完
复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)
代码实现
Go：
// 选择排序
func selectSort(arr []int) []int {
length := len(arr)
for i := 0; i < length-1; i++ {
min := i
for j := i + 1; j < length; j++ {
if arr[min] > arr[j] {
min = j
}
}
arr[i], arr[min] = arr[min], arr[i]
}
return arr
}PHP：
<?php
/**
* 选择排序
*
* @param array $arr 待排序数组
* @return array
*/
function selectSort($arr) {
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
//假设最小值为$i
$min = $i;
for ($j = $i + 1; $j < $len; $j++) {
//发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较
if ($arr[$min] > $arr[$j]) {
$min = $j;
}
}
//已经确定了当前的最小值的位置，如果发现最小值的位置与当前假设的位置$i不同，则位置互换即可
if ($min != $i) {
$tmp = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}
// $list = array(10,3,5,7,18,11,45,64,74,23,21,6);
// $list = selectSort($list);
// print_r($list);插入排序
原理
每次从无序表中取出第一个元素，把他到有序表合适的位置，使有序表依然有序
示例
复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)
代码实现
/**
* 插入排序.
* @param array $arr 待排序数组
* @return array
*/
function insertSort($arr) {
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$tmp = $arr[$i];
for ($j = $i - 1; $j >= 0; $j--) {
//发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
if ($tmp < $arr[$j]) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
break;
}
}
}
return $arr;
}
// $list = array(10,3,5,7,18,11,45,64,74,23,21,6);
// $list = insertSort($list);
// print_r($list);希尔排序
原理
把待排序的数据根据增量分成几个子序列，对子序列进行插入排序，直到增量为1，直接进行插入排序；增量的排序，一般是数组的长度的一半，再变为原来增量的一半，直到增量为1
示例
对49，38，65，97，76，13，27，49，55，04 十个数字排序
增量分别为：ceil(10 / 2) = 5，ceil(5 / 2) = 3，ceil(3 / 2) = 2，ceil(2 / 1) = 1
初始： 49，38，65，97，76，13，27，49，55，04
第一趟： 13，27，49，55，04，49，38，65，97，76
第二趟： 13，04，49，38，27，49，55，65，97，76
第三趟： 13，04，27，38，49，49，55，65，97，76
第四趟： 13，04，27，38，49，49，55，65，76，97
复杂度
时间复杂度：O(nlog2n)，最差：O(n^2)
空间复杂度：O(1)
代码实现
<?php
/**
* 希尔排序(对直接插入排序的改进)
* @param array $arr 待排序数组
* @return array
*/
function shellSort(&$arr) {
$count = count($arr);
//增量
$inc = $count;
do {
//计算增量
$inc = ceil($inc / 2);
for ($i = $inc; $i < $count; $i++) {
//设置哨兵
$temp = $arr[$i];
//需将$temp插入有序增量子表
for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
$arr[$j + $inc] = $arr[$j]; //记录后移
}
//插入
$arr[$j + $inc] = $temp;
}
//增量为1时停止循环
} while ($inc > 1);
}
// $arr = array(49,38,65,97,76,13,27,49,55,04);
// shellSort($arr);
// print_r($arr);归并排序
原理
归并排序：又称合并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，
即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。
归并排序的一个缺点是它需要存储器有另一个大小等于数据项数目的数组。如果初始数组几乎占满整个存储器，那么归并排序将不能工作，但是如果有足够的空间，归并排序会是一个很好的选择。
复杂度
时间复杂度：O(nlog2n)
空间复杂度：O(n)
代码实现
Golang：
func merge(left []int, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
for len(left) != 0 {
result = append(result, left[0])
left = left[1:]
}
for len(right) != 0 {
result = append(result, right[0])
right = right[1:]
}
return result
}
// 归并排序
func mergeSort(arr []int) []int {
length := len(arr)
if length < 2 {
return arr
}
middle := length / 2
left := arr[0:middle]
right := arr[middle:]
return merge(mergeSort(left), mergeSort(right))
}PHP：
function mergeSort($arr)
{
$len = count($arr);
if ($len < 2) {
return $arr;
}
$middle = floor($len / 2);
$left = array_slice($arr, 0, $middle);
$right = array_slice($arr, $middle);
return merge(mergeSort($left), mergeSort($right));
}
function merge($left, $right)
{
$result = [];
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
while (count($left))
$result[] = array_shift($left);
while (count($right))
$result[] = array_shift($right);
return $result;
}二、查找算法
二分查找
原理
先和中间数对比，若和中间不等，且小于中间数，则在左边查找，反之在右侧查找
复杂度
时间复杂度：O(log2n)
空间复杂度：迭代：O(1)，递归：O(log2n)
代码实现
GO：
func binarySearch(arr []int, search int) int {
low, high := 0, len(arr)
for low <= high {
mid := (low + high) / 2
if arr[mid] == search {
return mid
} else if arr[mid] > search {
high = mid - 1
} else {
low = mid + 1
}
}
return -1
}PHP：
<?php
/**
* 二分查找
* @param array $data 查找数组
* @param string $search 匹配元素
* @return string
*/
function binarySearch($data, $search){
$low = 0;
$high = count($data) - 1;
while( $low <= $high ){
$mid = floor( ($low + $high) / 2 );
if( $data[$mid] == $search ){
return $mid;
}
if( $data[$mid] > $search ){
$high = $mid - 1;
}
if($data[$mid] < $search){
$low = $mid + 1;
}
}
return -1;
}顺序查找
原理
按照顺序查找，暴力
复杂度
时间复杂度：O(n)
空间复杂度：O(1)
代码实现
<?php
/**
* 顺序查找
* @param array $data 查找数组
* @param string $search 匹配元素
* @return string
*/
function search($data, $search){
$len = count($)
for ($i = 0; $i < $len; $i++) {
if ($search == $data[$i]) {
return $i;
}
}
return -1;
}
还不快抢沙发