十大排序算法

栏目: 编程工具 · 发布时间: 6年前

排序算法对比

十大 <a href='https://www.codercto.com/topics/21904.html'>排序</a> 算法

n : 数据规模 

k :“桶”的个数 

In-place : 占用常数内存，不占用额外内存 

Out-place : 占用额外内存

1.冒泡排序（Bubble Sort）

动图演示

十大排序算法

JavaScript 代码 

function bubbleSort(arr){
	var low = 0;
	var high = arr.length - 1;
	while(low < high){
		for(j = low; j < high; ++j){
			//正向冒泡,找到最大者
			if(arr[j] > arr[j+1]){
				[arr[j],arr[j+1]] = [arr[j+1],arr[j]];
			}
		}
		--high;
		for(j = high; j > low; --j){
			//反向冒泡,找到最小者
			if(arr[j] < arr[j - 1]){
				[arr[j],arr[j-1]] = [arr[j-1],arr[j]];
			}
		}
		++low;
	}
	return arr;
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));
//  [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

2.选择排序（Selection Sort）

动图演示

十大排序算法

JavaScript 代码 

function selectionSort(arr){
	var len = arr.length;
	var midIndex;
	for(var i = 0; i < len - 1; i++){
		midIndex = i;
		for(var j = i + 1;j < len; j++){
			if(arr[j] < arr[midIndex]){
				midIndex = j;
			}
		}
		[arr[i],arr[midIndex]] = [arr[midIndex],arr[i]];
	}
	return arr;
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));
//  [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

3.插入排序（Insertion Sort)

动图演示

十大排序算法

JavaScript 代码 

function binaryInsertSort(array){
	for(var i = 1; i < array.length; i++){
		var key = array[i],
			left = 0,
			right = i-1;
		while(left <= right){
			var middle = parseInt((left + right) / 2);
			if(key < array[middle]){
				right = middle - 1;
			}else{
				left = middle + 1;
			}
		}
		for(var j = i-1; j >= left; j--){
			array[j+1] = array[j];
		}
		array[left] = key;
	}
	return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binaryInsertSort(arr));
//  [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

4.希尔排序（Shell Sort）

图示

十大排序算法

JavaScript 代码 

function shellSort(arr){
	var len = arr.length,
		temp,
		gap =1;
	while(gap < len/5){
		gap = gap*5 + 1;
	}
	for(gap; gap > 0; gap = Math.floor(gap/5)){
		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;
}
var arr = [9,1,2,5,7,4,8,6,3,5];
console.log(shellSort(arr));
// [1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
复制代码

5.归并排序（Merge Sort）

动图演示

十大排序算法

JavaScript 代码 

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;
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

6.快速排序(Quick Sort)

动图演示

十大排序算法

JavaScript 代码 

function quickSort(arr){
	if(arr.length<=1){
		return arr;
	}
	var pivotIndex = Math.floor(arr.length/2);
	var pivot = arr.splice(pivotIndex,1)[0];
	var left = [];
	var right = [];
	for(var 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));
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]复制代码

7.堆排序（Heap Sort）

动图演示

十大排序算法

JavaScript 代码 

var 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; // i 为该子树的根节点
	if(left < len && arr[left] > arr[largest]){
		largest = left;
	}
	if(right < len && arr[right] > arr[largest]){
		largest = right;
	}
	if(largest != i){  // 即上面的 if 语句有一个执行了
		[arr[i],arr[largest]] = [arr[largest],arr[i]];  // 交换最大的为父节点
		heapify(arr,largest);  // 作为根时，子节点可能比他大，因此要继续调整
	}
}
function heapSort(arr){
	buildMaxHeap(arr);
	for(var i = len - 1; i > 0 ; i--){
		[arr[0],arr[i]] = [arr[i],arr[0]];
		len--;
		heapify(arr,0);
	}
	return arr;
}
var arr=[91,50,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr,4)); // [10, 13, 20, 22, 30, 31, 35, 46, 50, 65, 65, 77, 81, 91, 96]
复制代码

8.计数排序 (Counting Sort)

动图演示

十大排序算法

JavaScript 代码 

