十大经典排序算法(JavaScript)

男娘i 2022-12-11 15:30 197阅读 0赞

## 十大经典排序算法(JavaScript) ##

> 这段时间琢磨了一下算法题，虽然算法课程在两年前就学了，但是期末才八十多分的我，，，真的啥也没学进去

> 本来也学得没多好，所以就从最基础的开始学吧！  
> 这十大算法都是之前老师在课堂上讲过的，但是，即使之前听的贼认真，很久也没有用也该忘了，况且我听得还不怎么认真呢

> CSDN的界面是真的好丑，这个字体真的丑，还不能切换字体大小，，，（不知道我几乎每篇博客都要吐槽它，会不会给我拉黑了）

> 这就是个自己学习的博客（因为我话多），如果有代码可以优化的还请大家多多指出来，孩子感激不尽呀！！！

>  *  首先是总体框架图
>  *  这十大算法可按照是否为比较算法分为两类：比较类和非比较类
>  *  比较类排序（非线性时间比较类排序）：通过比较来决定元素间的相对次序  
>     \-> 非比较类排序（先行世纪那非比较类排序）：不通过比较来决定元素间的相对次序。  
>     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RhbmdnZ0ppZWVl_size_16_color_FFFFFF_t_70_pic_center]  
>     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RhbmdnZ0ppZWVl_size_16_color_FFFFFF_t_70_pic_center 1]

>  *  时间复杂度，空间复杂度都写在了图里面（还是改成了电子版吧，之前自己写的太丑了）

### 1.冒泡排序（Bubble Sort） ###

冒泡排序的思想很简单。重复走访要排序的元素，一次比较两个元素，顺序错误则调换顺序。一直重复，直到所有的走访中顺序均按照指定（从大到小，从小到大）排序则排序完成。

#### 1.1算法描述（从小到大排列） ####

*  比较相邻元素。如果前一个元素大于后一个元素，则交换顺序。
 *  每一对相邻元素都做同样的工作，直至排序完成。

