一、冒泡排序
(1)算法描述和实现
1、比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3、针对所有的元素重复以上的步骤，除了最后一个；
4、重复步骤1~3，直到排序完成。
动图演示：http://img.blog.csdn.net/20160916160748389
(2)算法分析
最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
(3)JavaScript代码实现：
functionbubbleSort(arr) {
varlen = arr.length;
for(vari =0; i < len; i++) {
for(varj =0; j < len -1- i; j++) {
if(arr[j] > arr[j+1]) {//相邻元素两两对比
vartemp = arr[j+1];//元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
returnarr;
}
vararr=[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]
二、选择排序
(1)算法描述和实现
首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，
然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，直到排序完毕。
动图演示：http://img.blog.csdn.net/20160916164754013
(2)算法分析
最佳情况：T(n) = O(n2)
最差情况：T(n) = O(n2)
(3)JavaScript代码实现：
functionselectionSort(arr){
varlen = arr.length;
varminIndex,temp;
for(vari =0; i < len -1; i ++){
minIndex = i;
for(varj = i +1; j < len; j ++){
if(arr[j] < arr[minIndex]){//寻找最小的数
minIndex = j;//将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
returnarr;
}
vararr = [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]
三、插入排序
(1)算法描述和实现
将n个元素的数列分为已有序和无序两个部分。
数列：{a1，a2，a3，a4，…，an}
将该数列的第一元素视为有序数列，后面都视为无序数列：
{{a1}，{a2，a3，a4，…，an}}
将无序数列中的元素插入到有序数列的对应位置，插入前通过比大小的方式找到其在有序数列中的对应位置。
1、从第一个元素开始，该元素可以认为已经被排序；
2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5、将新元素插入到该位置后；
6、重复步骤2~5。
动图演示：http://img.blog.csdn.net/20160916173802597
(2)算法分析
最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
(3)JavaScript代码实现：
functioninsertionSort(array) {
//假设第0个元素是一个有序的数列，第1个以后的是无序的序列，
//所以从第1个元素开始将无序数列的元素插入到有序数列中
for(vari =1; i < array.length; i++) {
//取出无序数列中的第i个作为被插入元素
varkey = array[i];
//记住有序数列的最后一个位置
varj = i -1;
//比大小，找到被插入元素所在的位置
while(j >=0&& array[j] > key) {
array[j +1] = array[j];
j--;
}
//插入
array[j +1] = key;
}
returnarray;
}
四、快速排序
(1)算法描述和实现
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
1、从数列中挑出一个元素，称为“基准”（pivot）；
2、所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3、对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
(2)算法分析
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(n2)
(3)JavaScript代码实现：
functionquickSort(arr) {
if(arr.length <=1) {returnarr; }
varpivotIndex = Math.floor(arr.length /2);
varpivot = arr.splice(pivotIndex,1)[0];
varleft = [];
varright = [];
for(vari =0; i < arr.length; i ++){
if(arr[i] < pivot) {
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
returnquickSort(left).concat([pivot], quickSort(right));
};
vararr=[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]
五、归并排序
(1)算法描述和实现
归并排序：其基本思想是分治策略，先进行划分，然后再进行合并。
假设要对数组C进行归并排序，步骤是：
1.先将C划分为两个数组A和B（即把数组C从中间分开）
2.再分别对数组A、B重复步骤1的操作，逐步划分，直到不能再划分为止(每个子数组只剩下一个元素)，这样，划分的过程就结束了。
如：[12 20 30 21 15 33 26 19 40 25]
划分为: [12 20 30 21 15]
[33 26 19 40 25]
[12 20] [30 21 15] [33 26]
[19 40 25]
[12] [20] [30] [21 15] [33] [26]
[19] [40 25]
[12] [20] [30] [21] [15] [33] [26]
[19] [40] [25]
3.然后从下层往上层不断合并数组，每一层合并相邻的两个子数组，合并的过程是每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，不断重复直到把两个子数组的元素都放到合并后的数组为止。
4.依次类推，直到合并到最上层结束，这时数据的排序已经完成了。
[if !vml]
[endif]
[if !vml]
[endif]
动图演示：http://img.blog.csdn.net/20160917001326254
(2)算法分析
最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
(2)JavaScript代码实现：
functionmergeSort(arr){//采用自上而下的递归方法
varlen = arr.length;
if(len <2){
returnarr;
}
varmiddle = Math.floor(len /2),
left = arr.slice(0,middle),//得到下标从0~index-1的数组
right = arr.slice(middle);//得到下标从index开始到末尾的数组
returnmerge(mergeSort(left),mergeSort(right));//里面采用递归
}
functionmerge(left,right){//每次left或者right都是要shift掉第一个元素，最后arr.concat，因为不知道left或者right其中一个哪个剩下元素，所以要将剩下的元素给加上
varresult = [];
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());
returnresult;
}
vararr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
网友评论