归并排序

具体实现

GitHub版本库的归并排序。

算法实现

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

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
num 1000 sort cost time is 0.0038759708404541 s
num 10000 sort cost time is 0.28233289718628 s
num 100000 sort cost time is 36.840610027313 s

算法分析

最坏时间复杂度 О(nlog n)
最优时间复杂度 О(nlog n)
平均时间复杂度 О(nlog n)
空间复杂度   О(n)

参考链接

  1. 归并排序

选择排序

具体实现

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版本库的选择排序。

算法实现

采用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. 旋转字符串