js实现几大排序算法

深碍√TFBOYSˉ_ 2022-10-26 14:06 119阅读 0赞

### **一、冒泡排序：** ###

/* ----------- 冒泡排序（稳定排序）-----------
    平均时间复杂度：O(N^2)
    最佳时间复杂度：O(N)
    最差时间复杂度：O(N^2)
    空间复杂度：O(1)
        思路：每次循环比较相邻两个数的大小，如果小于就交换位置，
        所以每次循环结束会将最大值推向最右边
    注：因为每次最大数会依次被推向最边缘处，过程像水底的泡泡浮上水面一样，浮动的过程中慢慢变大，所以才称为冒泡排序，很形象
    */
    bubble_sort(list) {
    	for (let i = 0; i < list.length - 1; i++) { //外层总共只用循环n-1次,如果写i < list.length也没错
    		for (let j = 0; j < list.length - i - 1; j++) {
    			if (list[j] > list[j + 1]) {
    				let temp = list[j]
    				list[j] = list[j + 1]
    				list[j + 1] = temp
    			}
    		}
    	}
    	return list
    }

### **二、选择排序：** ###

/* ----------- 选择排序（不稳定排序）-----------
    平均时间复杂度：O(N^2)
    最佳时间复杂度：O(N^2)
    最差时间复杂度：O(N^2)
    空间复杂度：O(1)
        思路：每次循环找出数组中最大（最小值）放到数组最右边，
        每次循环只交换一次位置*/
    select_sort(list) {
    	for (let i = 0; i < list.length - 1; i++) { //外层总共只用循环n-1次,如果写i < list.length也没错
    		let max = list[0]
    		let p = 0
    		for (let j = 0; j < list.length - i; j++) {
    			if (max < list[j]) {
    				max = list[j]
    				p = j
    			}
    		}
    		let temp = list[p]
    		list[p] = list[list.length - 1 - i]
    		list[list.length - 1 - i] = temp
    	}
    	return list
    }

### **三、插入排序：** ###

/* ----------- 插入排序（稳定排序）-----------
    平均时间复杂度：O(N^2)
    最差时间复杂度：O(N^2)
    空间复杂度：O(1)
        --思路：从第二个数开始，拿出第二个数进行向前插入排序，
        前面的序列是已经有序的，每次拿出循环数插入到前面的有序序列中
        --具体插入操作：将循环数num与相邻的前面的数比较，如果num小于前面的数，
        则将前一个数往后移，若比前一个数大，则结束此次循环*/
    insert_sort(list) {
    	for (let i = 1; i < list.length; i++) { //注意是从第二个开始
    		let num = list[i]
    		let j = i - 1
    		for (; j >= 0; j--) {
    			//如果比较发现num比前面的值小，就将前面的值向右移动一位
    			if (num < list[j]) {
    				list[j + 1] = list[j]
    			} else {
    				break;
    			}
    		}
    		if (num != list[i]) {
    			list[j + 1] = num
    		}
    	}
    	return list
    }

### **四、快速排序：** ###

/* ----------- 快速排序（不稳定排序）-----------
          平均时间复杂度：O(NlogN)
          最佳时间复杂度：O(NlogN)
          最差时间复杂度：O(N^2)
          空间复杂度：根据实现方式的不同而不同
              思路：找一个基准点（一般为数组第一个数），将大于它的数都放到右边，小于它的数都放到它的左边，
              然后对left数组、right数组做同样的操作
    */
    quick_sort(list) {
    	if (list.length <= 1) return list;
    	/* 定义首、尾指针 */
    	let p_start = 0;
    	let p_end = list.length - 1;
    	/* 左右移动首尾指针，当两个指针碰到一起时结束循环 */
    	while (p_start != p_end) {
    		/* 始终先移动尾指针，判断尾部元素是否小于基准点（list[0]），
    		如果小于，就向右移动首指针，寻找大于基准点的元素，找到后交换两个元素位置，
    		之后继续移动尾指针，重复上面的操作 */
    		if (list[p_end] < list[0]) {
    			p_start++;
    			if (list[p_start] > list[0]) {
    				let temp = list[p_start];
    				list[p_start] = list[p_end];
    				list[p_end] = temp;
    			}
    		} else { /* 如果尾指针指向的元素大于基准点，就继续左移 */
    			p_end--;
    		}
    	}
    	/* 循环结束后再将基准点list[0]跟首尾指针指向的元素交换位置，
    	   这样得到的数组，基准点左边的都是小于它的数，右边都是大于它的数*/
    	let temp = list[0]
    	list[0] = list[p_end]
    	list[p_end] = temp
    	/* 将left数组、right数组递归做同样的操作 */
    	return [...quick_sort(list.slice(0, p_end)), list[p_end], ...quick_sort(list.slice(p_end + 1))]
    }

### **五、归并排序：** ###

/* 归并排序（稳定排序）
           平均时间复杂度：O(nlogn)
           最佳时间复杂度：O(n)
           最差时间复杂度：O(nlogn)
           空间复杂度：O(n)
                思路：基本思想是分治策略，先进行划分，然后再进行合并
    						通过迭代或递归，将数组逐步划分，直到不能再划分为止(每个子数组只剩下一个元素)。
    						然后再从下层往上层不断合并数组，每一层合并相邻的两个子数组，
    						合并的过程是从待合并的两个子数组中选取一个最小的元素，
    						然后把这个元素放到合并后的数组中*/
    //划分数组
    merge_sort(list) {
    	if (list.length < 2) return list
    	let left = list.slice(0, Math.floor(list.length / 2))
    	let right = list.slice(Math.floor(list.length / 2))
    	return merge(merge_sort(left), merge_sort(right))
    }
    // 排序并合并数组
    merge(left, right) {
    	let result = []
    	while (left.length && right.length) {
    		if (left[0] < right[0]) {
    			result.push(left.shift())
    		} else {
    			result.push(right.shift())
    		}
    	}
    	if (left.length)
    		return result.concat(left)
    	if (right.length)
    		return result.concat(right)
    }

过程如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmlfMTI1MTg2MTIwOQ_size_16_color_FFFFFF_t_70][]

动态演示：

![2021020216382758.gif][]

### **最后补充一个优劣对比：** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmlfMTI1MTg2MTIwOQ_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmlfMTI1MTg2MTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221024/96cba7460f4744f59696bb8ec64e9d13.png
[2021020216382758.gif]: /images/20221024/4f1125a092f84948af9d50ee345c7f4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmlfMTI1MTg2MTIwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221024/924c478a843d4e4184e4fe5259c7bf35.png