function countingSort(array){
	var index = 0, tempArr = [];
	console.time('计数排序耗时：');
	for(var i = 0; i < array.length; i++){
		tempArr[array[i]] = tempArr[array[i]] ? tempArr[array[i]] + 1 : 1 ;
	}
	for(var j = 0;j <= tempArr.length;j++){
		while(tempArr[j]>0){
			array[index++] = j;
			tempArr[j]--;
		}
	}
	console.timeEnd('计数排序耗时：');
	return array;
}
var arr=[7,12,12,12,56,23,19,33,35,42,2,8,22,39,26,17];
console.log(countingSort(arr,4)); 
// [2, 7, 8, 12, 12, 12, 17, 19, 22, 23, 26, 33, 35, 39, 42, 56]
复制代码

9.桶排序（Bucket Sort）

动图演示

十大排序算法

JavaScript 代码 

/*
    桶排序：
    array : 待排序数组
    bucketSize : 桶的数目
*/
function bucketSort(array, bucketSize) {
    if (array.length <= 1) {
        return array;
    }
    var buckets = [], result = [], min = max = array[0], space, n = 0;
    bucketSize = bucketSize || 5;
    console.time('桶排序耗时');
    for (var i = 1; i < arr.length; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
    }
    space = (max - min + 1) / bucketSize;
    for (var j = 0; j < array.length; j++) {
        var index = Math.floor((array[j] - min) / space);
        if (buckets[index]) {   
            //  非空桶，进行插入排序
            var k = buckets[index].length - 1;
            while (k >= 0 && buckets[index][k] > array[j]) {
                buckets[index][k + 1] = buckets[index][k];
                k--;
            }
            buckets[index][k + 1] = array[j];
        } else {
            // 空桶，初始化
            buckets[index] = [];
            buckets[index].push(array[j]);
        }
    }
    while (n < bucketSize) {
        result = result.concat(buckets[n]);
        n++;
    }
    console.timeEnd('桶排序耗时');
    return result;
}
var arr=[7,12,56,23,19,33,35,42,2,8,22,39,26,17];
console.log(bucketSort(arr,4)); // [2, 7, 8, 12, 17, 19, 22, 23, 26, 33, 35, 39, 42, 56]
复制代码

10.基数排序（Radix Sort）

  • MSD 从高位开始进行排序
  • LSD 从低位开始进行排序

LSD 基数排序 动图

十大排序算法

  • 最佳情况：T(n) = O(n * k)
  • 最差情况：T(n) = O(n * k)
  • 平均情况：T(n) = O(n * k)

说明：n 为数组长度 ； k 为数组中最大数的位数。

JavaScript 代码 

/*
	基数排序：
	arr ： 待排序数组
	maxDigit : 数组中的最大数的位数
*/
function radixSort(arr,maxDigit){
	var mod = 10;
	var dev = 1;
	var counter = [];
	console.time('基数排序耗时：');
	for(var i = 0; i < maxDigit; i++ ,dev *= 10,mod *= 10){
		for(var j = 0;j < arr.length; j++){
			var bucket = parseInt((arr[j]%mod)/dev);
			if(counter[bucket] == null){
				counter[bucket] =[];
			}
			counter[bucket].push(arr[j]);
		}
		var pos = 0;
		for(var j = 0;j < counter.length; j++){
			var value = null;
			if(counter[j]!=null){
				while((value = counter[j].shift()) != null){
					arr[pos++] = value;
				}
			}
		}
	}
	console.timeEnd('基数排序耗时：');
	return arr;
}
var arr =  [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(radixSort(arr,2));
//  [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
复制代码

图片和代码几乎全部来自网络，自己总结一下方便今后复习。


以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍
Python Algorithms

Python Algorithms

Magnus Lie Hetland / Apress / 2010-11-24 / USD 49.99

Python Algorithms explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python, this book is sharply focused on classical algorithms, but it......一起来看看 《Python Algorithms》 这本书的介绍吧!

码农工具
Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

  • New
  • 文章
  • 话题
  • 教程
    • 关注 码农网 公众号
    版权所有，保留一切权利！© 2018-2026 码农网 粤ICP备17054400号-3