常见的排序算法

今天来学习一下数据结构课程中非常重要的排序算法。

我们学习一下一些常见的排序算法，如冒泡排序、选择排序、快速排序等。

1、冒泡排序

实现思路：

• 对未排序的各元素从头到尾依次比较相邻的两个元素大小关系

• 如果左边的队员大, 则两队员交换位置

• 向右移动一个位置, 比较下面两个队员

• 当走到最右端时, 最大的队员一定被放在了最右边

• 按照这个思路, 从最左端重新开始, 这次走到倒数第二个位置的队员即可.

• 依次类推, 就可以将数据排序完成

我们用数组来存放每一项数据，每次又从左端开始称为新的一趟，排序的趟数为数组长度减一；第一趟比较的次数也是数组长度减一，每增加一趟比较次数就会对应减一。

知道了这些我们通过代码实现：

 //排序数组
        var arr=[5,4,2,14,7,3,9]
        //趟数
        for (let i = 0; i < arr.length-1; i++) {
            //每一趟的比较次数
            for (let j = 0; j < arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]) {
                    let temp=arr[j]
                    arr[j]=arr[j+1]
                    arr[j+1]=temp
                }
            }
        }
        console.log(arr);//[2, 3, 4, 5, 7, 9, 14]

2、选择排序

选择排序改进了冒泡排序, 将交换的次数由O(N²)减少到O(N), 但是比较的次数依然是O(N²)

实现思路：

• 选定第一个索引位置，然后和后面元素依次比较

• 如果后面的队员, 小于第一个索引位置的队员, 则交换位置

• 经过一轮的比较后, 可以确定第一个位置是最小的

• 然后使用同样的方法把剩下的元素逐个比较即可

• 可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后

排序的趟数也是数组的长度-1，每一趟将找到对应的最小值依次从前往后排。

代码实现：

    var arr=[5,4,2,14,7,3,9]
        //趟数
        for (let i = 0; i < arr.length-1; i++) {
          //最小值
          let min=i
          //判断每次的最小值
          for (let j = i+1; j < arr.length; j++) {
            if (arr[min]>arr[j]) {
                min=j
            }
          }
            //将初始设定的最小值与找到的最小值交互
            let temp=arr[min]
            arr[min]=arr[i]
            arr[i]=temp
        }
        console.log(arr);

 3、插叙排序

插入排序是简单排序中效率最好的一种.

插入排序也是学习其他高级排序的基础, 比如希尔排序/快速排序, 所以也非常重要.

插叙排序的实现的核心是局部排序

局部排序：比如在一个队列中的人, 我们选择其中一个作为标记的队员. 这个被标记的队员左边的所有队员已经是局部有序的.

这意味着, 有一部门人是按顺序排列好的. 有一部分还没有顺序.

实现思路：

• 从第一个元素开始，该元素可以认为已经被排序

• 取出下一个元素，在已经排序的元素序列中从后向前扫描

• 如果该元素（已排序）大于新元素，将该元素移到下一位置

• 重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置

• 将新元素插入到该位置后, 重复上面的步骤.

实现代码：

var arr = [5, 4, 2, 14, 7, 3, 9]
        //循环判断每一个元素
        for (let i = 1; i < arr.length; i++) {
            //从下标1开始，因为最开始数组第一个元素即下标取0的元素默认以及排好序了
 
            let j = i
            //设置一个变量标记一下每次插入的那个元素
            let mark = arr[i]
            // console.log(mark);
            while (j > 0 && arr[j - 1] > mark) {
                //直到找到合适的位置才会跳出循环
                arr[j] = arr[j - 1]
                j-- //向前找
            }
            //把我们要插入的那个元素插入到我们找到的位置
            arr[j] = mark
        }
        console.log(arr);

高级排序

快速排序

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

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

快速排序是什么?

• 快速排序其实是我们学习过的最慢的冒泡排序的升级版.

• 我们知道冒泡排序需要经过很多次交换, 才能在一次循环中, 将最大值放在正确的位置.

• 而快速排序可以在一次循环中(其实是递归调用)找出某个元素的正确位置, 并且该元素之后不需要任何移动.

快速排序的思想:

• 快速排序最重要的思想是分而治之.

• 比如我们下面有这样一顿数字需要排序:

  • 第一步: 从其中选出了65. (其实可以是选出任意的数字, 我们以65举个栗子)

  • 第二步: 我们通过算法: 将所有小于65的数字放在65的左边, 将所有大于65的数字放在65的右边.

  • 第三步: 递归的处理左边的数据.(比如你选择31来处理左侧), 递归的处理右边的数据.(比如选择75来处理右侧, 当然选择81可能更合适)

  • 最终: 排序完成

• 和冒泡排序不同的是什么呢?

  • 我们选择的65可以一次性将它放在最正确的位置, 之后不需要任何移动.

  • 需要从开始位置两个两个比较, 如果第一个就是最大值, 它需要一直向后移动, 直到走到最后.

  • 也就是即使已经找到了最大值, 也需要不断继续移动最大值. 而快速排序对数字的定位是一次性的.

代码实现：

  var arr = [5, 4, 2, 14, 7, 3, 9]
 
         function quicksort(arr){
            //如果数组只只有一个或者为空就不用排序
            if (arr.length<=1) {
                return arr
            } else {
                // 找出数组中间的那个数，如果是偶数位时取前一位
                let middle=Math.floor(arr.length/2)
                //将这一位移除
              let newarr = arr.splice(middle,1)
                // console.log(newarr);
                let arrleft=[]//用于接收小于middle位值得数
                let arrright=[]//用于接收大于middle位值得数
 
                arr.forEach(el => {
                    if (el0]) {
                        arrleft.push(el)
                    } else {
                        arrright.push(el)
                    }
                });
 
                // 将其拼接起来，并递归调用
                return quicksort(arrleft).concat(newarr,quicksort(arrright))
            }
         }
         
         console.log(quicksort(arr));

 

归并排序

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

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

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

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

代码实现：

 var arr = [5, 4, 2, 14, 7, 3, 9]
         //拆分
        function divide(arr){
            //如果数组长度小于1就不要拆分了，因为一个数据默认就是有序得
            if (arr.length<=1) {
                return arr
            } else {
                let middle=Math.floor(arr.length/2)
                let arrleft=arr.slice(0,middle)
                // console.log(arrleft);
                let arrright=arr.slice(middle)
                // console.log(arrright);
                //合并并递归
                return hebing(divide(arrleft),divide(arrright))
            }
 
         }
         //合并
        function hebing(arrleft,arrright){
            let arr=[]
            while (arrleft.length>0 && arrright.length>0) {
                if (arrleft[0]0]) {
                arr.push(arrleft.shift())
            }else{
                arr.push(arrright.shift())
            }
            }
           
            return arr.concat(arrleft,arrright)
         }
         console.log(divide(arr));