目录

直接插入排序算法

从第一个元素开始，该元素可以认为已经排好序，取下一个，在已经排好序的序列中向前扫描，有元素大于这个新元素，将已经在排好序中的元素移到下一个位置，依次执行
直接插入排序算法 - 图1

  1. function sortArray(arr){
  2.     for (var i = 1; i < arr.length; i++) {
  3.         var tmp = arr[i];
  4.         for(var j = i -1; j>=0 && arr[j] > tmp; j--){
  5.             arr[j+1] = arr[j];
  6.         }
  7.         arr[j+1] = tmp;
  8.     }
  9. }

改进：插入时使用二分查找
  1. function sortArray(arr){
  2.     for (var i = 1; i < arr.length; i++) {
  3.         var tmp = arr[i],left=0,right=i-1;
  4.         while (left <= right) {
  5.             var mid = parseInt((left+right)/2);
  6.             if (tmp < arr[mid] ) {
  7.                 right = mid -1;
  8.             }else {
  9.                 left = mid +1;
  10.             }
  11.         }
  12.         for(var j = i -1; j>=left; j--){
  13.             arr[j+1] = arr[j];
  14.         }
  15.         arr[left] = tmp;
  16.     }
  17. }

%23%23%23%20%E7%9B%AE%E5%BD%95%0A%5Btoc%5D%0A%20%20*%0A%0A%23%23%23%20%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%20%0A%0A%E4%BB%8E%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%85%83%E7%B4%A0%E5%BC%80%E5%A7%8B%EF%BC%8C%E8%AF%A5%E5%85%83%E7%B4%A0%E5%8F%AF%E4%BB%A5%E8%AE%A4%E4%B8%BA%E5%B7%B2%E7%BB%8F%E6%8E%92%E5%A5%BD%E5%BA%8F%EF%BC%8C%E5%8F%96%E4%B8%8B%E4%B8%80%E4%B8%AA%EF%BC%8C%E5%9C%A8%E5%B7%B2%E7%BB%8F%E6%8E%92%E5%A5%BD%E5%BA%8F%E7%9A%84%E5%BA%8F%E5%88%97%E4%B8%AD%E5%90%91%E5%89%8D%E6%89%AB%E6%8F%8F%EF%BC%8C%E6%9C%89%E5%85%83%E7%B4%A0%E5%A4%A7%E4%BA%8E%E8%BF%99%E4%B8%AA%E6%96%B0%E5%85%83%E7%B4%A0%EF%BC%8C%E5%B0%86%E5%B7%B2%E7%BB%8F%E5%9C%A8%E6%8E%92%E5%A5%BD%E5%BA%8F%E4%B8%AD%E7%9A%84%E5%85%83%E7%B4%A0%E7%A7%BB%E5%88%B0%E4%B8%8B%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE%EF%BC%8C%E4%BE%9D%E6%AC%A1%E6%89%A7%E8%A1%8C%0A%0A!%5B91b76e8e4dab9b0cad9a017d7dd431e2.gif%5D(evernotecid%3A%2F%2FD2915699-A379-4AAB-999E-4534E3EAFB1A%2Fappyinxiangcom%2F25807730%2FENResource%2Fp9)%0A%0A%0A%60%60%60%0Afunction%20sortArray(arr)%7B%0A%09for%20(var%20i%20%3D%201%3B%20i%20%3C%20arr.length%3B%20i%2B%2B)%20%7B%0A%09%09var%20tmp%20%3D%20arr%5Bi%5D%3B%0A%09%09for(var%20j%20%3D%20i%20-1%3B%20j%3E%3D0%20%26%26%20arr%5Bj%5D%20%3E%20tmp%3B%20j—)%7B%0A%09%09%09arr%5Bj%2B1%5D%20%3D%20arr%5Bj%5D%3B%0A%09%09%7D%0A%09%09arr%5Bj%2B1%5D%20%3D%20tmp%3B%0A%09%7D%0A%7D%0A%60%60%60%0A%0A%23%23%23%23%23%20%E6%94%B9%E8%BF%9B%EF%BC%9A%E6%8F%92%E5%85%A5%E6%97%B6%E4%BD%BF%E7%94%A8%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%0A%0A%60%60%60%0Afunction%20sortArray(arr)%7B%0A%09for%20(var%20i%20%3D%201%3B%20i%20%3C%20arr.length%3B%20i%2B%2B)%20%7B%0A%09%09var%20tmp%20%3D%20arr%5Bi%5D%2Cleft%3D0%2Cright%3Di-1%3B%0A%09%09while%20(left%20%3C%3D%20right)%20%7B%0A%09%09%09var%20mid%20%3D%20parseInt((left%2Bright)%2F2)%3B%0A%09%09%09if%20(tmp%20%3C%20arr%5Bmid%5D%20)%20%7B%0A%09%09%09%09right%20%3D%20mid%20-1%3B%0A%09%09%09%7Delse%20%7B%0A%09%09%09%09left%20%3D%20mid%20%2B1%3B%0A%09%09%09%7D%0A%09%09%7D%0A%09%09for(var%20j%20%3D%20i%20-1%3B%20j%3E%3Dleft%3B%20j—)%7B%0A%09%09%09arr%5Bj%2B1%5D%20%3D%20arr%5Bj%5D%3B%0A%09%09%7D%0A%09%09arr%5Bleft%5D%20%3D%20tmp%3B%0A%09%7D%0A%7D%0A%60%60%60%0A