快速排序

具体实现

GitHub版本库的选择排序。

算法实现

采用2层循环遍历实现。
1. 第一层循环,从一个元素开始到最后一个元素为止。
2. 选择每次循环的第一个元素为基准。
3. 第二层循环,以第一层循环的第二个数开始,到未排序的数组末尾。
4. 与第二个元素比较,遇到比第一个元素小的数,交换位置。

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
num 1000 sort cost time is 0.012492895126343 s
num 10000 sort cost time is 1.2727150917053 s
num 100000 sort cost time is 146.14201211929 s

算法分析

最坏时间复杂度 О(n²)
最优时间复杂度 О(n²)
平均时间复杂度 О(n²)
空间复杂度   О(n) total, O(1) auxiliary

参考链接

  1. 选择排序

冒泡排序

具体实现

GitHub版本库的冒泡排序。

算法实现

  1. 根据需要排序的个数,进行倒序循环,起点为待排序个数,依次递减,直到1为止。
  2. 第二层循环,从第一个元素(索引为0)开始,到待排序个数实时减一。
  3. 第一次比较,找到比第一个数小的话,进行交换,那么最小的数,必定在第一的位置。
  4. 第二层循环,终止条件$j< $i-1的原因是每次第一层循环完后,会把较少的值交换,故下次不需要再进行排序。

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
num 1000 sort cost time is 0.0314781665802 s
num 10000 sort cost time is 2.6688499450684 s
num 100000 sort cost time is 287.84617590904 s

算法分析

最坏时间复杂度 {\displaystyle O(n^{2})} O(n^{2})
最优时间复杂度 {\displaystyle O(n)} O(n)
平均时间复杂度 {\displaystyle O(n^{2})} O(n^{2})
空间复杂度 总共 {\displaystyle O(n)} O(n),需要辅助空间 {\displaystyle O(1)} O(1)

参考链接

  1. 冒泡排序

字符串反转

具体实现

GitHub版本库的字符串反转。

PHP内置

只支持ASCII字符串

正则实现

/*
其中正则的两个修正符的说明如下:
u (PCRE_UTF8)
此修正符启用了一个 PCRE 中与 Perl 不兼容的额外功能。模式字符串被当成 UTF-8。本修正符在 Unix 下自 PHP 4.1.0 起可用,在 win32 下自 PHP 4.2.3 起可用。
s (PCRE_DOTALL)
如果设定了此修正符,模式中的圆点元字符(.) 匹配所有的字符,包括换行符。没有此设定的话,则不包括换行符。这和 Perl 的 /s 修正符是等效的。排除字符类例如 [^a] 总是匹配换行符的,无论是否设定了此修正符。
*/

截取

/*
mb_strlen — 获取字符串的长度

mb_substr
根据字符数执行一个多字节安全的 substr() 操作。 位置是从 str 的开始位置进行计数。 第一个字符的位置是 0。第二个字符的位置是 1,以此类推。
*/

参考链接

  1. 反转UTF8编码中文字符串
  2. 旋转字符串