插入排序

插入排序Python实现

    import random

    a=[random.randint(1,999) for x in range(0,36)]

    # 直接插入排序算法
    def insertionSort(a):
      for i in range(1,len(a)):
        # 若下标为i的元素小于下标为i-1的元素，则将下标为i的元素放到合适位置
        if a[i] < a[i-1]:
          tmp = a[i]
          j = i-1
          # 寻找a[i]的合适位置，并将a[i-1]至a[i]新位置的元素依次后移
          while j >= 0 and tmp < a[j]:
            a[j+1] = a[j]
            j = j-1

          # 将a[i]放到新位置
          a[j+1] = tmp

    insertionSort(a)
    print(a)

插入排序PHP实现

    <?php
    // 生成待排序数组
    $a = [];
    for($i=0;$i<36;$i++){
      array_push($a,mt_rand(1,999));
    }
    shuffle($a);

    /**
     * 插入排序 insertion sort
     * @param [type] $a 待排序数组的引用
     * @return null
     */
    function insertionSort(&$a){
      for($i = 1;$i<count($a);$i++){
        // 若下标为i的元素小于下标为i-1的元素，则将下标为i的元素放到合适位置
        if($a[$i] < $a[$i-1]){
          $tmp = $a[$i];
          // 寻找a[i]的合适位置，并将a[i-1]至a[i]新位置的元素依次后移
          for($j = $i-1; $j>=0 && $tmp<$a[$j];$j--)
            $a[$j+1] = $a[$j];
          // 将a[i]放到新位置
          $a[$j+1] = $tmp;
        }
      }

    }

    insertionSort($a);
    var_dump($a);

插入排序时间复杂度分析

插入排序算法的时间复杂度为O（n2），但是插入排序法比冒泡和选择排序的性能更好。

以上这篇插入排序_Python与PHP的实现版(推荐)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持脚本之家。