javascript基本排序算法

忘是亡心i 2021-09-18 23:18 380阅读 0赞

咱们在这说一下基本的排序算法吧！

以下主要说到基础的三种排序【冒泡，选择，插入】，处理大量数据的【快排】

### 先说一下原理： ###

1、冒泡排序：

冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTg1NTEx_size_16_color_FFFFFF_t_70][]

//冒泡排序
        bubbleSort() {
            for(var i = 1; i< this.data.length; i++) {
                for(var j = 0; j< this.data.length -i; j++) {
                    if(this.data[j] < this.data[j+1]) {
                        var temp = this.data[j];
                        this.data[j] = this.data[j+1];
                        this.data[j+1] = temp;
                    }
                }
            }
            return this.data
        }

2、选择排序：

选择排序会用到嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素；内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTg1NTEx_size_16_color_FFFFFF_t_70 1][]

//选择排序
        selectionSort() {
            for(var i = 0; i< this.data.length-1; i++) {
                for(var j = i+ 1;j < this.data.length; j++) {
                    if(this.data[i] < this.data[j]) {
                        var temp = this.data[i];
                        this.data[i] = this.data[j];
                        this.data[j] = temp
                    }
                }
            }
            return this.data;
        }

3、插入排序：

插入排序类似于人类按数字或字母顺序对数据进行排序。例如，让班里的每个学生上交一张写有他的名字、学生证号以及个人简介的索引卡片。学生交上来的卡片是没有顺序的，但是我想让这些卡片按字母顺序排好，这样就可以很容易地与班级花名册进行对照了。

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置，就像之前介绍的姓氏卡片一样。

![20190517202540508.png][]

//插入排序
        insertionSort() {
            for(var i = 1; i< this.data.length; i++) {
                var temp = this.data[i];
                var j = i;
                while(j>0 && (this.data[j-1] >= temp)) {
                    this.data[j] = this.data[j-1];
                    --j
                }
                this.data[j] = temp;
            }
            return this.data;
        }
        insertionSort1() {
            for(var i = 1; i< this.data.length; i++) {
                for(var j = i; j>0; j--) {
                    if(this.data[j-1] > this.data[j]) {
                        var temp = this.data[j];
                        this.data[j] = this.data[j-1];
                        this.data[j-1] = temp;
                    }  else {
                        break;
                    }
                }
            }
            return this.data
        }

以上这三种排序算法的复杂度非常相似，从理论上来说，它们的执行效率也应该差不多。要确定这三种算法的性能差异。经过测试：选择排序和插入排序要比冒泡排序快，插入排序是这三种算法中最快的。

4、快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。  
        这个算法首先要在列表中选择一个元素作为基准值（pivot）。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTg1NTEx_size_16_color_FFFFFF_t_70 2][]

//快速排序
        quickSort(arr) {
            if(arr.length == 0) {
                return [];
            }
            let left = [];
            let right = [];
            let point = arr[0];
            for(var i = 1; i< arr.length; i++) {
                if(arr[i] < point) {
                    left.push(arr[i]);
                } else {
                    right.push(arr[i]);
                }
            }
            return this.quickSort(left).concat(point, this.quickSort(right))
        }

源码地址： [https://github.com/GuoYuFu123/test-project/blob/master/arithmetic/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.html][https_github.com_GuoYuFu123_test-project_blob_master_arithmetic_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95.html]

参考：《数据结构与算法JavaScript描述》

# **原创不易，自由转载，保留出处** #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTg1NTEx_size_16_color_FFFFFF_t_70]: /images/20210812/d501ad25e1484d178ca8da8889a8ebc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTg1NTEx_size_16_color_FFFFFF_t_70 1]: /images/20210812/c5b667dd767b4592bdff95ed15c0e9c6.png
[20190517202540508.png]: /images/20210812/790576a8242f4a6ea4bc1c19e70e39e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTg1NTEx_size_16_color_FFFFFF_t_70 2]: /images/20210812/5a7a99a27588440b87d5e2c7ffb53e95.png
[https_github.com_GuoYuFu123_test-project_blob_master_arithmetic_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95.html]: https://github.com/GuoYuFu123/test-project/blob/master/arithmetic/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.html