1.直接插入排序
原理:
将待排序的一个元素插入到已排好序的数组中,插入过程的原理是:记录下待插入的元素的值,然后在已排好序的数组中,从后往前,将比这个数字大的元素往后移一个位置,依次循环,最终,空出来一个位置,就是待插入元素该放的位置
javascript算法实现
function InsertSort(arr) {
for (var i = 1; i < arr.length; i++) {
var x = arr[i]
var j = i - 1;
while(arr[j] > x && j > -1){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = x;
}
console.log(arr);
}
算法分析
插入排序是稳定的(如何遇见相同的值,这个值是不会往前移动一位的)
插入排序的事件复杂度是O(n*n)
2.简单选择排序
原理:
从整个数组中遍历一遍,选择其中最小的一个值。然后,将这个值放在第一个位置上,第二次遍历,从待排序的数组中选择最小的一个放在第二个位置上,依次循环n-1次,最终得到排好序的数组
javascript算法实现
// 选择排序
function select(arr){
for (var i = 0;i < arr.length-1;i++) {
var min = arr[i];
var minIndex = i;
var temp;
for (var j = i + 1;j < arr.length;j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
console.log(arr);
}
算法分析
通常该算法被认为是不稳定的,但是可以改进使之变成稳定的,
同时,也可以经过改进,使得其时间复杂度降低
上述算法的事件复杂度是O(n*n)
3.冒泡排序
原理:
在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
javascript算法实现
// 冒泡排序
function mao(arr){
var temp;
for (var i = arr.length - 1; i > 0; i--) {
for (var j = 0; j < i; j++){
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
console.log(arr);
}
算法分析
冒泡排序是稳定的
冒泡排序的时间复杂度是O(n*n)
大神写的总结链接:http://blog.csdn.net/hguisu/article/details/7776068
网友评论