公司网站备案网址,推广软件赚钱的app,哈尔滨开发网站,五指山网站开发价格插入排序 算法描述#xff1a; 1. 从第一个元素开始#xff0c;该元素可以认为已经被排序 2. 取出下一个元素#xff0c;在已经排序的元素序列中从后向前扫描 3. 如果该元素#xff08;已排序#xff09;大于新元素#xff0c;将该元素移到下一位置 4. 重复步骤 3 1. 从第一个元素开始该元素可以认为已经被排序 2. 取出下一个元素在已经排序的元素序列中从后向前扫描 3. 如果该元素已排序大于新元素将该元素移到下一位置 4. 重复步骤 3直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到该位置后 6. 重复步骤 2~5 现有一组数组 arr [5, 6, 3, 1, 8, 7, 2, 4]
[5] 6 3 1 8 7 2 4 //第一个元素被认为已经被排序[5,6] 3 1 8 7 2 4 //6与5比较放在5的右边[356] 1 8 7 2 4 //3与6和5比较都小则放入数组头部[1,3,5,6] 8 7 2 4 //1与3,5,6比较则放入头部[1,3568] 7 2 4[1,356,78] 2 4[12,356,78] 4[12,3456,78] 123456789101112131415123456789101112131415 编程思路双层循环外循环控制未排序的元素内循环控制已排序的元素将未排序元素设为标杆与已排序的元素进行比较小于则交换位置大于则位置不动
function insertSort(arr){var tmp;for(var i1;iarr.length;i){tmp arr[i];for(var ji;j0;j--){if(arr[j-1]tmp){arr[j]arr[j-1];}else{arr[j]tmp;break;}}}return arr
}123456789101112131415123456789101112131415 时间复杂度O(n^2) 选择排序 算法描述直接从待排序数组中选择一个最小或最大数字放入新数组中。
[1] 5 6 3 8 7 2 4
[1,2] 5 6 3 8 7 4
[1,2,3] 5 6 8 7 2 4
[1,2,3,4] 5 6 8 7
[1,2,3,4,5] 6 8 7
[1,2,3,4,5,6] 8 7
[1,2,3,4,5,6,7] 8
[1,2,3,4,5,6,7,8] 1234567812345678 编程思路先假设第一个元素为最小的然后通过循环找出最小元素然后同第一个元素交换接着假设第二个元素重复上述操作即可
function selectionSort(array) {var length array.length,i,j,minIndex,minValue,temp;for (i 0; i length - 1; i) {minIndex i;minValue array[minIndex];for (j i 1; j length; j) {//通过循环选出最小的if (array[j] minValue) {minIndex j;minValue array[minIndex];}}// 交换位置temp array[i];array[i] minValue;array[minIndex] temp;}return array
}12345678910111213141516171819202122231234567891011121314151617181920212223 时间复杂度O(n^2) 归并排序 算法描述 1. 把 n 个记录看成 n 个长度为 l 的有序子表 2. 进行两两归并使记录关键字有序得到 n/2 个长度为 2 的有序子表 3. 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
5 6 3 1 8 7 2 4[5,6] [3,1] [8,7] [2,4][5,6] [1,3] [7,8] [2,4][5,6,1,3] [7,8,2,4][1,3,5,6] [2,4,7,8][1,2,3,4,5,6,7,8]12345678910111234567891011 编程思路将数组一直等分然后合并
function merge(left, right) {var tmp [];while (left.length right.length) {if (left[0] right[0])tmp.push(left.shift());elsetmp.push(right.shift());}return tmp.concat(left, right);
}function mergeSort(a) {if (a.length 1) return a;var mid Math.floor(a.length / 2), left a.slice(0, mid), right a.slice(mid);return merge(mergeSort(left), mergeSort(right));
}12345678910111213141516171819202122231234567891011121314151617181920212223 时间复杂度O(nlogn) 快速排序 算法描述
在数据集之中选择一个元素作为”基准”pivot。所有小于”基准”的元素都移到”基准”的左边所有大于”基准”的元素都移到”基准”的右边。这个操作称为分区 (partition)操作分区操作结束后基准元素所处的位置就是最终排序后它的位置。对”基准”左边和右边的两个子集不断重复第一步和第二步直到所有子集只剩下一个元素为止。
5 6 3 1 8 7 2 4pivot
|
5 6 3 1 9 7 2 4
|
storeIndex5 6 3 1 9 7 2 4//将5同6比较大于则不更换
|
storeIndex3 6 5 1 9 7 2 4//将5同3比较小于则更换|storeIndex3 6 1 5 9 7 2 4//将5同1比较小于则不更换|storeIndex
...3 6 1 4 9 7 2 5//将5同4比较小于则更换|storeIndex3 6 1 4 5 7 2 9//将标准元素放到正确位置|
storeIndex pivot1234567891011121314151617181920212223242526272812345678910111213141516171819202122232425262728 上述讲解了分区的过程然后就是对每个子区进行同样做法
function quickSort(arr){if(arr.length1) return arr;var partitionIndexMath.floor(arr.length/2);var tmparr[partitionIndex];var left[];var right[];for(var i0;iarr.length;i){if(arr[i]tmp){left.push(arr[i])}else{right.push(arr[i])}}return quickSort(left).concat([tmp],quickSort(right))
}123456789101112131415123456789101112131415 上述版本会造成堆栈溢出所以建议使用下面版本 原地分区版主要区别在于先进行分区处理将数组分为左小右大
function quickSort(arr){function swap(arr,right,left){var tmp arr[right];arr[right]arr[left];arr[left]tmp;}function partition(arr,left,right){//分区操作var pivotValuearr[right]//最右面设为标准var storeIndexleft;for(var ileft;iright;i){if(arr[i]pivotValue){swap(arr,storeIndex,i);storeIndex;}}swap(arr,right,storeIndex);return storeIndex//返回标杆元素的索引值}function sort(arr,left,right){if(leftright) return;var storeIndexpartition(arr,left,right);sort(arr,left,storeIndex-1);sort(arr,storeIndex1,right);}sort(arr,0,arr.length-1);return arr;
}123456789101112131415161718192021222324252627123456789101112131415161718192021222324252627 时间复杂度O(nlogn) 冒泡排序 算法描述 1. 比较相邻的元素。如果第一个比第二个大就交换他们两个。 2. 对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。 3. 针对所有的元素重复以上的步骤除了最后一个。 4. 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。5.
5 6 3 1 8 7 2 4[5 6] 3 1 8 7 2 4 //比较5和65 [6 3] 1 8 7 2 45 3 [6 1] 8 7 2 45 3 1 [6 8] 7 2 45 3 1 6 [8 7] 2 45 3 1 6 7 [8 2] 45 3 1 6 7 2 [8 4]5 3 1 6 7 2 4 8 // 这样最后一个元素已经在正确位置所以下一次开始时候就不需要再比较最后一个
123456789101112131415161718123456789101112131415161718 编程思路外循环控制需要比较的元素比如第一次排序后最后一个元素就不需要比较了内循环则负责两两元素比较将元素放到正确位置上
function bubbleSort(arr){var lenarr.length;for(var ilen-1;i0;i--){for(var j0;ji;j){if(arr[j]arr[j1]){var tmp arr[j];arr[j]arr[j1];arr[j1]tmp}}}return arr;
}1234567891011121312345678910111213 时间复杂度O(n^2) 参考资料 排序效果 常见排序算法 排序算法 维基百科
