几种算法
2017-03-30 本文已影响0人
_july77
代码虽源自抄袭，自己重写时改了一下变量名，消化更好了_
冒泡排序（Bubble Sort）
1. 算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越
2. 动图演示
3. JavaScript 代码实现
function sort(arr){
var len=arr.length;
for(var i=0;i<len;i++){
for(var j=0;j<len-1-i;j++){
if(arr[j]>arr[j+1]){
var temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
console.log(sort([2,53,1,16,26]));
选择排序（selectionSort）
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
1. 算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
- 重复第二步，直到所有元素均排序完毕
2. 动图演示
function sort(arr){
var len=arr.length;
var minId,temp;
for(var i=0;i<len-1;i++){
minId=i;
for(var j=i+1;j<len;j++){
if(arr[j]<arr[minId]){
minId=j;
}
}
temp=arr[i];
arr[i]=arr[minId];
arr[minId]=temp;
}
return arr;
}
console.log(sort([2,5,3,1,4]));
插入排序
1. 算法步骤
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2. 动图演示
3. JavaScript 代码实现
function sort(arr){
var len=arr.length;
var sortedId,sortingValue;
for(var i=1;i<len;i++){
sortedId=i-1;
sortingValue=arr[i];
while(sortedId>=0 && arr[sortedId]>sortingValue){
arr[sortedId+1]=arr[sortedId];//排序好的依次往后顺移
sortedId=sortedId-1;//
}
arr[sortedId+1]=sortingValue;//最后把在排序的值赋给已排好的顺下一位
}
return arr;
}
console.log(sort([2,10,3,1,4]));
归并排序（Merge sort）
1. 算法步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤 3 直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
2. 动图演示
3. JavaScript 代码实现
function sort(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(sort(left),sort(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;
}
console.log(sort([2,5,4,9,10,8,1]))
快速排序
1. 算法步骤
- 从数列中挑出一个元素，称为 “基准”（pivot）
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
- 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
2. 动图演示
3. JavaScript 代码实现
<!---表示还没弄很懂，乱啊乱--->
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 = paritition2(arr, low, high);
quickSort2(arr, low, pivot - 1);
quickSort2(arr, pivot + 1, high);
}
return arr;
}
console.log(quickSort([5,4,2,1,3,99]));
借来同学一个快速排序，很简洁
快速排序又称为自私算法，它优先让每个元素找到自己所在的位置，每次排序都实现“比我大的都在我右边，比我小的都在我左边”而不去计较它们的位置关系。具体做法为：先找一个基准点（一般用第一个元素或者中间元素）然后数组被分为两部分，如果选定值比它小，放左边；比它大，放右边。然后进行反复比较，就可以实现效果。
function sort(array){
if(array.length<=1){
return array;
}
var len = Math.floor(array.length/2);
var cur = array.splice(len,1);
var left = [];
var right = [];
for(var i=0;i<array.length;i++){
if(cur>array[i]){
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return sort(left).concat(cur,sort(right));
}
