技术分享：基本排序算法

2023-08-10 18:52:04

 前言：

 今天我给大家分享一点排序算法的知识。大概要花30分钟的时间，我尽量控制在20分钟左右。

首先，我想问大家一个问题，你们知道的排序算法有哪些？冒泡排序？快速排序？

那你们知道它们之间的差异是什么？有的快有的慢对吧？没错，排序算法分为基本排序算法和高级排序算法。我今天要讲的就是基本排序算法。请看下面的目录。

 

技术主题：基本排序算法

目录：

一、冒泡排序

  1. 原理
  2. 实现方法

二、选择排序

  1. 原理
  2. 实现方法

三、插入排序

  1. 原理
  2. 实现方法

 

四、如何通过测试来比较这三种算法的速度？

 

五、其他（有时间的话就讲）

【问题1】sort()方法用的是什么排序算法？

【问题2】for循环中++i 和 i++ 的区别？

 

 基本排序算法有三种，冒泡排序、选择排序、插入排序。我会依次讲它们的原理和实现方法。最后会讲下如何比较它们的排序速度。

 

冒泡排序

我们先来看冒泡排序，冒泡排序是最基本的排序算法，也是最慢的。

它的原理是什么呢？我用表格给大家演示。更直观。（打开表格，随机输入一串数据）

 从第一个数字开始，和它相邻的数字比较，左边比右边大就交换。一直重复这个过程，直到最大的数字移到最右端。

技术分享：基本排序算法

 

 

 不知道大家听懂了没有？有问题可以提出来哦。没问题的话，那我给大家看下代码怎么实现这种算法。看完代码我再给大家演示一遍也可以。

function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}


/**冒泡排序 */
function bubbleSort(arr) {
    for (var outer = arr.length; outer >= 2; --outer) {
        console.log(arr.toString());
        for (var inner = 0; inner <= outer - 1; ++inner) {
            if (arr[inner] > arr[inner+1]) {
                swap(arr, inner, inner + 1);
            }
        }
    }
    console.log(arr.toString());
}


/**选择排序 */
function selectionSort(arr) {
    var min;
    for (var outer = 0; outer < arr.length - 1; ++outer) {
        console.log(arr.toString());
        min = outer;
        for (var inner = outer + 1; inner < arr.length; ++inner) {
            if (arr[inner] < arr[min]) {
                min = inner;
            }
        }
        swap(arr, outer, min);
    }
    console.log(arr.toString());
}

/**插入排序 */
function insertionSort(arr) {
    var temp, inner;
    for (var outer = 1; outer <= arr.length - 1; ++outer) {
        console.log(arr.toString());
        temp = arr[outer];
        inner = outer;
        while(inner > 0 && (arr[inner-1] >= temp)) {
            arr[inner] = arr[inner - 1];
            --inner;
        }
        arr[inner] = temp;
    }
    console.log(arr.toString());
}

 

这里有3个函数。分别用来实现冒泡排序、选择排序、插入排序。

我先讲一下他们的共同点，第一、都是嵌套循环，第二、都用到了交换函数swap，请看swap的代码。

swap函数

function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

 

 

现在看下冒泡排序函数

/**冒泡排序 */
function bubbleSort(arr) {
    for (var outer = arr.length; outer >= 2; --outer) {
        console.log(arr.toString());
        for (var inner = 0; inner <= outer - 1; ++inner) {
            if (arr[inner] > arr[inner+1]) {
                swap(arr, inner, inner + 1);
            }
        }
    }
    console.log(arr.toString());
}

 

外层的for循环是用来控制内层for循环的长度的。所以它是递减的。

（。。。。）讲完后

我再给大家用表格演示一遍冒泡排序的过程，一边对照代码一边演示

技术分享：基本排序算法

 

现在用代码执行一遍，看看代码执行的冒泡排序和我演示的过程是不是一致的。执行结果如下：

技术分享：基本排序算法

 

 

大家有什么问题吗？没有的话我继续讲选择排序。
（时间有限，我得快点讲）

 

选择排序

请看表格。

技术分享：基本排序算法

 

 请看代码。

/**选择排序 */
function selectionSort(arr) {
    var min;
    for (var outer = 0; outer < arr.length - 1; ++outer) {
        console.log(arr.toString());
        min = outer;
        for (var inner = outer + 1; inner < arr.length; ++inner) {
            if (arr[inner] < arr[min]) {
                min = inner;
            }
        }
        swap(arr, outer, min);
    }
    console.log(arr.toString());
}

 

同样也用代码验证一下[9, 2, 6, 3, 8, 0]

技术分享：基本排序算法

 

 有些循环输出的结果和上一次是一样的，我在表格中省略掉了。

 

选择排序就是这样。大家有什么疑问吗？要不要我用表格再演示一遍。没有的话我继续讲插入排序。

 

插入排序

请看表格，还是这一组数据。

技术分享：基本排序算法

 

 看下插入排序的方法

