从学习数据结构开始就接触各种算法基础，但是自从应付完考试之后就再也没有练习过，当在开发的时候也是什么时候使用什么时候去查一下，现在在学习JavaScript，趁这个时间再把各种基础算法整理一遍，分别以JS和PHP语法的方式编写代码。
1.冒泡排序
原理：临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束
时间复杂度：平均情况：O（n2） 最好情况：O（n） 最坏情况：O（n2）
空间复杂度：O（1）
稳定性：稳定
//JavaScript语法 var array = [23,0,32,45,56,75,43,0,34]; for(var i = 0; i < array.length; i++) { var isSort = true; for(var j = 0; j < array.length - 1 - i; j++) { if(array[j] > array[j+1]) { isSort = false; var temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } if(isSort) { break; } } console.log(array);
<?php $array = [23,0,32,45,56,75,43,0,34]; for($i = 0; $i < count($array); $i++) { $isSort = true; for($j = 0; $j < count($array) - 1; $j++) { if($array[$j] > $array[$j+1]) { $isSort = false; $temp = $array[$j]; $array[$j] = $array[$j + 1]; $array[$j + 1] = $temp; } } if($isSort) { break; } } var_dump($array); ?>
2.简单选择排序
原理：通过n-i次关键字之间的比较,从n-i+1 个记录中选择关键字最小的记录,并和第i(1<=i<=n)个记录交换 简单选择排序的性能要略优于冒泡排序
时间复杂度:平均情况：O（n2） 最好情况：O（n） 最坏情况：O（n2）
空间复杂度：O（1）
稳定性：不稳定
//JavaScript var array = [23,0,32,45,56,75,43,0,34]; for(var i = 0; i < array.length - 1; i++) { var pos = i; for(var j = i + 1; j < array.length;j++) { if(array[j] < array[pos]) { pos=j; } } var temp=array[i]; array[i]=array[pos]; array[pos]=temp; } console.log(array);
<?php $array = [23,0,32,45,56,75,43,0,34]; for($i = 0; $i < count($array); $i++) { $pos = $i; for($j = $i + 1;$j < count($array); $j++) { if($array[$j] < $array[$pos]) { $pos = $j; } } $temp = $array[$i]; $array[$i] = $array[$pos]; $array[$pos] = $temp; } var_dump($array); ?>
3.直接插入排序
原理：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 比冒泡法和选择排序的性能要更好一些
时间复杂度：平均情况：O（n2） 最好情况：O（n） 最坏情况：O（n2）
空间复杂度：O（1）
稳定性：稳定
//JavaScript var array = [23,0,32,45,56,75,43,0,34]; for(var j = 0;j < array.length;j++) { var key = array[j]; var i = j - 1; while (i > -1 && array[i] > key) { array[i + 1] = array[i]; i = i - 1; } array[i + 1] = key; } console.log(array);
<?php //直接插入排序 $array = [23,0,32,45,56,75,43,0,34]; for($i = 0; $i < count($array); $i++) { $key = $array[$i]; $j= $i - 1; while($j > -1 && $array[$j] > $key) { $array[$j +1] = $array[$j]; $j = $j - 1; } $array[$j + 1] = $key; } var_dump($array); ?>
4.快速排序
原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度:平均情况：O（nlog2n） 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：O（nlog2n）
稳定性：不稳定
//JavaScript 快速排序 var array = [23,0,32,45,56,75,43,0,34]; var quickSort = function(arr) { if (arr.length <= 1) { return arr; }//检查数组的元素个数，如果小于等于1，就返回。 var pivotIndex = Math.floor(arr.length / 2);// var pivot = arr.splice(pivotIndex,1)[0];//选择"基准"（pivot），并将其与原数组分离， 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 newArray=quickSort(array); console.log(newArray);