插入排序基本思想
插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
示例代码
1.C++
for(int i=2;i<=n;i++)//从第二个数开始排序 { key=a[i];//待记录插入的数字 j=i-1;//令j=已有序列的尾位置 while(j>=1 and key<a[j])//从后往前遍历序列的已有序列,直到第一个比key小的位置 { a[j+1]=a[j]; j--; } a[j+1]=key; }
2.PHP
function insertionSort($arr) { $len = count($arr); for ($i = 1; $i < $len; $i++) { $preIndex = $i - 1; $current = $arr[$i]; while($preIndex >= 0 && $arr[$preIndex] > $current) { $arr[$preIndex+1] = $arr[$preIndex]; $preIndex--; } $arr[$preIndex+1] = $current; } return $arr; }
3.JavaScript
function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex+1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = current; } return arr; }