- 什么是算法
- 输入：一个算法必须有零个或以上输入量
- 输出：一个算法应有一个或以上输出量
- 明确性：算法的描述必须无歧义，实际运行结果是确定的
- 有限性：必须在有限个步骤内结束
- 有效性：又称可行性，能够被执行者实现
- 十种常见排序算法可以分为两大类：
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
算法分类.png
-
算法复杂度
算法复杂度.png
- 遇到思路障碍怎么办
- 抽象的问题转化为具体的问题
- 没见过的问题转化为见过的问题
冒泡排序：高的往后排
- 比较相邻的两个元素，第一个比第二个大，则交换两个
- 对每一对相邻元素做同样工作，这样最大值被固定到最后
- 重头开始新一轮的比较，得到新的最大值，这样得到倒数第二位
-
以此类推
冒泡排序.gif
function swap(array,a,b){
var temp
temp = array[a]
array[a] = array[b]
array[b] = temp
}
function sort(array){
var i,j
for(i = 0;i<array.length;i++){
//排了第i次
for(j=0;j<array.length-1-i;j++){
if(array[j] <= array[j+1]){
}else{
swap(array,j,j+1)
}
}
}
return array
}
console.log(sort([3,5,6,2,5,2,4]))
每次最高的排最后
选择排序：每次选择最小的，最小的往前站
- 在序列中找到最小元素(大)，存放在序列的起始位置
- 未排序的序列中继续找最小元素，然后放序列中的第二行
-
以此类推
选择排序.gif
function swap(array,a,b){
var temp
temp = array[a]
array[a] = array[b]
array[b] = temp
}
function sort(array){
var i,j,indexMin
for(i=0;i<array.length;i++){
indexMin = i
for(j=i+1;j<array.length;j++){
//找到最小值，将j的值赋给indexMin
if(array[j] < array[indexMin]){
indexMin = j
}
}
swap(array,i,indexMin)
}
return array
}
console.log(sort([3,5,6,2,5,2,4]))
插入排序：扑克牌算法
- 起一张牌，第二张牌要是小的话放前面
-
第三张牌比较有序区的元素，比较后插入到合适的位置，以此类推
插入排序.gif
归并排序：领导算法 最底层
快速排序：自私算法：前面比我矮。后面比我高
- 1.取出一个元素为基准
- 2.对数列进行以此比较排序，比基准小的放基准前面，大的放基准后面，此操作结束后，基准位于数列中间
-
3.然后分别对基准两边的区，进行以上操作
快速排序.gif
var times=0;
var quickSort=function(arr){
//如果数组长度小于等于1无需判断直接返回即可
if(arr.length<=1){
return arr;
}
var midIndex=Math.floor(arr.length/2);//取基准点
var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1]
var left=[];//存放比基准点小的数组
var right=[];//存放比基准点大的数组
//遍历数组，进行判断分配
for(var i=0;i<arr.length;i++){
if(arr[i]<midIndexVal){
left.push(arr[i]);//比基准点小的放在左边数组
}
else{
right.push(arr[i]);//比基准点大的放在右边数组
}
console.log("第"+(++times)+"次排序后："+arr);
}
//递归执行以上操作,对左右两个数组进行操作，直到数组长度为<=1；
return quickSort(left).concat(midIndexVal,quickSort(right));//连接数组
};
console.log(quickSort(arr));
随机快速排序法:比快排效率高一些
桶排序
桶排序的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶分别排序
缺点：占内存
基数排序：
先从低位排序，然后收集，再慢慢高位排序，以此类推
基数排序.gif
// LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
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;
}
}
}
}
return arr;
}