/**插入排序 */
function insertionSort(arr) {
    var temp, inner;
    for (var outer = 1; outer <= arr.length - 1; ++outer) {
        console.log(arr.toString());
        temp = arr[outer];
        inner = outer;
        while(inner > 0 && (arr[inner-1] >= temp)) {
            arr[inner] = arr[inner - 1];
            --inner;
        }
        arr[inner] = temp;
    }
    console.log(arr.toString());
}

代码验证一下

技术分享：基本排序算法

 

 

到这里三种基本排序算法都讲完了。

你们都听懂了吗？我提个问题吧，你们觉得哪一种排序算法好？

我们需要一个客观的衡量。

这三种排序算法的复杂度非常相似。从理论上来说，他们的执行效率也应该差不多。现在我们就做一个测试来比较它们的效率，看看到底哪个更快。

这个测试怎么来做呢？我们不可能手动输入1000,10000个数据来测试。所以，

首先我们要准备2个工具。一个可以生成随机数组的类。还有一个问题是如何计时。这个等下再说。先看怎么生成数组。

function CArray(numElements) {
    this.dataStore = [];
    this.pos = 0;
    this.numElements = numElements;
    this.toString = toString;
    this.setData = setData;
    this.swap = swap; // 交换方法
    this.bubbleSort = bubbleSort; // 冒泡排序
    this.selectionSort = selectionSort; // 选择排序
    this.insertionSort = insertionSort; // 插入排序

    for (var i = 0; i < numElements; ++i) {
        this.dataStore[i] = i;
    }
}

function setData() {
    for (var i = 0; i < this.numElements; ++i) {
        this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1)); // 这里为什么要+1？
    }
}

function toString() {
    var restr = '';
    for (var i = 0; i < this.dataStore.length; ++i) {
        restr += this.dataStore[i] + ' ';
        if (i > 0 & i % 10 == 0) {
            restr += '\n'
        }
    }
    return restr;
}

function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

/**冒泡排序 */
function bubbleSort() {
    var len = this.dataStore.length;
    for (var outer = len; outer >= 2; --outer) {
        for (var inner = 0; inner <= outer - 1; ++inner) {
            if (this.dataStore[inner] > this.dataStore[inner+1]) {
                swap(this.dataStore, inner, inner + 1);
            }
        }
    }
}

/**选择排序 */
function selectionSort() {
    var min;
    for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
        min = outer;
        for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
            if (this.dataStore[inner] < this.dataStore[min]) {
                min = inner;
            }
        }
        swap(this.dataStore, outer, min);
    }
}

/**插入排序 */
function insertionSort() {
    var temp, inner;
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        temp = this.dataStore[outer];
        inner = outer;
        while(inner > 0 && (this.dataStore[inner-1] >= temp)) {
            this.dataStore[inner] = this.dataStore[inner - 1];
            --inner;
        }
        this.dataStore[inner] = temp;
    }
}

这里面的冒泡排序、选择排序和插入排序的三个方法和上面用的稍微有些区别，那就是不用传入数组，直接调用实例上的内置方法。其他都一样。

我们先来生成一个长度100，值为0-100之间的数组。

为了节省时间，这些代码我都提前准备好了。请看

var numElements = 100;
var nums = new CArray(numElements);
nums.setData();
console.log(nums.toString());

结果如下：

技术分享：基本排序算法

 

 

现在数据准备好了。我们来看计时怎么写？

先给大家看一个小例子

var start = new Date().getTime();
for (var i = 1; i < 1000; ++i) {
    console.log(i);
}
var stop = new Date().getTime();
var elapsed = stop - start;
console.log('消耗的时间为：' + elapsed + ' 毫秒');

运行一下就可以看到这个简单的for循环执行需要时间

技术分享：基本排序算法

 

 

最后把这个计时方法用到排序算法测速上。

var start = new Date().getTime();
nums.bubbleSort();
var stop = new Date().getTime();
var elapsed = stop - start;
console.log(numElements + ' 个元素执行【冒泡排序】消耗的时间为：' + elapsed + ' 毫秒');

start = new Date().getTime();
nums.selectionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log(numElements + ' 个元素执行【选择排序】消耗的时间为：' + elapsed + ' 毫秒');

start = new Date().getTime();
nums.insertionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log(numElements + ' 个元素执行【插入排序】消耗的时间为：' + elapsed + ' 毫秒');

 

先看下100个数据三种排序算法的速度分别是多少？

结果如下：

技术分享：基本排序算法

 

 差不多。

再看1000个数据的情况，把numElements的值改成1000.

技术分享：基本排序算法

 

 差距已经出来了。再看看10000个数据如何？

技术分享：基本排序算法

 

 这个差距非常明显了。

今天的主要内容就是这些。大家有什么疑问可以提出来。

有时间的话，我想提个问题，你们知道sort()用的什么排序算法吗？

【答】

ECMAScript没有定义使用哪种排序算法，各个浏览器的实现方式会有不同。火狐中使用的是归并排序，Chrome使用的是插入排序和快速排序的结合排序算法。数组长度不超过10时，使用插入排序。超过10则用快速排序。因为在数组较短时插入排序更有效。

 

今天的分享到此结束，谢谢大家！

 

上一篇：JAVA基础-内部类


下一篇：Java内部类及其实例化