JavaScript实现的六种排序算法总结

资源摘要信息:"排序算法总结——javascript实现" 在编程世界中，排序算法是基础且重要的算法之一，它广泛应用于各种场景中，例如数据处理、资源分配、搜索算法优化等。JavaScript作为一种广泛使用的编程语言，其内置的`sort`方法为开发者提供了便捷的数组排序功能。然而，对于算法的深入理解与灵活运用，掌握多种排序算法的实现原理和特点则是非常必要的。本文将对常见的排序算法进行总结，并以JavaScript语言为例，展示各种排序算法的实现方式。 ### 冒泡排序——bubbling 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端，就像水中的气泡一样升到水面上。 ```javascript function bubbling(arr) { for (let i = 0; i < arr.length - 1; i++) { for (let j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } return arr; } ``` ### 插入排序——insertSort 插入排序的工作方式像许多人在玩扑克牌时整理手上的牌，我们从数组的第二个元素开始，把当前元素插入到已排序好的数组中的适当位置，然后继续处理下一个元素，直到整个数组排序完成。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 ```javascript function insertSort(arr) { for (let i = 1; i < arr.length; i++) { let key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr; } ``` ### 选择排序——selectSort 选择排序算法是一种原址比较排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。这种方法在未排序序列中找到最小（大）元素，然后放到排序序列的起始位置。 ```javascript function selectSort(arr) { for (let i = 0; i < arr.length; i++) { let minIndex = i; for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } let temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } return arr; } ``` ### 快速排序——quickSort 快速排序使用分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：选择一个基准元素，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 ```javascript function quickSort(arr, left, right) { if (left < right) { let pivot = arr[left]; // 基准值 let i = left; let j = right; while (i < j) { // 从右向左找小于基准值的数 while (arr[j] >= pivot && i < j) { j--; } // 从左向右找大于基准值的数 while (arr[i] <= pivot && i < j) { i++; } // 交换两个数在数组中的位置 if (i < j) { let t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } // 将基准值放到正确的位置（排好序的数组中间位置） arr[left] = arr[i]; arr[i] = pivot; // 对基准值左右两边的数组进行快速排序 quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); } return arr; } ``` ### 希尔排序——shellSort 希尔排序是插入排序的一种更高效的改进版本。它先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。该方法因D.L.Shell于1959年提出而得名。希尔排序是一种基于插入排序的快速的排序算法。 ```javascript function shellSort(arr) { for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) { for (let i = gap; i < arr.length; i++) { let temp = arr[i]; let j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } return arr; } ``` ### 归并排序——mergeSort 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 ```javascript function mergeSort(arr) { if (arr.length > 1) { let mid = Math.floor(arr.length / 2); let left = arr.slice(0, mid); let right = arr.slice(mid); mergeSort(left); mergeSort(right); let i = 0; let j = 0; let k = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) { arr[k++] = left[i++]; } else { arr[k++] = right[j++]; } } while (i < left.length) { arr[k++] = left[i++]; } while (j < right.length) { arr[k++] = right[j++]; } } return arr; } ``` 排序算法在实际应用中，选择合适的算法非常关键，它们在不同的场景下表现出来的效率各不相同。理解各种排序算法的原理和优缺点对于开发中选择合适的工具来解决问题至关重要。在某些特定的需求下，例如内存受限或数据量极小，选择基础的排序算法就能达到良好的性能。而在面对大数据量时，快速排序、归并排序这样的更高效算法更能发挥作用。此外，JavaScript本身提供的`Array.prototype.sort`方法性能也非常优秀，对于大部分应用场景而言，可以直接使用而无需自行实现排序算法。但在学习和研究算法时，手动实现这些排序算法对提升算法理解能力大有裨益。