插入排序代码,JS代码库,德仔网

代码语言

代码分类

【JS】插入排序

作者:金荣 / 发布于2014/12/31/ 595


	/**
	* 插入排序
	* @param {Array} arr
	* @returns {Array} ret
	*/
	function insertionSort(arr) {
	 // 从1开始，因为一个元素的序列，始终是有序的
	 for(var i = 1, j; i < arr.length; i++) {
	 j = i;
	 // 保存待排序元素
	 v= arr[j];
	 // 如果有序序列中的元素大于待插入的元素，则有序列序列中的元素向后移动一个位置
	 // 向后移到一个位置，会覆盖待排序的元素，但我们前面有保存待排序元素，所以待排序元素不会丢失
	 // 同时，也留出一个位置，以插入待排序元素
	 // 直到找一个已经排序的元素，其不大于待排序元素，将待排序元素插入到这里。
	 // 如果遍历到有序序列的开始位置，也不存在一个元素不大于待排序元素，则将待排序元素插入到已经排序序列的开始
	 while(arr[j-1] > v) {
	 arr[j] = arr[j-1];
	 j--;
	 if(j === 0) {
	 break;
	 }
	 }
	 arr[j] = v;
	 }
	 return arr;
	}
	// qunit
	test('insertion-sort', function () {
	 var arr1 = [1,5,3,6,4,2];
	 var arr2 = [1,5,4,6,4,2];
	 propEqual(insertionSort(arr1), [1,2,3,4,5,6]);
	 propEqual(insertionSort(arr2), [1,2,4,4,5,6]);
	});

试试其它关键字

　插入排序　

同语言下

可能有用的

金荣贡献的其它代码(7)