作者:络风落泪_411 | 来源:互联网 | 2023-08-04 17:04
1.冒泡排序法 1.1 概念 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
1.2 原理示意图
1.3 代码 const arr &#61; [ 5 , 2 , 7 , 8 , 34 , 7 , 39 , 12 , 56 , 9 , 1 ] function bubbleSort ( arr) { const len &#61; arr. lengthfor ( let i &#61; 0 ; i < len; i&#43;&#43; ) { for ( let j &#61; 1 ; j < len - i; j&#43;&#43; ) { if ( arr[ j - 1 ] > arr[ j] ) { [ arr[ j - 1 ] , arr[ j] ] &#61; [ arr[ j] , arr[ j - 1 ] ] } } } return arr} console. log ( bubbleSort ( arr) )
改进的冒泡排序法&#xff1a;
function bubbleSort ( arr) { let temp &#61; null , flag &#61; 1 const len &#61; arr. lengthfor ( let i &#61; 0 ; i <&#61; len - 1 && flag &#61;&#61;&#61; 1 ; i&#43;&#43; ) { flag &#61; 0 for ( let j &#61; 0 ; j < len - i; j&#43;&#43; ) { if ( arr[ j] > arr[ j &#43; 1 ] ) { temp &#61; arr[ j &#43; 1 ] arr[ j &#43; 1 ] &#61; arr[ j] arr[ j] &#61; tempflag &#61; 1 } } } return arr}
2.插入排序法 2.1 概念 一般也被称为直接插入排序&#xff08;Insert Sort&#xff09;。对于少量元素的排序&#xff0c;它是一个有效的算法。插入排序是一种最简单的排序方法&#xff0c;它的基本思想是将一个记录插入到已经排好序的有序表中&#xff0c;从而一个新的、记录数增1的有序表。在其实现过程使用双层循环&#xff0c;外层循环对除了第一个元素之外的所有元素&#xff0c;内层循环对当前元素前面有序表进行待插入位置查找&#xff0c;并进行移动。
插入排序是指在待排序的元素中&#xff0c;假设前面n-1(其中n>&#61;2)个数已经是排好顺序的&#xff0c;现将第n个数插到前面已经排好的序列中&#xff0c;然后找到合适自己的位置&#xff0c;使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入&#xff0c;直到整个序列排为有序的过程&#xff0c;称为插入排序。
2.2 原理示意图 插入排序的工作方式像许多人排序一手扑克牌。开始时&#xff0c;我们的左手为空并且桌子上的牌面向下。然后&#xff0c;我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置&#xff0c;我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的&#xff0c;原来这些牌是桌子上牌堆中顶部的牌 。
2.3 代码 function quickSort ( arr) { if ( arr. length <&#61; 1 ) { return arr} const middleIndex &#61; Math. floor ( arr. length / 2 ) const middle &#61; arr. splice ( middleIndex, 1 ) [ 0 ] const leftArr &#61; [ ] , rightArr &#61; [ ] for ( let i &#61; 0 ; i < arr. length; i&#43;&#43; ) { const current &#61; arr[ i] current < middle ? leftArr. push ( current) : rightArr. push ( current) } return quickSort ( leftArr) . concat ( middle, quickSort ( rightArr) ) }
另一种解法&#xff1a;
const arr &#61; [ 5 , 2 , 7 , 8 , 34 , 7 , 39 , 12 , 56 , 9 , 1 ] function insertSort ( arr) { const handle &#61; [ arr[ 0 ] ] , len &#61; arr. lengthfor ( let i &#61; 1 ; i <&#61; len - 1 ; i&#43;&#43; ) { const current &#61; arr[ i] for ( var j &#61; handle. length - 1 ; j >&#61; 0 ; j-- ) { if ( current > handle[ j] ) { handle. splice ( j &#43; 1 , 0 , current) break } if ( j &#61;&#61;&#61; 0 ) { handle. unshift ( current) } } } return handle} console. log ( insertSort ( arr) )
优化的插入排序法&#xff1a;
function insertSort ( arr) { for ( let i &#61; 1 ; i < arr. length; i&#43;&#43; ) { for ( let j &#61; i; j > 0 ; j-- ) { if ( arr[ j] < arr[ j - 1 ] ) { [ arr[ j - 1 ] , arr[ j] ] &#61; [ arr[ j] , arr[ j - 1 ] ] } } } return arr}
3.快速排序法 3.1 概念 快速排序&#xff08;Quick Sort&#xff09;是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是&#xff1a;通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小&#xff0c;然后再按此方法对这两部分数据分别进行快速排序&#xff0c;整个排序过程可以递归进行&#xff0c;以此达到整个数据变成有序序列。
3.2 原理示意图 ##### 3.3 代码 function quickSort ( arr) { if ( arr. length <&#61; 1 ) { return arr} const middleIndex &#61; Math. floor ( arr. length / 2 ) const middle &#61; arr. splice ( middleIndex, 1 ) [ 0 ] const leftArr &#61; [ ] , rightArr &#61; [ ] for ( let i &#61; 0 ; i < arr. length; i&#43;&#43; ) { const current &#61; arr[ i] current < middle ? leftArr. push ( current) : rightArr. push ( current) } return quickSort ( leftArr) . concat ( middle, quickSort ( rightArr) ) }
另一种写法&#xff1a;
const arr &#61; [ 5 , 2 , 7 , 8 , 34 , 7 , 39 , 12 , 56 , 9 , 1 ] function quickSort ( outter) { function sort ( arr, left &#61; 0 , right &#61; arr. length - 1 ) { if ( left >&#61; right) { return } let i &#61; left, j &#61; rightconst baseVal &#61; arr[ j] while ( i < j) { while ( i < j && arr[ i] <&#61; baseVal) { i&#43;&#43; } arr[ j] &#61; arr[ i] while ( j > i && arr[ j] >&#61; baseVal) { j-- } arr[ i] &#61; arr[ j] } arr[ j] &#61; baseVal sort ( arr, left, j - 1 ) sort ( arr, j &#43; 1 , right) } const newArr &#61; outter. concat ( ) sort ( newArr) return newArr} console. log ( bubbleSort ( arr) )
4.十大排序空间复杂度和时间复杂度&#xff1a;