由于最近要考试复习,所以学习 js 的时间少了 -_-||,考试完还会继续的努力学习,这次用原生的 JavaScript 实现以前学习的常用的排序算法,有冒泡排序、快速排序、直接插入排序、希尔排序、直接选择排序
交换排序是一类在排序过程中借助于交换操作来完成排序的方法,基本思想是两两比较排序记录的关键字,如果发现两个关键字逆序,则将两个记录位置互换,重复此过程,直到该排序列中所有关键字都有序为止,接下来介绍交换排序中常见的冒泡排序和快速排序
冒泡排序的名字由来是因为越大的元素会经由交换慢慢 "浮" 到数列的顶端,故名
冒泡排序算法的运作如下:(从后往前)
1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
冒泡排序的时间复杂度是 O(n^2)
代码:
- 1 // 冒泡排序
- 2
- function bubbleSort(arr) {
- 3 4
- for (var i = 0; i) {
- 5
- for (var j = 0; j) {
- 6
- if (arr[j] > arr[j + 1]) {
- 7
- var arrMax = arr[j + 1];
- 8 arr[j + 1] = arr[j];
- 9 arr[j] = arrMax;
- 10
- }
- 11
- }
- 12
- }
- 13 14
- return arr;
- 15
- }
- 1 // 快速排序
- 2
- function quickSort(arr) {
- 3 // 结束递归条件
- 4
- if (arr.length <= 1) {
- 5
- return arr;
- 6
- }
- 7 8
- var left = [];
- 9
- var right = [];
- 10
- var key = arr[0];
- 11 12 // 分组
- 13
- for (var i = 1; i) {
- 14
- if (arr[i] < key) {
- 15 left.push(arr[i]);
- 16
- } else {
- 17 right.push(arr[i]);
- 18
- }
- 19
- }
- 20 21 // 递归分组
- 22
- return quickSort(left).concat(key, quickSort(right));
- 23
- }
插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排序的序列中的适当位置,直到全部记录插入完成为止,接下来介绍两种常用的插入排序方法:直接插入排序和希尔排序
- 1 // 直接插入排序
- 2
- function insertSort(arr) {
- 3 // 默认第一个元素是有序的
- 4
- for (var i = 1; i) {
- 5 6
- if (arr[i] < arr[i - 1]) {
- 7
- var guard = arr[i];
- 8
- var j = i - 1;
- 9 // 将有序数组扩大一位
- 10 arr[i] = arr[j];
- 11 12 //遍历有序组,找到自己的位置
- 13
- while (j >= 0 && guard < arr[j]) {
- 14 arr[j + 1] = arr[j];
- 15 j--;
- 16
- }
- 17 18 // 插入检查的元素
- 19 arr[j + 1] = guard;
- 20
- }
- 21
- }
- 22
- return arr;
- 23
- }
希尔排序 (Shell Sort) 是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL.Shell 于 1959 年提出 而得名。
希尔排序属于插入类排序, 是将整个有序序列分割成若干小的子序列分别进行插入排序。 排序过程:先取一个正整数 d1<n,把所有序号相隔 d1 的数组元素放一组,组内进行直接插入排序;然后取 d2<d1,重复上述分组和排序操作;直至 di=1,即所有 记录放进一 个组中排序为止。 希尔排序的时间复杂度为时间复杂度 O(n*logn) 代码:
- 1 // 希尔排序
- 2
- function shellSort(arr) {
- 3
- var len = arr.length;
- 4
- var stepLen = 1;
- 5 // 确定首次遍历的步长
- 6
- while (stepLen < len / 3) {
- 7 stepLen = 3 * stepLen + 1;
- 8
- }
- 9 // 开始遍历
- 10
- while (stepLen >= 1) {
- 11
- for (var i = stepLen; i) {
- 12
- for (var j = i; j >= stepLen && arr[j] < arr[j - stepLen]; j -= stepLen) {
- 13 swap(arr, j, j - stepLen);
- 14
- }
- 15
- }
- 16 stepLen = (stepLen - 1) / 3;
- 17
- }
- 18 19
- return arr;
- 20
- }
- 21 22
- function swap(arr, i, j) {
- 23
- var temp = arr[j];
- 24 arr[j] = arr[i];
- 25 arr[i] = temp;
- 26
- }
选择排序的基本思想是:每一趟排序在 n-i+1 个带排序记录中选出关键字最小的记录,作为有序序列的第 i 个记录,直到全部记录排序完毕。常用的排序方法有直接选择排序和堆排序 (由于 js 不能很好的体现堆排序的特点就不写了)
基本思想是:第一次从 R[0]~R[n-1] 中选取最小值,与 R[0] 交换,第二次从 R[1]~R[n-1] 中选取最小值,与 R[1] 交换,....,第 i 次从 R[i-1]~R[n-1] 中选取最小值,与 R[i-1] 交换,.....,第 n-1 次从 R[n-2]~R[n-1] 中选取最小值,与 R[n-2] 交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列
直接选择排序的时间复杂度:O(n^2)
代码:
- 1 // 直接选择排序
- 2
- function straightSelectSort(arr) {
- 3 // 默认第一个元素是最小的
- 4
- var min;
- 5
- var k;
- 6
- var lArr = [];
- 7
- for (var i = 0; i) {
- 8 min = arr[i];
- 9 k = i;
- 10
- for (var j = i + 1; j) {
- 11
- if (arr[j] < min) {
- 12 min = arr[j];
- 13 k = j;
- 14
- }
- 15
- }
- 16
- if (k != i) {
- 17 arr[k] = arr[i];
- 18 arr[i] = min;
- 19
- }
- 20
- }
- 21
- return arr;
- 22
- }
来源: