# 一、冒泡排序
冒泡排序算法思路
- 比较相邻的两个数组元素,如果第一个比第二个大,则交换两个的值
- 对每一对相邻元素做同样的工作,从开始第一对比较到最后一对,最后的元素应该是最大值
- 针对所有元素重复以上步骤,除了最后一个
- 针对越来越少的元素重复以上步骤,直至没有任何一对数字比较
代码实现:
<?php
//冒泡排序
arr = array(4, 2, 76, 2, 7, 1, 9, 45);
//控制循环次数
for (i = 0; len = count(arr), i<len; i++) { //控制最大值
for (j = 0; j<len - 1 - i;j++) {
//交换值
if (arr[j] > arr[j + 1]) {
arr[j] = arr[j] + arr[j + 1];
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
}
}
}
print_r($arr);
# 二、选择排序
选择排序算法思路:
- 假设第一个元素为最小值,记下其下标
- 寻找右侧剩下的元素,若有更小的,记录其下标
- 如果有新的最小值,交换元素
- 往右重复以上步骤,直至元素是最后一个
代码实现:
<?php
//选择排序
arr = array(2, 6, 34, 2, 67, 33, 9);
//确定交换多少次,一次找到一个最小值
for (i = 0; len = count(arr), i<len; i++) { //假定第一个元素为最小值min = i; //拿最小值比较比较剩下的元素 for (j = i + 1;j < len;j++) {
//比较当前元素与选定的最小元素
if (arr[j] < arr[min]) {
//不符合交换下标
min =j;
}
}
//交换当前选定的最小值与实际最小值
if (min !=i) {
arr[min] = arr[min] + arr[i];
arr[i] = arr[min] - arr[i];
arr[min] = arr[min] - arr[i];
}
}
print_r($arr);
# 三、插入排序
插入排序算法思路:
- 假设第一个元素已经排好
- 取出第二个元素,作为待插入元素
- 与已经排好序的最右侧元素比较
- 如果后面的元素大于前面的元素,说明前面的元素不在正确的位置上,则往后退一个位置,然后让新的元素填充进去,继续向前比
- 重复以上步骤,直到元素插入正确位置
- 重复以上步骤,直至所有元素插入正确位置
代码实现:
<?php
//插入排序
arr=array(6,3,8,9,5,3,7,10);
//确定插入多少回(假设一个数组一次插入到正确位置,同时第一个位置是对的)
for (i=1;len=count(arr),i<len;i++){ //取出当前要插入的值temp=arr[i];
//让该元素与前面已经排好序的元素比较
for (j=i-1;j>=0;j--){
if (arr[j]>temp){arr[j+1]=arr[j];arr[j]=temp;
}
else{
//比前一个元素大,所以不用比较在往前的,直接退出循环
break;
}
}
}
print_r($arr);
# 四、快速排序
快速排序算法思路:
- 假设将第一个元素作为比较元素
- 定义两个数组(left,right),然后从第二个元素开始跟比较元素相比,小的放大left数组里,大的放到right数组里
- 这是中间的元素位置肯定是对的
- 用递归实现left和right元素的排序
代码实现:
<?php
//快速排序
arr = array(2, 0, 1, 7, 3, 5, 6);
function quick_sort(arr)
{
len = count(arr);
//如果数组长度小于等于1,直接返回该数组
if (len <= 1) {
returnarr;
}
left =right = array();
//取出第一个元素作为比较元素,剩下的元素比他小放到left,大的放到right
for (i = 1;i < len;i++) {
if (arr[i] < arr[0]) {left[] = arr[i];
} else {
right [] =arr[i];
}
}
//递归排好左右两个数组元素left = quick_sort(left);right = quick_sort(right);
//合并三个数组
return array_merge(left, (array)arr[0],right);
}
print_r(quick_sort($arr));
# 五、归并排序
归并排序算法思路:
- 分而治之的思想
- 将要排序的数组从中间元素分开成两个数组,然后在定义一个新数组用来放归并的元素
- 把两个数组挨个比较,较小的先放进新定义的归并数组
- 直至两个数组都比较完,这时有一个数组只剩一个最大的元素,然后将归并完的数组与这个元素合并
- 注意左右两个数组递归排序内部元素
代码实现:
<?php
arr = array(4, 7, 2, 1, 5, 9, 3);
function merge_sort(arr)
{
len = count(arr);
if (len <= 1) {
returnarr;
}
//拆分
middle = round(len / 2);
left = array_slice(arr, 0, middle);right = array_slice(arr,middle);
//递归左右两个数组
left = merge_sort(left);
right = merge_sort(right);
//两个数组里都有元素才比较
while (count(left) && count(right)) {
//取出两个数组中第一个元素比较,小的放到mm[] = left[0]<right[0] ? array_shift(left) : array_shift(right);
}
return array_merge(m,left, right);
}
print_r(merge_sort(arr));