/**
* 常用排序总结
* 排序分类：插入排序、交换排序、选择排序和归并排序。
* Created by xj on 2017/3/8.
*/
var array = [3,1,8,9,10,4,5,6,7,2];
var compareTime = 0;
var changeTime = 0;
/**
* 最简单的交换排序，严格意义上来说不算标准的冒泡排序，因为不满足“两两比较相邻记录”的条件。
* 思路：每一个关键字都和它后面的关键字比较，如果当前关键字不是最小的记录，则与相比较的关键
* 字交换位置，这样当前位置的关键字再一次循环后一定是最小值。
* 复杂度：本身有序就是n-1次比较；若正好倒序，则需要进行1+2+3+……+(n-1) = n(n-1)/2次比较，因为总的时间复杂度为O(n²)
*/
function sortBubble1() {
console.log("------交换排序------");
console.log("---" + array + "------");
for(var i = 0; i < this.array.length; i++)
{
for(var j = i; j < this.array.length; j++)
{
if(this.array[j] < this.array[i])
{
this.change(i, j);
}
compareTime ++;
}
console.log("---" + this.array + "---");
}
console.log(this.array + "\n compareTime = " + compareTime + "\n changeTime = " + changeTime);
}
/**
* 真正的冒泡排序，每次循环从序列的末尾开始两两比较，若关键字（n-1）大于n，则交换位置，继续比较（n-2）和（n-1），
* 这样即保证每次循环第一个关键字都是最小值，而且序列后边的较小的关键字也会相对前移。
*/
function sortBubble2() {
console.log("------冒泡排序------");
console.log("---" + array + "------");
for(var i = 0; i < array.length; i++)
{
for(var j = array.length-2; j >= i; j--)
{
if(this.array[j] > this.array[j+1])
{
this.change(j, j+1);
}
compareTime ++;
}
console.log("---" + this.array + "---");
}
console.log(this.array + "\n compareTime = " + compareTime + "\n changeTime = " + changeTime);
}
/**
* 改进的冒泡排序，若存在当一定情况下，序列已经有序，没有必要进行重复的循环判断，减少冗余的比较次数。
*/
function sortBubble3() {
console.log("------冒泡排序改进------");
console.log("---" + array + "------");
var flag = true; //进入循环
for(var i = 0; i < array.length && flag; i++)
{
flag = false; //循环判断关键字置false,若此次循环中没有进行数据移动，则可以确定此时序列已经有序，无需再次进行比较和迁移
for(var j = array.length-2; j >= i; j--)
{
if(this.array[j] > this.array[j+1])
{
this.change(j, j+1);
flag = true; //若有数据移动，说明序列仍是无序，有必要再次进行循环
}
compareTime ++;
}
console.log("---" + this.array + "---");
}
console.log(this.array + "\n compareTime = " + compareTime + "\n changeTime = " + changeTime);
}
/**
* 思想：通过n-1次关键字之间的比较，从n-1+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。
* 优点：相对冒泡排序来说，交换移动数据的次数少了，这样就节约了相应的时间。
* 复杂度：比较次数一样多。对于交换次数而言，最好的时候交换0次，最差的时候交换n-1次。总的时间复杂度O(n²)
* 总结：尽管复杂度相同，但简单选择排序在性能上还是优于冒泡排序。
*/
function sortSelect() {
console.log("------简单选择排序------");
console.log("---" + array + "------");
var min = 0;
for(var i = 0; i < array.length; i++)
{
min = i;
for(var j = i; j < array.length; j++)
{
if(this.array[j] < this.array[min])
{
min = j;
}
compareTime ++;
}
if(min != i)
{
this.change(min, i);
}
console.log("---" + this.array + "---");
}
console.log(this.array + "\n compareTime = " + compareTime + "\n changeTime = " + changeTime);
}
function change(i, j) {
var temp = this.array[i];
this.array[i] = this.array[j];
this.array[j] = temp;
changeTime ++;
}
转载请注明原文地址: https://ju.6miu.com/read-5327.html
