排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、计数排序、桶排序。
冒泡排序
冒泡排序是一种比较简单的排序算法,它循环走过需要排序的元素,依次比较相邻的两个元素,如果顺序错误就交换,直至没有元素交换,完成排序。
若对n个人进行排序,我们需要n-1次比较,所以第k次比较需要进行n-k次比较。排序算法通过以数据对象的两两比较作为关键,可以得出冒泡排序需要进行的比较次数为:(n-1) + (n-2) + ... + 1 = n*(n-1) / 2,因此冒泡排序的时间复杂度为O(n^2)。
动画演示:
![](https://img.haomeiwen.com/i15401334/a1c80eaa3d7caac5.gif)
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { //相邻元素两两对比
let temp = arr[j + 1] //元素交换
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
let arr = [5, 2, 1, 3, 6, 10, 8, 4, 7]
console.log(bubbleSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 10 ]
选择排序
选择排序是一种简单直观的排序算法,工作原理为:在未排序的序列中找出最小(大)元素与第一个位置的元素交换位置。
选择排序每遍历一次都记住了当前最小(大)元素的位置,最后仅需一次交换操作即可将其放到合适的位置。然后在剩下的元素中再找最小(大)元素与第二个元素的位置交换,依此类推,直到所有元素排序排序完成。根据上述描述,一共进行n-1趟比较后,就能完成整个排队过程。我们可以知道,第k趟比较需要进行的数组元素的两两比较的次数为n-k次,所以共需要的比较次数为n*(n-1) / 2,因此选择排序算法的时间复杂度与冒泡排序一样,也为O(n^2)。
动画演示:
![](https://img.haomeiwen.com/i15401334/092b6058fef4b1cb.gif)
function selectionSort(arr) {
let len = arr.length;
let minIndex, temp;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //寻找最小的数
minIndex = j; //将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
let arr = [5, 2, 1, 3, 6, 10, 8, 4, 7]
console.log(selectionSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 10 ]
插入排序
插入排序是一种简单直观的排序算法,工作原理为构建有序序列,对于未排序元素,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间,直到排序完成,如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。理解了插入排序的思想后,我们便能够得到它的时间复杂度。对于n个元素,一共需要进行n-1轮比较,而第k轮比较需要进行k次数组元素的两两比较,因此共需要进行的比较次数为:1 + 2 + ... + (n-1),所以插入排序的时间复杂度同冒泡排序一样,也为O(n^2)。
动画演示:
![](https://img.haomeiwen.com/i15401334/c85634fbc2d38dbe.gif)
function insertionSort(arr) {
let len = arr.length;
let preIndex, current;
for (let 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;
}
let arr = [5, 2, 1, 3, 6, 10, 8, 4, 7]
console.log(insertionSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 10 ]
希尔排序
1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
按增量序列个数 k,对序列进行 k 趟排序;每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
动画演示:
![](https://img.haomeiwen.com/i15401334/78e5e645929f1391.gif)
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap = gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
let arr = [5, 2, 1, 3, 9,6, 10, 8, 4, 7]
console.log(shellSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
归并排序
![](https://img.haomeiwen.com/i15401334/f9c0e974d82531c3.gif)
function mergeSort(arr) { //采用自上而下的递归方法
let len = arr.length;
if(len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length > 0 && right.length > 0) {
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;
}
let arr = [5, 2, 1, 3, 9,6, 10, 8, 4, 7]
console.log(mergeSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
快速排序
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
具体算法描述如下:从数列中挑出一个元素,称为 “基准”(pivot);重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
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;
}
let arr = [5, 2, 1, 3, 9,6, 10, 8, 4, 7]
console.log(quickSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
简单版:
function quickSort(arr){
//如果数组 <=1, 则直接返回
if(arr.length <= 1){return arr}
//找基准
let pivotIndex = Math.floor(arr.length / 2)
// 把基准从原数组删除
let pivot = arr.splice(pivotIndex, 1)[0]
//定义左右数组
let left = []
let right = []
//比基准小的放在left,比基准大的放在right
for(let i = 0; i < arr.length; i++){
if(arr[i] <= pivot){
left.push(arr[i])
}
else{
right.push(arr[i])
}
}
//递归
return quickSort(left).concat([pivot],quickSort(right))
}
let arr = [5, 2, 1, 3, 9,6, 10, 8, 4, 7]
console.log(quickSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
堆排序
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
![](https://img.haomeiwen.com/i15401334/176660d3cb954958.gif)
var len; // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
let arr = [5, 2, 1, 3, 9,6, 10, 8, 4, 7]
console.log(heapSort(arr)) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
各排序算法比较
![](https://img.haomeiwen.com/i15401334/6d78b1838e4b2a33.png)
网友评论