五种常见数组排序算法

# 一、冒泡排序

冒泡排序算法思路

1. 比较相邻的两个数组元素，如果第一个比第二个大，则交换两个的值
2. 对每一对相邻元素做同样的工作，从开始第一对比较到最后一对，最后的元素应该是最大值
3. 针对所有元素重复以上步骤，除了最后一个
4. 针对越来越少的元素重复以上步骤，直至没有任何一对数字比较

代码实现：

<?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);

# 二、选择排序

选择排序算法思路：

1. 假设第一个元素为最小值，记下其下标
2. 寻找右侧剩下的元素，若有更小的，记录其下标
3. 如果有新的最小值，交换元素
4. 往右重复以上步骤，直至元素是最后一个

代码实现：

<?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);

# 三、插入排序

插入排序算法思路：

1. 假设第一个元素已经排好
2. 取出第二个元素，作为待插入元素
3. 与已经排好序的最右侧元素比较
4. 如果后面的元素大于前面的元素，说明前面的元素不在正确的位置上，则往后退一个位置，然后让新的元素填充进去，继续向前比
5. 重复以上步骤，直到元素插入正确位置
6. 重复以上步骤，直至所有元素插入正确位置

代码实现：

<?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);

# 四、快速排序

快速排序算法思路:

1. 假设将第一个元素作为比较元素
2. 定义两个数组(left,right),然后从第二个元素开始跟比较元素相比，小的放大left数组里，大的放到right数组里
3. 这是中间的元素位置肯定是对的
4. 用递归实现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));

# 五、归并排序

归并排序算法思路：

1. 分而治之的思想
2. 将要排序的数组从中间元素分开成两个数组，然后在定义一个新数组用来放归并的元素
3. 把两个数组挨个比较，较小的先放进新定义的归并数组
4. 直至两个数组都比较完，这时有一个数组只剩一个最大的元素，然后将归并完的数组与这个元素合并
5. 注意左右两个数组递归排序内部元素

代码实现：

<?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));