人脑中【突触】越多，就越容易联想记忆，靠的是连接所有相关的东西。那么，排序就是连接【判断】【循环】【数组】等基本程序设计知识的一个东西。

 

约定：

要排序的是整数数组 （它只能是锻炼思维，实际开发 常用 BigDecimal 这类对象来排序，排序的目的显然是给展示用户所需要的数据样子。）

…………………………………………………………………………………………………………………………………………………………

【插入排序】

for(int i=1;i<list.length;i++){

//将 list[i] 插入 list[0...i-1]　(可移动，申请一个临时局部变量 currentElement)　

}

【冒泡排序】

for(int i=1;i<list.length;i++){

// 比较 和 交换

// * 第一次优化 第 i 次遍历 最后的（i - 1）个元素已经有序

// * 第二次优化 第 i 次遍历 发现没有发生交换 证明所有元素排序完毕 即不需要下次遍历

}

…………………………………………………………………………………………………………

【递归】归并排序和快速排序 基础

 

第1点 base 

 

第2点 exit

 

第3点 reduce

public static boolean isPalindrome(String s) {        if (s.length() <= 1) {            return true;        } else if (s.charAt(0) != s.charAt(s.length() - 1)) {            return false;        } else {            return isPalindrome(s.substring(1, s.length() - 1));        }    }

 

………………………………………………………………………………………………………………………………………………………………………………

【第一次优化】递归辅助方法 

优化点 每次都产生新串

 

private static boolean isPalindrome(String s,int low,int high) {        if (high < low) {            return true;        } else if (s.charAt(0) != s.charAt(s.length() - 1)) {            return false;        } else {            return isPalindrome(s,low+1,high-1);        }    }        public static boolean isPalindrome(String s) {        return isPalindrome(s,0,s.length()-1);    }

 

 

 

【第二次优化】尾递归，定义是递归调用后没有别的操作。

优化点 减轻方法开出来的栈负担。

……………………………………刚好第一次优化已经干掉了，说明使用递归辅助方法可以化解递归为尾递归（一般情况下。）

 

【归并排序】由于 TimSort(py2) 是插入排序和归并排序的合体，所以特别重要。

大概意思

public static void sort(int[] list){

    if(list.length > 1){    // base case ，当元素个数为1开始收敛 合并

　　　　// 拷贝一半到 第一部分

　　　　// 拷贝另一半到 第二部分

　　　 merge(firstHalf,secondHalf,list);//此时我们的 list（总空间） 可以由 firstHalf + secondHalf 来重新排序。

　　}

}

【快速排序】1962年 HOARE 老爷子发明。

核心思想  小数摆在一起 |pivot虚拟为中心| 较大的摆在一起 （pivot可以每次都选择第一个，但在每次摆好后要手动选择下一个主元元素） 

//STEP1 把列表分而治之，按照 Divide - （Conquer） - Combine 这个递归过程类似归并排序的处理方法。

function quickSort(list: number[], first: number, last: number): void {    if (first < last) {        let pivotIdx: number = partition(list, first, last);        quickSort(list, first, pivotIdx - 1);        quickSort(list, pivotIdx + 1, last);    }}//STEP2 核心算法 分区function partition(list: number[], first: number, last: number): number {    let pivot: number = list[first];    let low: number = first + 1;// pivot虚拟摆在中间并以它为中心    let high: number = last;    while (low < high) {        // 从 low=> 找比 pivot 小的        while (low <= high && list[low] <= pivot) {            low = low + 1;        }        // 从 high=> 找比 pivot 大的        while (low <= high && list[high] > pivot) {            high = high - 1;        }        if (low < high) {            let temp:number = list[low];            list[low] = list[high];            list[high] = temp;        }    }    // high => first 找到比主元大的    while(first
     
      =pivot){        high = high - 1;    }    // 选择下一个正确的主元     if(list[high]
     

 

…………………………………………………………………………………………………………………………………………………………………………