基础知识总结_高总的忘却日记

一些常见的问题，知道是知道，但是就怕忘，写个备忘录属于是。

一、十大排序算法及其优化

①冒泡排序：每趟决出一个最大值，来回交换到队尾。因此是稳定的，最坏时间复杂度就是全部交换过一次，O（n^2），那最好的情况肯定就是本身有序，一趟之后就结束，那么就是O（n）。没有使用额外内存空间，时间复杂度是O（1）。

优化：①：冒泡排序实际是比较慢的一种排序方式，因为不好的情况下每次都要遍历全体数据，但是有优化的一点在于，可以维护一个变量flag，当一趟冒泡之后如果发现flag没有改变，则表示排序结束，可以直接停止，因此在大致有序的条件下，冒泡排序的效率还可以。

②上述是从外层循环的角度考虑，接下来可以从内层循环的角度考虑一下，记录每一次冒泡的最后位置Location，那么在location后面的位置已经有序，每次的循环到这个最后一个位置即可。

②选择排序：最直观的一种排序算法，就是每一次选一个最小的（或者最大的）放在序列的首或者尾，注意这种情况是选定后交换，因此有可能导致排序不稳定。交换当前元素与至于怎么选，就是把当前元素存起来，然后比较，替换。因此这种方法的时间复杂度也是可以预见的高，达到了好坏都是O（n^2）。没有使用额外空间，空间复杂度O（1）。

优化：每次找到最小值的时候，同时维护一个最大值，然后把两者同时放到他们该放的位置，这样下次的循环区间就会变成[1:n-1]

③插入排序：从某一个元素开始，该元素被认为是有序的，然后取出下一个元素，在已有序的序列中从后向前扫描，如果已有元素大于新元素，则交换两个元素的位置，并一直循环这个过程直到找到位置。如果不是，则将新元素放在该元素之后。重复上述过程，直到最后一个元素，最坏情况，无序的时候是O(n^2),有序可以达到O（n），空间复杂度因为没有使用额外空间，因此也是O（1）。

优化：①停止搜索的时机，如果新元素已经找到存放位置，即可停止搜索。同时将搜索和移动合并，一边比较一边移动。

②交换代替后移，字面意思，减少操作次数。

④希尔排序：选择一个增量t1到tk,其中tk为1，每次选择每个增量内的元素进行插入排序，比如t1=5，择选下表0-5-10，1-6-11以此类推。最好最坏时间复杂度与直接插入相同，但是平均时间复杂度不太好计算，记一个结论吧。O（1.3）。其他的和直接插入基本类似，不稳定，没有使用额外空间。

优化：①提前停止。

②交换代替后移。

③每次可以先从GAP个元素开始，而无需从第一个元素开始，即先将第GAP个元素与第一个元素比较，再插入，能省掉一些时间。

⑤归并排序：采用分治的想法，首先将序列分为两个n/2的序列，再对每个序列再归并，直到元素被拆分完，然后再组合起来，需要使用额外空间，因此空间复杂度为O（n）,时间复杂度取决于分和治树的高度，为O（lgn），实际各lgn，为2lgn。当然也是稳定的，相同元素不会跑到前面。

⑥快速排序：需要先选定一个基准值，一般选取第一个，然后左右指针分别指向0和nums.length，然后从r指针开始遍历，找到比基准小的值即将该值存储到left指针所指向的位置，然后再从left指针的下一个位置开始遍历，找到比基准大的存储到右指针指向的位置，再从r指针的前一个位置开始遍历，直到l=r，不断重复上述过程。直到l再次等于r，此时所有基准都选择完毕。因为使用了递归的思想，时间复杂度方面就是递归树当中叶子节点的个数乘以举例，基本就是最好情况为O（nlgn），最差情况为O（n^2），最差情况下每次只能确定一个数字，退化为冒泡排序。

因为快排比较常用一些，因此贴一个快排的代码把：

import java.util.Arrays;

public class quicksort{
    public int partition(int[] arr,int left,int right){
        int base=arr[left];

        while(left<right){
            while(left<right&&arr[right]>=base){
                right--;
            }
            arr[left]=arr[right];
            while(left<right&&arr[left]<=base){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=base;
        return left;
    }
    public void Quicksort(int[] arr,int left,int right){
        if (left<right){
            int pos=partition(arr,left,right);
            Quicksort(arr,pos+1,right);
            Quicksort(arr,left,pos-1);
        }
    }
    public static void main(String[] args){
        quicksort sorter=new quicksort();
        int[] arr={7,9,8,2,3,4};
        sorter.Quicksort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}

优化：①三平均分区法：选择待排数组最左边，最右边和最中间三个元素的中间值作为基准，这是因为一般的排序是大致有序的。

②当分区规模小到一定程度的时候，整个序列已经大致有序，因此可以使用插入排序去处理剩下的序列。

③每次排序优先选择最小的子区间，这样能够更加有效的利用存储空间，加速算法的执行。

④快排的主要时间都浪费在了分区上，因此要保证分区尽可能的均匀，如果存在和base相同的部分值，那么会有很多无用的交换，因此可以开辟一块想等区域，三等分。

⑦堆排序：按照序列构建大顶堆，将堆顶元素与最后一个元素交换，然后调整堆，此时出现无序区与有序区，接着重复上述操作，直至全部有序。堆排序一直在原地操作，因此空间复杂度是O（1）。时间复杂主要是取决于建堆以及调整的过程，整个过程重复n次，每次lgn。非稳定。

⑧计数排序：非比较排序，先确定序列中最大最小值，然后遍历序列，将每一个元素出现的次数记录到额外空间当中，接着向原始数组写入，C[I]为几就填几个。时间复杂度主要体现在找最大和最小，因此为O(n+k),空间复杂度同理，主要体现在存储额外数字以及计数。是稳定算法。

⑨桶排序：首先设置一个定长的数组当空桶，遍历数据填入对应桶，这里有点像链表处理哈希冲突的过程，接着对每个不是空的通排序，最后从不是空的桶里把所有数拼起来，总体时间复杂度接近O（n）,但要额外空间O（n）。也是稳定的。

⑩基数排序：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。举个例子，比如{1，52，478，12，83，7，45，333}，会先从个位开始将个位数相同的数字放在一个桶里，位数不足用0补齐，然后对每个桶里进行计数排序。然后会将十位相同的数字放在桶里，一直到有序为止。空复杂度也均为O（n+k），时间复杂度为O（n*k）。稳定排序。

最后放一张图吧：

基础知识总结