JS实现各种排序算法 #63

Seasons123 · 2017-07-27T07:26:57Z

<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title></title>
</head>
<body>
	<script>
		var arr1 = [10, 8, 1, 4, 9, 2, -1, -2, 0];	
		var arr2 = [10, 8, 1, 4, 9, 2, -1, -2, 0];	
		var arr3 = [10, 8, 1, 4, 9, 2, -1, -2, 0];	
		var arr4 = [10, 8, 1, 4, 9, 2, -1, -2, 0];	
		var arr5 = [10, 8, 1, 4, 9, 2, -1, -2, 0];	
		var arr6 = [10, 8, 1, 4, 9, 2, -1, -2, 0];	
		var arr7 = [10, 8, 1, 4, 9, 2, -1, -2, 0];	
		/*
		 * 冒泡排序
		 * 时间复杂度n的平方
		 *
		 */
		function bubbleSort(arr) {
                      var i,j,exchange=1;
                      var n=arr.length;
                      for(i = 0;i < n-1 && exchange;i++) {
                             exchange=0;
                             for(j=n-2; j>=i ;j--){
                                        if(arr[j]>arr[j+1]){
                                                    var temp=arr[j+1];
                                                    arr[j+1]=arr[j];
                                                    arr[j]=temp;
                                                    exchange=1;
                             }
                       }
                       if(exchange==0){
                                 break;
                       }
            }
            return arr;
        }
		/*
		 * 选择排序
		 * 时间复杂度n的平方
		 *
		 */
		function selectSort(arr) {
			for(var i = 0;i < arr.length - 1;i++) {
				var minIndex = i;
				for(var j = i;j < arr.length;j++) {
					if(arr[minIndex] > arr[j]) {
						minIndex = j;
					}
				}
				if(minIndex != i) {
					var temp = arr[i];
					arr[i] = arr[minIndex];
					arr[minIndex] = temp;
				}
			    }
			       return arr;
		       }
		/*
		 * 插入排序
		 * 构造有序区与无序区
		 * 左边是有序区
		 * 右边是无序区
		 * 接下来几步:
		 * 1. 保存要被插入的数
		 * 2. 保存有序区的最大的数的下标
		 * 3. 开始移动
		 * 4. 插入
		 *
		 */
		function insertSort(arr) {
			for(var i = 1;i < arr.length;i++) {
				if(arr[i - 1] > arr[i]) {
					var guard = arr[i];
					var j = i - 1;
					while(j >= 0 && arr[j] > guard) {
						arr[j + 1] = arr[j];
						j--;
					}
					arr[j + 1] = guard;
				}
			}
			return arr;
		}
		/*
		 * 快速排序
		 * 快速排序的思想是分治法
                 “快速排序”的思想很简单，整个排序过程只需要三步：
　              （1）首先选一个轴值（即比较的基准）
　　            （2）通过一趟排序将待排序的记录分割成独立的两部分，前一部分的关键码均小于
                      或等于轴值，后一部分的关键码均大于或等于轴值。轴值元素则排在这两部分中间。
                      实际实现是：建立两个数组，分别存储左边和右边的数组
　              （3）利用递归，分别对这两部分重复上述方法。
		 *
		 */
		function quickSort(arr) {
			if(arr.length <= 1) {
				return arr;   //如果数组只有一个数，就直接返回；
			}
			var pivotIndex = Math.floor(arr.length / 2); //选取轴值位置：找到中间
//数的索引值，如果是浮点数，则向下取整
			var pivot = arr.splice(pivotIndex, 1)[0];//找到中间数的值
			var leftArr = [];
			var rightArr = [];
			for(var i = 0;i < arr.length;i++) {
				if(arr[i] > pivot) {
					rightArr.push(arr[i]); //基准点的右边的数传到右边数组
				} else {
					leftArr.push(arr[i]); //基准点的左边的数传到左边数组
				}
			}
                        //递归
			return quickSort(leftArr).concat(pivot,quickSort(rightArr));
		}
			
		console.log("冒泡排序:" + bubbleSort(arr1));
		console.log("选择排序:" + selectSort(arr2));
		console.log("插入排序:" + insertSort(arr3));
               alert(quickSort([32,45,37,16,2,87]));//弹出“2,16,32,37,45,87”
	</script>
</body>
</html>

The text was updated successfully, but these errors were encountered:

Seasons123 · 2017-08-01T03:19:37Z

Math.floor() : 取小于等于指定值的最大整数例 Math.floor(4.5) ; //4

Seasons123 mentioned this issue Jul 10, 2018

《Object-Oriented JavaScript》—— 4.2.2 Array #11

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

JS实现各种排序算法 #63

JS实现各种排序算法 #63

Seasons123 commented Jul 27, 2017 •

edited

Loading

Seasons123 commented Aug 1, 2017

JS实现各种排序算法 #63

JS实现各种排序算法 #63

Comments

Seasons123 commented Jul 27, 2017 • edited Loading

Seasons123 commented Aug 1, 2017

Seasons123 commented Jul 27, 2017 •

edited

Loading