简单的排序算法
主要研究N个正整数排序
算法的简单归纳：1.输入: 一个算法必须有零个或以上输入量
2.输出 :一个算法应该有一个或以上输出量
3.明确性: 算法的描述必须无歧义
4.有限性 : 必须在有限个步骤内结束
5.有效性:又称可行性,能够被执行者实现
定义问题
数组array 含有N个正整数
输入量为array
请将array中的数字从小到大排列
输出量为排好序的数组
例如
var array = [5,2,4,6,8]
function sort(){
你的代码
}
sort(array) === [2,4,5,6,8]
不会做
遇到思维障碍怎么办
1.将抽象的问题转化为具体的问题
2.将没见过的问题转化为见过的问题
1.冒泡排序(教官双手算法:较高的往后站)
通过一轮遍历,最高的一定到右边去了
function sort(array){
var i,j
for(i=0; i<array.length; i++){ //第i次
for(j=0; j<array.length-1-i; j++){ //每一次的起点
//console.log(array[j]+','+array[j+1])
if(array[j]<=array[j+1]){
}else{
swap(array, j, j+1)
//console.log('swap:'+array[j]+','+array[j+1])
}
}
}
return array;
}
function swap(array, a,b){
var temp = array[a]
array[a] = array[b]
array[b] = temp
}
console.log(sort[3,5,2,4,1])
console.log(sort[1,2,1,2,1])
console.log(sort[1])
console.log(sort[])
2.选择排序(教官一指 最矮的到前面来)
function sort(array){
var i
var j
var indexOfMin
for(i=0; i<array.length; i++){
indexOfMin = i
for(j=i+1; j<array.length; j++){
if(array[j] < array[indexOfMin]){
swap(array, j, indexOfMin)
}
}
if(indexOfMin !== i){
swap(array, i, indexOfMin)
}
}
return array;
}
function swap(){
var temp = array[a]
array[a] = array[b]
array[b] = temp
}
console.log(sort([3,5,2,4,1]))
console.log(sort([1,2,1,2,1]))
console.log(sort([1]))
console.log(sort([]))
3.插入排序(起牌算法)
打个比方就类比水浒传一百单八将的排名吧，每个好汉来了不知道自己排老几，怎么办，那就和已经排过级别的人比较，然后找到其对应的位置，单八将宋万、杜迁先上的梁山，先默认杜迁第一来的也是单八将最厉害的，然后宋万来了，一比较宋万厉害，那宋万排第一，杜迁排第二，接下来朱贵来了，朱贵没他们两个厉害，那就排第三，再后来林冲来了，林冲比他们三个都厉害，那林冲排第一，宋万第二，杜迁第三，朱贵第四，依次类推。梁山排名其实就是典型的插入排序。
function insertSort(arr){
for(var i=1; i<arr.length; i++){
var key = arr[i]
var j = i -1
while( arr[j] > key){
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertSort(arr));
4.归并排序(领导算法)
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right){
var result = [];
//console.time('归并排序耗时');
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length){
result.push(left.shift());
}
while (right.length){
result.push(right.shift());
}
//console.timeEnd('归并排序耗时');
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
5.快速排序(自私算法：我前面的都比我矮 我后面的都比我高)
function quickSort(array, left, right) {
console.time('1.快速排序耗时');
if (left < right) {
var x = array[right], i = left - 1, temp;
for (var j = left; j <= right; j++) {
if (array[j] <= x) {
i++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
console.log(array) ;
console.log(left,i) ;
quickSort(array, left, i - 1);
console.log(array)
console.log(i,right)
quickSort(array, i + 1, right);
}
console.timeEnd('1.快速排序耗时');
console.log(array)
return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];
网友评论