JS排序算法

快来打我* 2023-06-24 04:43 14阅读 0赞

1. 冒泡排序  
程序员启蒙排序算法 基础中的基础

思想：

先建立一个外部循环为总比较次数 再写一个内循环为两两比较的次数  
第一个内循环结束应将数组中最大的数排在了数组的最右边  
经过arr.length-1次循环 数组中的元素按照从小到大的顺序排列

var arr = \[3, 4, 15, 80, 2, 7, 6, 5, 8, 9, 10, 16, 13\]; // length = 13

function insertSort(arr) \{  
            var current, preIndex;  
            var len = arr.length;  
            for (var i = 1; i < len; i++) \{  
            //当前元素的前一个元素下标  
                preIndex = i - 1;  
            // 将需要排序的元素用current保存起来以免因下面下标变化而取错值  
                current = arr\[i\];  
            // 开始内部循环将第一个值开始排序 终止条件为当前元素下标大于数组的第0位并且当前元素大于前一个元素    否则的话将前一个元素赋值给当前元素（arr\[preIndex+1\]）  
            //然后将前一个元素下标-1 继续向前比较  
                while (preIndex >= 0 && current < arr\[preIndex\]) \{  
                    arr\[preIndex + 1\] = arr\[preIndex\];  
                    preIndex--;  
                \}  
            // 当current大于前一个元素时 把保存起来的current赋值给arr\[preIndex\]   
                arr\[preIndex + 1\] = current;

\}  
            return arr;  
        \}  
        console.log(insertSort(arr));  
  
3.快速排序  
思想：

创建两个数组left right  
取一个基准值可以数组中任一元素 下面取了数组的中间元素并且从数组中剥离出来  
将数组中的元素与基准值比较 小于基准值的放进左边 left数组 大于基准值的放进右边right数组  
重复 步骤2 3  
var arr = \[3, 4, 2, 6, 5, 8, 9, 10, 16, 13\]; // length = 10  
        function quickSort(arr) \{  
            if (arr.length <= 1) \{ return arr; \}  
            //     基准值  
            var pivot = arr\[Math.floor(arr.length / 2)\];  
            arr.splice(arr.indexOf(pivot), 1);  
            var left = \[\];  
            var right = \[\];  
            for (var i = 0; i < arr.length; i++) \{

if (arr\[i\] < pivot) \{  
                    left.push(arr\[i\]);  
                \} else \{  
                    right.push(arr\[i\]);  
                \}

\}  
            return quickSort(left).concat(\[pivot\], quickSort(right));

console.log(quickSort(arr));  
  
4.选择排序  
思想：  
1.遍历数组，设置最小值的索引为 0，  
2.如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。  
3.如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。