快速排序

具体实现

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

二分法查找-算法学习

二分法查找

二分搜索算法

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)[1]、对数搜索(英语:logarithmic search)[2],是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

具体实现

GitHub版本库的二分法查找。

算法实现

该算法非常快,从已经排序好的数组查找制定的元素。
1. 初始化,分别有两个指向开始的元素和结束的元素。
2. 每次循环后,去掉一半的元素,同时更新对应的开始和结束的指向。
3. 循环结束的条件是开始小于等于结束(默认元素是升序排列)

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
num 1000 search 2992889 cost time is 4.0531158447266E-6 s
num 10000 search 2207856 cost time is 5.9604644775391E-6 s
num 100000 search 1142758 cost time is 8.1062316894531E-6 s

算法分析

最坏时间复杂度 O(log n)}
最优时间复杂度 O(1)}
平均时间复杂度 O(log n)}
空间复杂度 迭代: O(1)}
递归: O(log n)}
(无尾调用消除)

参考链接

  1. 二分法查找
  2. 二分法查找
  3. 二分法查找 百度百科