• 数据结构——排序算法（冒泡排序、选择排序、插入排序、归并排序、快速排序、搜索算法）

    目录

    一、排序算法

    二、大O表示法

    三、简单排序

    1、冒泡排序

    2、选择排序

    3、插入排序

    四、高级排序

    1、归并排序

    2、快速排序

    五、搜索算法

    一、排序算法

    排序算法有很多: 冒泡排序/选择排序/插入排序/归并排序/计数排序(counting sort)/基数排序(radix sort)/希尔排序/堆排序/桶排序.

    简单排序: 冒泡排序 - 选择排序 - 插入排序

    高级排序: 归并排序 - 快速排序

    二、大O表示法

    企业规模的概述:

    - 公司可以按照规模分为:小型企业/中型企业/大型企业.
    - 在不说明具体员工人数或者占地面积的情况下，我们可以通过这样大概的概念来描述企业的规模

    大O表示法:

    - 在算法的描述中，我们也可以通过类似的快捷方式来描述计算机算法的效率.
    - 在计算机中，这种粗略的度量被称作”大O”表示法
    - 在算法比较的过程中，我们可能更喜欢说:算法A比算法B快两倍.但是这样的比较有时候没有意义.
    - 在数据项个数发生变化时，算法的效率会跟着发生改变
    - 所以我们通常使用一种算法的速度会如何跟随着数据量的变化的.

     常见的大O表示法

     推导大O表示法

    1. 用常数1取代运行时间中的所有加法常数。 //  76 ==1
    2. 在修改后的运行次数函数中，只保留最高阶项。
    3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

    2N²+3N+1 ==> N²

    三、简单排序

    1、冒泡排序

    冒泡排序的思路:

    - 对未排序的各元素从头到尾依次比较相邻的两个元素大小关系
    - 如果左边的队员高, 则两队员交换位置
    - 向右移动一个位置, 比较下面两个队员
    - 当走到最右端时, 最高的队员一定被放在了最右边
    - 按照这个思路, 从最左端重新开始, 这次走到倒数第二个位置的队员即可.
    - 依次类推, 就可以将数据排序完成

    思路再分析:

    - 第一次找出最高人放在最后, 我们需要两个两个数据项进行比较, 那么这个应该是一个循环操作.
    - 第二次将次高的人找到放在倒数第二个位置, 也是两个比较, 只是不要和最后一个比较(少了一次), 但是前面的两个两个比较也是一个循环操作.
    - 第三次...第四次...
    - 有发现规律吗? 这应该是一个循环中嵌套循环, 并且被嵌套的循环次数越来越少的.
    - 根据这个分析, 你能写出代码实现吗?

    冒泡排序的效率

    - 冒泡排序的比较次数: 
      - 如果按照上面的例子来说, 一共有7个数字, 那么每次循环时进行了几次的比较呢?
      - 第一次循环6次比较, 第二次5次比较, 第三次4次比较....直到最后一趟进行了一次比较.
      - 对于7个数据项比较次数: 6 + 5 + 4 + 3 + 2 + 1
      - 对于N个数据项呢? (N - 1) + (N - 2) + (N - 3) + ... + 1 = N * (N - 1) / 2       N²

    大O表示法: 

    - 大O表示法是描述性能和复杂度的一种表示方法.
    - 推导大O表示法通常我们会使用如下规则: 
      - 用常量1取代运行时间中的所有加法常量
      - 在修改后的运行次数函数中, 只保留最高阶项
      - 如果最高阶项存在并且不是1, 则去除与这个项相乘的常数.

    通过大O表示法推到过程, 我们来推到一下冒泡排序的大O形式. 

    - N * (N - 1) / 2 = N²/2 - N/2,根据规则2, 只保留最高阶项, 编程N² / 2
    - N² / 2, 根据规则3, 去除常量, 编程N²
    - 因此冒泡排序的大O表示法为O(N²)

    冒泡排序的交换次数: 

    - 冒泡排序的交换次数是多少呢?
    - 如果有两次比较才需要交换一次(不可能每次比较都交换一次.), 那么交换次数为N² / 4
    - 由于常量不算在大O表示法中, 因此, 我们可以认为交换次数的大O表示也是O(N²)c

    2、选择排序

    选择排序的思路:

    - 选定第一个索引位置，然后和后面元素依次比较
    - 如果后面的队员, 小于第一个索引位置的队员, 则交换位置
    - 经过一轮的比较后, 可以确定第一个位置是最小的
    - 然后使用同样的方法把剩下的元素逐个比较即可
    - 可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后

    • 选择排序第一次将第0位置的人取出, 和后面的人(1, 2, 3...)依次比较, 如果后面的人更小, 那么就交换.

    • 这样经过一轮之后, 第一个肯定是最小的人.

    • 第二次将第1位置的人取出, 和后面的人(2, 3, 4...)依次比较, 如果后面的人更小, 那么就交换.

    • 这样经过第二轮后, 第二个肯定是次小的人.

    • 第三轮...第四轮...直到最后就可以排好序了. 有发现规律吗?

    • 外层循环依次取出0-1-2...N-2位置的人作为index(N-1不需要取了, 因为只剩它一个了肯定是排好序的)

    • 内层循环从index+1开始比较, 直到最后一个.

    选择排序的效率

    - 选择排序的比较次数: 
      - 选择排序和冒泡排序的比较次数都是N*(N-1)/2, 也就是O(N²).
    - 选择排序的交换次数: 
      - 选择排序的交换次数只有N-1次, 用大O表示法就是O(N).
      - 所以选择排序通常认为在执行效率上是高于冒泡排序的.

    3、插入排序

    - 局部有序:

      - 插入排序思想的核心是局部有序. 什么是局部有序呢?
      - 比如在一个队列中的人, 我们选择其中一个作为标记的队员. 这个被标记的队员左边的所有队员已经是局部有序的.
      - 这意味着, 有一部门人是按顺序排列好的. 有一部分还没有顺序.

    插入排序的思路:

    - 从第一个元素开始，该元素可以认为已经被排序
    - 取出下一个元素，在已经排序的元素序列中从后向前扫描
    - 如果该元素（已排序）大于新元素，将该元素移到下一位置
    - 重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置
    - 将新元素插入到该位置后, 重复上面的步骤.

    思路再分析:

    - 插入排序应该从下标值1开始(因为0位置默认可以被认为是有序的)
    - 从1位置开始取出元素, 并且判断该元素的大小和0位置进行比较, 如果1位置元素小于0位置元素, 那么交换, 否则不交换.
    - 上面步骤执行完成后, 0 - 1位置已经排序好.
    - 取出2位置的元素, 和1位置进行比较: 
      - 如果2位置元素大于1位置元素, 说明2位置不需要任何动作. 0 - 1 - 2已经排序好.
      - 如果2位置元素小于1位置元素, 那么将1移动到2的位置, 并且2继续和0进行比较.
      - 如果2位置元素大于0位置的元素, 那么将2位置放置在1的位置, 排序完成. 0 - 1 - 2搞定.
      - 如果2位置元素小于1位置的元素, 那么将0位置的元素移动到1位置, 并且将2位置的元素放在0位置, 0 - 1 - 2搞定.
    - 按照上面的步骤, 依次找到最后一个元素, 整个数组排序完成.

    插入排序的效率

    • 插入排序的比较次数:

      • 第一趟时, 需要的最多次数是1, 第二趟最多次数是2, 依次类推, 最后一趟是N-1次.

      • 因此是1 + 2 + 3 + ... + N - 1 = N * (N1) / 2.

      • 然而每趟发现插入点之前, 平均只有全体数据项的一半需要进行比较.

      • 我们可以除以2得到 N * (N - 1) / 4. 所以相对于选择排序, 其他比较次数是少了一半的.

    • 插入排序的复制次数:

      • 第一趟时, 需要的最多复制次数是1, 第二趟最多次数是2, 依次类推, 最后一趟是N-1次.

      • 因此是1 + 2 + 3 + ... + N - 1 = N * (N - 1) / 2.

    • 对于基本有序的情况

      • 对于已经有序或基本有序的数据来说, 插入排序要好很多.

      • 当数据有序的时候, while循环的条件总是为假, 所以它变成了外层循环中的一个简单语句, 执行N-1次.

      • 在这种情况下, 算法运行至需要N(N)的时间, 效率相对来说会更高.

      • 另外别忘了, 我们的比较次数是选择排序的一半, 所以这个算法的效率是高于选择排序的.

    四、高级排序

    1、归并排序

    1、基本思想与过程：**先递归的分解数列**，**再合并数列**（分治思想的典型应用）

    　　（1）将一个数组拆成A、B两个小组，两个小组继续拆，直到每个小组只有一个元素为止。

    　　（2）按照拆分过程逐步合并小组，由于各小组初始只有一个元素，可以看做小组内部是有序的，合并小组可以被看做是合并两个有序数组的过程。

    　　（3）对左右两个小数列重复第二步，直至各区间只有1个数。

    　　下面对数组【42,20,17,13,28,14,23,15】进行归并排序，模拟排序过程如下：

    　　第一步：拆分数组，一共需要拆分三次（logN）；

    　　　　第一次拆成【42,20,17,13】，【28,14,23,15】，

    　　　　第二次拆成【42,20】，【17,13】，【28,14】，【23,15】，、

    　　　　第三次拆成【42】，【20】，【17】，【13】，【28】，【14】，【23】，【15】；

    　　第二步：逐步归并数组，采用合并两个有序数组的方法，每一步其算法复杂度基本接近于O(N)

    　　　　第一次归并为【20,42】，【13,17】，【14,28】，【15,23】

    　　　　第二次归并为【13,17,20,42】，【14,15,23,28】，

    　　　　第三次归并为【13, 14, 15, 17, 20, 23, 28, 42】

    2、快速排序

    快速排序几乎可以说是目前所有排序算法中, 最快的一种排序算法.

    当然, 没有任何一种算法是在任意情况下都是最优的, 比如希尔排序确实在某些情况下可能好于快速排序. 但是大多数情况下, 快速排序还是比较好的选择.

    快速排序的介绍

    - 快速排序的重要性:

      - 如果有一天你面试的时候, 让你写一个排序算法, 你可以洋洋洒洒的写出多个排序算法, 但是如果其中没有快速排序, 那么证明你对排序算法也只是浅尝辄止, 并没有深入的研究过.
      - 因为快速排序可以说是排序算法中最常见的, 无论是C++的STL中, 还是Java的SDK中其实都能找到它的影子.
      - 快速排序也被列为20世纪十大算法之一.

    - 快速排序是什么?

      - 希尔排序相当于插入排序的升级版, 快速排序其实是我们学习过的最慢的冒泡排序的升级版.
      - 我们知道冒泡排序需要经过很多次交换, 才能在一次循环中, 将最大值放在正确的位置.
      - 而快速排序可以在一次循环中(其实是递归调用)找出某个元素的正确位置, 并且该元素之后不需要任何移动.

    - 快速排序的思想:

      - 快速排序最重要的思想是分而治之.
      - 比如我们下面有这样一顿数字需要排序: 
        - 第一步: 从其中选出了65. (其实可以是选出任意的数字, 我们以65举个栗子)
        - 第二步: 我们通过算法: 将所有小于65的数字放在65的左边, 将所有大于65的数字放在65的右边.
        - 第三步: 递归的处理左边的数据.(比如你选择31来处理左侧), 递归的处理右边的数据.(比如选择75来处理右侧, 当然选择81可能更合适)
        - 最终: 排序完成
      - 和冒泡排序不同的是什么呢? 
        - 我们选择的65可以一次性将它放在最正确的位置, 之后不需要任何移动.
        - 需要从开始位置两个两个比较, 如果第一个就是最大值, 它需要一直向后移动, 直到走到最后.
        - 也就是即使已经找到了最大值, 也需要不断继续移动最大值. 而快速排序对数字的定位是一次性的.

    五、搜索算法

    1.  class Sort {
    2.             constructor() {
    3.                 this.item = [];
    4.             }
    5.             push(ele) {
    6.                 this.item.push(ele)
    7.             }
    8.             toString() {
    9.                 return this.item.join("-")
    10.             }
    11.             swap(m, n) {
    12.                 // 交换两个位置的值
    13.                 let temp = this.item[n];
    14.                 this.item[n] = this.item[m]
    15.                 this.item[m] = temp
    16.             }
    17.             bubbleSort() {
    18.                 // 控制趟数   控制次数
    19.                 for (let i = 0; i < this.item.length - 1; i++) {
    20.                     for (let j = 0; j < this.item.length - 1 - i; j++) {
    21.                         // 比较
    22.                         if (this.item[j + 1] < this.item[j]) {
    23.                             this.swap(j, j + 1)
    24.                         }
    25.                     }
    26.                 }
    27.             }
    28.             // 选择排序
    29.             selectionSort() {
    30.                 for (let i = 0; i < this.item.length - 1; i++) {
    31.                     let min = i;
    32.                     for (let j = i + 1; j < this.item.length; j++) {
    33.                         if (this.item[j] < this.item[min]) {
    34.                             min = j
    35.                         }
    36.                     }
    37.                     this.swap(i, min)
    38.                 }
    39.             }
    40.             // 插入排序
    41.             insertionSort() {
    42.                 for (let i = 1; i < this.item.length; i++) {
    43.                     let j = i;
    44.                     let mark = this.item[i];
    45.                     while (this.item[j - 1] > mark && j > 0) {
    46.                         this.item[j] = this.item[j - 1];
    47.                         j--;
    48.                     }
    49.                     this.item[j] = mark
    50.                 }
    51.             }
    52.             // 快速排序
    53.             quicksort() {
    54.                 this.item = this.quick(this.item)
    55.             }
    56.             quick(arr) {
    57.                 if (arr.length <= 1) {
    58.                     return arr
    59.                 } else {
    60.                     // 分
    61.                     let index = Math.floor(arr.length / 2);
    62.                     let middle = arr.splice(index, 1)[0];
    63.  
    64.                     let leftArr = [],
    65.                         rightarr = [];
    66.                     for (let i = 0; i < arr.length; i++) {
    67.                         if (arr[i] < middle) {
    68.                             leftArr.push(arr[i])
    69.                         } else {
    70.                             rightarr.push(arr[i])
    71.                         }
    72.                     }
    73.  
    74.                     return this.quick(leftArr).concat(middle, this.quick(rightarr))
    75.  
    76.                 }
    77.             }
    78.             // 归并排序
    79.             mergerSort() {
    80.                this.item =  this.divide(this.item)
    81.             }
    82.             // 分
    83.             divide(arr) {
    84.                 if (arr.length <= 1) {
    85.                     return arr
    86.                 } else {
    87.                     let index = Math.floor(arr.length / 2);
    88.                     let leftArr = arr.slice(0, index);
    89.                     let rightArr = arr.slice(index);
    90.  
    91.                    return this.merge(this.divide(leftArr), this.divide(rightArr))
    92.                 }
    93.             }
    94.             // 和
    95.             merge(left, right) {
    96.                 let newarr = [];
    97.                 while (left.length && right.length) {
    98.                     if (left[0] < right[0]) {
    99.                         newarr.push(left.shift())
    100.                     } else {
    101.                         newarr.push(right.shift())
    102.                     }
    103.                 }
    104.                 return newarr.concat(left,right)
    105.             }
    106.             shunxuSerach(ele){
    107.                 for (let i = 0; i < this.item.length; i++) {
    108.                     if(this.item[i] == ele){
    109.                         return true
    110.                     }
    111.                 }
    112.                 return false
    113.             }
    114.             // 必须有序
    115.             BinarySearch(ele){
    116.                 let start = 0;
    117.                 let end = this.item.length-1;
    118.                 if(ele < this.item[start] || ele > this.item[end]) return false
    119.                 while( start <= end ){
    120.                     let middle = Math.floor((start + end)/2);
    121.                     if(ele < this.item[middle]){
    122.                         end = middle -1
    123.                     }else if(ele > this.item[middle]){
    124.                         start = middle +1
    125.                     }else{
    126.                         return true
    127.                     }
    128.                 }
    129.                 return false
    130.             }
    131.         }
    132.         let sort = new Sort();
    133.         sort.push(1)
    134.         sort.push(10)
    135.         sort.mergerSort();
    136.         console.log(sort.toString());
    137.         console.log(sort.BinarySearch(9));

  • 相关阅读:
    Android自定义控件（六) Andriod仿iOS控件Switch开关
    已解决（pip安装库报错）Consider using the-- user option or check the permissions.
    MySQL索引事务——小记
    【文件格式_XML_HTML_】XML、HTML文件
    cookie介绍：cookie实现增删改查功能
    WEB前端网页设计 HTML CSS 网页设计参数 - JavaScripts
    Cesium快速上手2-Model图元使用讲解
    【C++】根据遍历确定二叉树
    Python requests有问题
    设计模式-开闭原则和迪米特法则
  • 原文地址：https://blog.csdn.net/qq_52301431/article/details/126529419