首页 > 代码库 > 插入排序与选择排序【线性方法】

插入排序与选择排序【线性方法】

 1 var A = [5, 2, 4, 6, 1, 3]; 2 console.log("排序前-:") 3 A.forEach(function (element, index, arr) { 4     console.log(index, "-----------", element); 5 }); 6  7 function insertion_sort(A) { 8     var len = A.length; 9     for (var i = 1; i < len; i++) {10         let key = A[i];11         let j = i - 1;12         while (j >= 0 && A[j] > key) {13             A[j + 1] = A[j];14             j--;15         }16         A[j + 1] = key;17     }18 }19 20 insertion_sort(A);21 console.log("排序后-");22 A.forEach(function (element, index, arr) {23     console.log(index, "-----------", element);24 });

 上面的代码是算法导论里给的伪代码例子,是一种升序的写法,那降序的怎么写呢:

 1 function insertion_sort(A) { 2     var len = A.length; 3     for (var i = 1; i < len; i++) { 4         let key = A[i]; 5         let j = i - 1; 6         while (j >= 0 && A[j] < key) { 7             A[j + 1] = A[j]; 8             j--; 9         }10 11         A[j + 1] = key;12     }13 }

 

在给一个选择排序的算法(升序):

 1 function SelectSort(A) { 2     var len = A.length; 3     for (var i = 0; i < len; i++) { 4         var min = A[i]; 5         var index = i; 6         var temp = A[i]; 7         for (var j = i + 1; j < len; j++) { 8             if (A[j] < min) { 9                 min = A[j];10                 index = j;11             }12         }13         A[i] = min;14         A[index] = temp;15 16     }17 18 }

 线性排序的方法里还有个冒泡,就是两两互换,也是线性的。下一篇讲解分治。

插入排序与选择排序【线性方法】