交换排序有2种，冒泡排序和快速排序
这里先谈冒泡排序，冒泡排序的原理是什么？
大的数往下沉，小的数往上冒。通俗来讲，就是对相邻的2个数做比较，如果前一个数比后一个数大，交换他们的位置，最后达到大的数在后面，小的数在前面的效果；
还是用代码来讲解，写一个函数：
function maopao(arr){
for(var j = 0;j < arr.length-1;j++){
for(var i = 0;i < arr.length-1;i++){
if (arr[i] >arr[i+1]) { //前一个数大于后一个数，交换
var tmp = arr[i];
arr[i]=arr[i+1];
arr[i+1] = tmp;
}
}
}
return arr;
}
当然这个是最传统的冒泡排序,这种排序方式的结果是无论对什么数组，都需要进行完整的n * n次for循环。这里有2种改进方式，让他的循环次数少一些。
第一种：我们设置一个变量pos，让它来记录一次循环之后最后交换的位置，而pos后面的数不需要交换了。当pos等于0的时候，说明整个数组已经没有要交换的了。
接下来我们看看代码怎么实现，依然是写一个函数：
function maopao1(arr){
var n = arr.length-1;
while(n>0){
var pos = 0;
for(var i = 0; i < n; i++){
if(a[i]>a[i+1]){
pos = i; //记录pos,由于for循环会走完，所以pos记录的是此次循环最后的i值
var a = arr[i];
arr[i] = arr[i+1];
arr[i+1]=a;
}
}
n = pos; //下次循环就只到pos了
}
return arr;
}
上面是第一种改进方式，接下来说说第二种改进方式。
冒泡排序的一次循环可以排出数组的最大值或最小值，那我们试着用2个循环求出最大值和最小值。然后就不再去管最大值和最小值了，每次循环就少计算2个数。
代码来看，写一个函数：
function maopao2(arr){
var max = arr.length-1;
var min = 0;
if (max>min) {
for(var i = min; i < max;i++){
if (arr[i] > arr[i+1]) {
var a = arr[i];
arr[i] = arr[i+1];
arr[i+1]=a;
}
}
max--;
for(var i = max; i > min;i--){
if (arr[i] < arr[i-1]) {
var a = arr[i];
arr[i] = arr[i+1];
arr[i+1]=a;
}
}
min++;
}
return arr;
}
网友评论