|
大家好，我是IT修真院北京分院第32期学员，一枚正直善良的java程序员。
今天给大家分享一下，数据结构与算法基础中的排序算法：一、背景介绍 1.内排序 排序的分类内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。 内排序又有插入排序、选择排序、交换排序（冒泡排序、快速排序）、归并排序、基数排序
2.时间复杂度 以未知数n为基准来计算算法的规模，例如嵌套多个if循环的时候时间复杂度要取最里面的if循环消耗时间来计算
3.空间复杂度 空间复杂度即该算法需要为运算开辟新的空间来记录存储一些数据
如果有多次入栈操作那么取入栈最深的一次操作的存储空间作为空间复杂度
4.算法稳定性 这里举例说明比较方便，如果数组为{5，5，2}那么第一个5和第二个5在原数组中是有顺序的，如果排序永远不会交换二者位置那么为稳定排序
5.关于算法的时间复杂度的估计 有一些算法的时间复杂度是不固定的，因为有最好情况和最坏情况，我们可以根据数据推算
二、知识剖析与代码实现 1.冒泡排序（Bubble Sort） （1）算法流程 先对一个长度为N的数组从a[0]到a[N-1]遍历，每次都比较前后两个的大小，如果前者比后者大则两者交换顺序，再对a[0]到a[N-2]遍历，重复上述操作，直到对a[0]到a[1]遍历，一共N-1次遍历
（2）时间复杂度与空间复杂度 最好情况：正序排序，需要进行n-1次比较，时间复杂度为O(n)
最坏情况：倒序排序，需要进行n(n-1)/2次比较，时间复杂度为O(n^2)
平均时间复杂度为O(n^2)
空间复杂度为O(1)
（3）算法稳定性 冒泡排序是就地排序、是稳定的
（4）代码实现： 
2.选择排序（Selection Sort) （1）算法流程
指针指向a[0]，然后遍历数组比较，如果新的元素小于a[0]则将指针指向新的元素，继续遍历直到数组中最小元素取得指针，指针元素与a[0]交换，然后a[0]变为此数组最小元素，下次遍历从a[1]开始，重复上述步骤
（2）时间复杂度与空间复杂度 指针指向a[0]，然后遍历数组比较，如果新的元素小于a[0]则将指针指向新的元素，继续遍历直到数组中最小元素取得指针，指针元素与a[0]交换，然后a[0]变为此数组最小元素，下次遍历从a[1]开始，重复上述步骤 （3）算法稳定性 在数组情况下是非稳定排序，算法一书上也指出是非稳定排序，
eg.{1，1，0}进行选择排序，第一个1与0交换之后会直接变成第三位，改变了原来的相对顺序
（4）代码实现： 
3.插入排序（Insertion Sort） （1）算法流程
指针j从a[0]开始，一开始右侧元素完全未知，只需要将指针及其左侧元素排序即可，j+1，然后将j设置一个新的下标i，将i依次向左比较大小，如果小于则交换位置，不小于则break
（2）时间复杂度与空间复杂度 平均需要1/4 n^2的比较和1/4 n^2的交换，平均时间复杂度仍然为O(n^2)，>插入排序在数组部分有序的情况下比选择排序要快，空间复杂度为O(1) （3）算法稳定性 插入排序是稳定排序
（4）代码实现： 
4.快速排序(Quick Sort) (1)算法流程 指定一个数K，将K置为数组最左边，然后设置最右边的下标为J，最左边的下标为i，j--,i++,直到j的数小于K，i的数大于K，交换i、j指向的元素,交换之后继续上述步骤，直到i>=j，然后将K与J交换，这时在K的左边都是小于K的数，右边都是大于K的数,K位置已经确定，然后设置新的K为左边第一个数，进行上述步骤，直到完全排序，右边同理，递归过程
(2)时间复杂度与空间复杂度 平均时间复杂度为O(nlogn)，空间复杂度由递归过程产生，最优的情况为O(logn),最差情况为O(n)，大部分情况下比归并排序速度要快 (3)算法稳定性 快速是非稳定排序，不稳定排序发生在center元素交换的时刻 (4)代码实现： 
5.归并排序（Merge Sort) (1)算法流程
将数组分治处理，直到分成为单个数，然后做归并处理，分别对各个分治处理的块比较大小排序，最后归并完成
(2)时间复杂度与空间复杂度 对长度为n的数组需要进行二路归并，每次归并的时间为O(n),时间复杂度为O(nlgn)，需要开辟一个空间来存储归并结果，空间复杂度为O(n)
(3)算法稳定性 归并排序是稳定排序
(4)代码实现: 
6.基数排序（Counting Sort) (1)算法流程 创建一个0-9的空间来存放对应的数据，然后将数据从最高位数或者最低位数分类，在分类的同时实现排序 (2）时间复杂度与空间复杂度 时间复杂度为O(d(n+r)),O(n+r)
(3)算法稳定性 基数排序是稳定排序
三、编码实战 四、常见问题 算法的几大基本思想： 分治，动态规划，贪心，回溯，分支界限
五、参考文献 算法（第四版）
六、扩展思考 1.shell排序的h值如何选取？shell排序是否为稳定排序？ h值一般选为h=3*h+1，shell排序为非稳定排序，多次的插入排序导致其不稳定性 代码实现： 
2.如何做到完全随机的洗牌算法？ 代码实现如下： 
| 
转播