#### 1.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>sort</title>
    	</head>
    	<body>
    		<p id="bubblesort"></p>
    	</body>
    	<script>
    		function bubblesort(arr){ 
    			var len = arr.length;
    			for (var i = len - 1; i > 0; i++){ 
    				for (var j = 1; j <= i; j++){ 
    					if (arr[j-1] > arr[j]){ 	//相邻两两元素对比
    						var temp = arr[j];
    						arr[j] = arr[j-1];
    						arr[j-1] = temp;
    					}
    				}
    			}
    			return arr;
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("bubblesort").innerHTML = bubblesort(arr);	
    	</script>
    </html>

### 2.选择排序（Selection Sort） ###

选择排序的思想也很简单。首先找到最大（最小）元素放在起始位置，然后在剩余元素中继续寻找最大（最小）元素放在已排序的元素后。以此类推，直至所有元素排序完毕。

#### 2.1算法描述（从小到大） ####

*  初始状态时，有序为空，无序为arr
 *  第一趟排序过后，有序中有一个最小元素，无序中为出去最小元素后的arr序列
 *  n-1趟结束，数组有序

#### 2.2算法实现 ####

这两个都是从小到大排序的，但是第二个是先找出最大元素

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="selectsort1"></p>
    		<p id="selectsort2"></p>
    	</body>
    	<script>
    		function selectsort1(arr){ 
    			var len = arr.length;
    			var minindex;
    			
    			for (var i = 0; i < len; i++){ 
    				minindex = i;
    				for (var j = i+1; j < len; j++){ 
    					if (arr[j] < arr[minindex]){ 
    						minindex = j;
    					}
    				}
    				var temp = arr[i];
    				arr[i] = arr[minindex];
    				arr[minindex] = temp;
    			}
    			return arr;
    		}
    		
    		function selectsort2(arr){ 
    			var len = arr.length;
    			var maxindex;
    			
    			for (var i = len-1; i >=0; i--){ 
    				maxindex = i;
    				for (var j = i-1; j >= 0; j--){ 
    					if (arr[j] >arr[maxindex]){ 
    						maxindex = j;
    					}
    				}
    				var temp = arr[i];
    				arr[i] = arr[maxindex];
    				arr[maxindex] = temp;
    			}
    			return arr;
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("selectsort1").innerHTML = selectsort1(arr);	
    		document.getElementById("selectsort2").innerHTML = selectsort2(arr);	
    	</script>
    </html>

### 3.插入排序（Insertion Sort） ###

插入排序的思想也很简单直观。通过构建有序序列，对未排序的数据，在已排序的序列中从后向前扫描，找到相应位置进行插入。

#### 3.1算法描述（从小到大） ####

*  从第一个元素开始，该元素被认为是已经排序
 *  抽取下一个元素，在已经排序的序列中从后向前扫描，直到出现一个小于它的元素，将其插入该元素后面

#### 3.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="insertsort"></p>
    	</body>
    	<script>
    		function insertsort(arr){ 
    			var len = arr.length;
    			var preindex,current;
    			
    			for (var i = 1; i < len; i++){ 
    				preindex = i-1;
    				current = arr[i];
    				
    				while(preindex >= 0 && arr[preindex] > current){ 
    					var temp;
    					temp = arr[preindex+1];
    					arr[preindex+1] = arr[preindex];
    					arr[preindex] = temp;
    					preindex--;
    				}
    			}
    			return arr;
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("insertsort").innerHTML = insertsort(arr);
    	</script>
    </html>

### 4.希尔排序（Shell Sort） ###

第一个突破O(n\*n)的排序算法，是简单插入排序的升级版。但它是优先比较距离较远的元素。也称为缩小增量排序。

#### 4.1算法描述 ####

*  将需要排序的序列进行分组，分组计算为(length/2)取整数值，每进行一轮分组就会减少一半或者更多。
 *  从下标为0的元素开始，下一个元素为下标加上分组的组数，在序列长度内均为该组的元素。
 *  组内进行排序，从小到大，直至分组数为1结束。

#### 4.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="shellsort"></p>
    	</body>
    	<script>
    		function shellsort(arr){ 
    			var len = arr.length;
    			var temp;
    			for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)){ 	//分组
    				for (var i = 0; i < gap; i++){ 	//组
    					for (var j = 0; j < len / gap; j++){ 	//组成员
    						for ( var z = 0; z < len; z += gap){ 
    							if (arr[z] > arr[z+gap]){ 
    								temp = arr[z];
    								arr[z] = arr[z+gap];
    								arr[z+gap] = temp;
    							}
    						}
    					}
    				}
    			}
    			return arr;
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("shellsort").innerHTML = shellsort(arr);	
    	</script>
    </html>

### 5.归并排序（Merge Sort） ###

归并排序建立在归并操作上。采用分治法的思想。将已有的有序子序列进行合并，得到完全有序的序列；先使子序列有序然后实现整体有序。  
两个有序表合并为一个称为二路归并，n个称为n路归并。

#### 5.1算法描述 ####

*  将长度为n的序列分为两个长度为n/2的序列，为单数则右边比左边多一个；
 *  对这两个子序列分别进行归并和排序；
 *  将排序号的两个子序列合并。

#### 5.2 代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="mergesort"></p>
    	</body>
    	<script>
    		function mergesort(arr){ 
    			var len = arr.length;
    			if (len < 2){ 
    				return arr;
    			}
    			
    			var middle = Math.floor(len / 2);
    			var left = arr.slice(0,middle);
    			var right = arr.slice(middle);
    			
    			return merge(mergesort(left),mergesort(right));	//递归
    		}
    		
    		function merge(left,right){ 
    			var res = [];
    			while (left.length > 0 && right.length > 0){ 
    				if (left[0] <= right[0]){ 
    					res.push(left.shift());	//将小者放入结果中，并在原数组中删除
    				}else{ 
    					res.push(right.shift());
    				}
    			}
    			
    			while (left.length)		//左右两边不均等，所以最后的数值直接放入
    				res.push(left.shift());
    			while (right.length)
    				res.push(right.shift());
    			
    			return res;
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("mergesort").innerHTML = mergesort(arr);	
    	</script>
    </html>

### 6.快速排序（Quick Sort） ###

通过一趟排序，将序列分为两部分，一部分比关键字小，另一部分比关键字大，将关键字排到两部分之间，进行第二轮排序。

#### 6.1算法描述 ####

*  从数列中挑出一个元素作为基准（pivot），一般为第一个；
 *  将所有比基准元素小的元素排在前面，大的排在后面；
 *  将基准元素放在中间位置；
 *  递归将第一个元素选为基准元素。

#### 6.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="quicksort"></p>
    	</body>
    	<script>
    		function quicksort(arr,left,right){ 
    			
    			var left = typeof left != 'number' ? 0 : left;
    			var right = typeof right != 'number' ? arr.length - 1 : right;
    			
    			if (left >= right){ 
    				return;
    			}
    			
    			var start = left;
    			var end = right;
    			var flag = left;
    			
    			while (left < right){ 
    				//当队尾元素 >= 基准元素，向前挪动right
    				while (left < right && arr[right] >= arr[flag]) { 
    					right--;
    				}
    				
    				//当队尾元素 < 基准元素，进行交换
    				//调转扫描顺序
    				if (arr[right] < arr[flag]) { 
    					
    					var temp = arr[right];
    					arr[right] = arr[flag];
    					arr[flag] = temp;
    					
    					flag = right;
    				}
    				
    				//当队首元素 <= 基准元素，向后挪动left
    				while (left < right && arr[left] <= arr[flag]) { 
    					left++;
    				}
    				
    				//当队首元素 > 基准元素，进行交换
    				//调转扫描顺序
    				if(arr[left] > arr[flag]) { 
    					
    					var temp = arr[left];
    					arr[left] = arr[flag];
    					arr[flag] = temp;
    					
    					flag = left;
    				}
    			}
    			
    			//进行迭代对index之前和之后的数组进行相同的操作是整个数组变得有序
    			quicksort(arr, start, left - 1);
    			quicksort(arr, left + 1, end);
    			
    			return arr;
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("quicksort").innerHTML = quicksort(arr);	
    	</script>
    </html>

### 7.堆排序（Heap Sort） ###

利用堆设计的一种排序算法。子节点的键值总是大于（小于）它的父节点。

#### 7.1算法描述 ####

*  将初始无序列表构建成大根堆，即父节点总是大于它的子节点；
 *  将堆顶元素与最后的元素进行交换；
 *  对交换后的堆进行调整成为新的大根堆；再进行上一步操作；
 *  直到所有的元素排序完毕。

#### 7.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="heapsort"></p>
    	</body>
    	<script>
    		var leng;	//多个函数都会用到
    		function heapsort(arr){ 
    			var leng = arr.length;
    			for (var i = Math.floor(leng / 2); i >= 0; i--){ 	//非叶子节点个数
    				heapify(arr,i);
    			}
    			return arr;
    		}
    		
    		function heapify(arr,i){ 
    			var left = 2 * i + 1;
    			var right = 2 * i + 2;
    			var largest = i;
    			
    			if (left < leng && arr[left] > arr[largest]){ 
    				largest = left;
    			}
    			
    			if (right < leng && arr[right] > arr[largest]){ 
    				largest = right;
    			}
    			
    			if(largest != i){ 
    				var temp = arr[i];
    				arr[i] = arr[largest];
    				arr[largest] = temp;
    				heapify(arr,largest);
    			}
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("heapsort").innerHTML = heapsort(arr);	
    	</script>
    </html>

### 8.计数排序（Counting Sort） ###

输入的数据值转化为键存储在额外开辟的数据空间中。作为一种线性实践复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

#### 8.1算法描述 ####

*  找出待排序的数组中的最大元素和最小元素，建立区间为最小元素到最大元素之间的额外空间；
 *  统计数组中每个值为i的元素出现的次数，存入额外空间；
 *  反向填充数组，将每个元素i放在新数组中，每放一个计数就减去1。

#### 8.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="countsort"></p>
    	</body>
    	<script>
    		function countsort(arr){ 
    			var len = arr.length;
    			var min = arr[0], max = arr[0];
    			
    			for (var i = 1; i < len; i++){ 
    			
    				if (arr[i] < min){ 
    					min = arr[i];
    				}
    				if (arr[i] > max){ 
    					max = arr[i];
    				}
    			}
    			
    			var bucketlen = max - min + 1;
    			var bucket = [];
    			var count = new Array(bucketlen);
    			
    			for (var i = 0; i < bucketlen; i++){ 
    				count[i] = 0;
    			}
    			var index = 0;
    			
    			for (var i = 0; i < len; i++){ 
    				count[arr[i] - min]++;
    			}
    			
    			for (var i = 0; i < bucketlen; i++){ 
    				while (count[i]--){ 
    					bucket[index] = i + min;
    					index++;
    				}
    			}
    			return bucket;
    		}
    		var arr = [1,8,9,2,2,2,3,1,1,1,5,6,8,9,5];
    		document.getElementById("countsort").innerHTML = countsort(arr);	
    	</script>
    </html>

### 9.桶排序（Bucket Sort） ###

桶排序是计数排序的升级版。利用了函数映射的关系，高效的关键就在于映射函数的确定。  
假设输入数据服从均匀分布，将数据分到有限数量的桶中，每个桶内在进行排序（可能会使用到别的排序方法，或者使用递归）。

#### 9.1算法描述 ####

*  设置定量的数组作为空桶；
 *  便利输入数据，把数据通过区间比较（比如23，放在代号为2的桶，52放在代号为5的桶）；
 *  对每个不是空桶的桶进行排序；
 *  将排好序的非空桶的数据拼合。

#### 9.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="bucketsort"></p>
    	</body>
    	<script>
    		function bucketsort(arr,bucsize){ 
    			if (arr.length === 0){ 
    				return arr;
    			}
    			
    			var min = arr[0];
    			var max = arr[0];
    			
    			for (var i = 1; i < arr.length; i++){ 
    				if (arr[i] < min){ 
    					min = arr[i];
    				}else if (arr[i] > max){ 
    					max =  arr[i];
    				}
    			}
    			
    			// 初始化桶
    			var default_buck_size = 5;	//桶的容量
    			bucsize = bucsize || default_buck_size;
    			var buccount = Math.floor((max - min) / bucsize) + 1;	//桶的数量
    			var buckets = new Array(buccount);
    			for (var i = 0; i < buckets.length; i++){ 
    				buckets[i] = [];
    			}
    			
    			// 利用映射函数将数据分配到各个桶中
    			for (var i = 0; i < arr.length; i++){ 
    				buckets[Math.floor((arr[i] - min) / bucsize)].push(arr[i]);	//将对应的数值装入对应的桶中
    			}
    			
    			arr.length = 0;
    			for (var i = 0; i < buckets.length; i++){ 
    				insertsort(buckets[i]);	//对每个桶中已有的数值进行排序，插入排序请参见上面的代码
    				for (var j = 0; j < buckets[i].length; j++){ 
    					arr.push(buckets[i][j]);
    				}
    			}
    			return arr;
    		}
    		var arr = [1,8,9,2,2,2,3,1,1,1,5,6,8,9,5];
    		document.getElementById("bucketsort").innerHTML = bucketsort(arr);	
    	</script>
    </html>

### 10.基数排序（Radix Sort） ###

基数排序按照低位优先排序，然后收集；然后高位排序，然后再收集；依此类推，直至最高位排序完毕。

#### 10.1算法描述 ####

*  取得数组中的最大数值，确定最大位数；
 *  从最低位开始取每个位组成radix数组；
 *  对radix进行基数排序。

#### 10.2代码实现 ####

<html>
    	<meta charset="utf-8">
    	<head>
    		<title>Sort</title>
    	</head>
    	<body>
    		<p id="radixsort"></p>
    	</body>
    	<script>
    		function radixsort(arr){ 
    			var mod = 10;
    			var dev = 1;
    			var max = arr[0];
    			var maxdigit = 0;	//最大数值的位数
    			
    			for (var i = 1; i < arr.length; i++){ 
    				if (arr[i] > max){ 
    					max = arr[i];
    				}
    			}
    			while (max){ 
    				max = parseInt(max / 10);
    				maxdigit++;
    			}
    			var count = [];
    			for (var i = 0; i < maxdigit; i++, dev *= 10, mod *= 10){ 
    				for (var j = 0; j < arr.length; j++){ 
    					var bucket = parseInt((arr[j] % mod) / dev);	//尾数
    					if (count[bucket] == null){ 
    						count[bucket] = [];
    					}
    					count[bucket].push(arr[j]);
    				}
    				
    				var pos = 0;
    				for (var j = 0; j < count.length; j++){ 
    					var value = null;
    					if (count[j] != null){ 
    						while((value = count[j].shift()) != null){ 
    							arr[pos++] = value;
    						}
    					}
    				}
    			}
    			return arr;
    		}
    		var arr = [20,2,5,9,62,52,33,7,41,22,8];
    		document.getElementById("radixsort").innerHTML = radixsort(arr);	
    	</script>
    </html>

> **如果发现哪里有错误还请多多指正，路漫漫其修远兮，我们一起加油呀！**

> 文章参考：https://www.cnblogs.com/onepixel/articles/7674659.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RhbmdnZ0ppZWVl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7d7355a6e68c4ec693c792697a75432e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RhbmdnZ0ppZWVl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ee0c3c68934246c088fd015b6144d4aa.png