学习JavaScript算法之常用的排序算法讲解
学习常用的排序算法
一、冒泡排序
优点:
所有排序中最简单的,易于理解;
缺点:
时间复杂度o(n^2),平均来说是最差的一种排序方式;
因为在默认情况下,对于已经排好序的部分,此排序任然会进行比较(当然可以进行改进优化)
算法步骤:
比较相邻的元素,如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对一直到结尾的最后一对,如此将最大的数放在后面。
对所有的元素重复以上的步骤,除了最后一个。
持续每次对元素重复上面的步骤,直到排序完成。
原理分析:
通过比较两个相邻的项,(由大到小排序)如果第一个比的二个大,则交换它们的位置元素项向上移动至正确的顺序,就好像气泡升至表面,冒泡也因此得名。
const bubblesort = (arr) => { const length= arr.length; for (let i = 0; i arr[j+1]){ let swap = arr[j]; arr[j] = arr[j+1]; arr[j+1] = swap; } } } }
改进优化:
默认上述代码,对于第一轮之后的循环任然会进行和全部元素的比较,但其实之前的循环已经将器排序正确了,所以可以从内循环中减去外循环已经进行过的轮数,从而避免不必要的比较
const bubblesort = (arr) => { const length= arr.length; for (let i = 0; i arr[j+1]){ let swap = arr[j]; arr[j] = arr[j+1]; arr[j+1] = swap; } } } }
二、选择排序
原理:
进行原地址比较,找到数据结构中最小值并放在第一位,接着在剩下的中找到第二个最小值放在第二位,依次类推;
代码实现:
function selectionsort(arr) { var length= arr.length; var minindex; for (var i = 0; i < length - 1; i++) { minindex = i; for (var j = i + 1; j < length; j++) { if (arr[j] < arr[minindex]) { // 寻找最小的数 minindex = j; // 将最小数的索引保存 } } if(i != minindex){ var temp = arr[i]; arr[i] = arr[minindex]; arr[minindex] = temp; } } return arr; }
三、插入排序
原理:
通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
排序步骤:
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
代码实现
function insertionsort(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) { arr[preindex+1] = arr[preindex]; preindex--; } arr[preindex+1] = current; } return arr; }
原理图
四、归并排序
原理:
归并是一种分治算法,即将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,每次归并时进行排序,直到最后只有一个排序完毕的大数组。
代码实现(递归):
function mergesort(arr) { // 采用自上而下的递归方法,数组拆分 var len = arr.length; if(len < 2) { return arr; } var middle = math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergesort(left), mergesort(right)); } //合并数组,并进行排序 function merge(left, right) { var result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; }
原理图
五、快速排序
原理:
快速排序使用分治法(divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
排序步骤:
首先,从数组中选择中间一项作基数;
然后,创建两个指针,左边一个指向数组的第一项,右边一个指向数组的最后一项;
移动左指针直到找到一个比基数大的元素,移动右指针,直到找到一个比基数小的元素;然后交换它们;
重复以上步骤,直到左指针超过了右指针;(这个过程将使得比基数小的树都在基数的前面,较大的数都在基数的后面)
最后,对划分后的小数组(比基数小的值组成的子数组,以及比基数大的值组成是子数组)重复之前的两个步骤,直到数组已经完全排序。
代码实现
function quicksort(arr, left, right) { var len = arr.length, partitionindex, left = typeof left != 'number' ? 0 : left, right = typeof right != 'number' ? len - 1 : right; if (left < right) { partitionindex = partition(arr, left, right); quicksort(arr, left, partitionindex-1); quicksort(arr, partitionindex+1, right); } return arr; } function partition(arr, left ,right) { // 分区操作 var pivot = left, // 设定基准值(pivot) index = pivot + 1; for (var i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index-1; } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function partition2(arr, low, high) { let pivot = arr[low]; while (low < high) { while (low < high && arr[high] > pivot) { --high; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { ++low; } arr[high] = arr[low]; } arr[low] = pivot; return low; } function quicksort2(arr, low, high) { if (low < high) { let pivot = partition2(arr, low, high); quicksort2(arr, low, pivot - 1); quicksort2(arr, pivot + 1, high); } return arr; }
原理图