常见排序算法及复杂度数据结构与算法

冒泡排序两层循环
外层循环：遍历数组中待排序部分
内层循环：当前元素和它后面的元素比较大小，如果逆序就交换位置；下一个元素和它后面的元素比较大小，如果逆序就交换位置...直到结束
内层循环的排序过程，就是一个冒泡的过程，很形象，当内层排序结束后，最后一个元素就是已经排好序的元素，就像气泡冒出水面了。

数组：[5,1,3,4,2]外层遍历，遍历数组待排序部分：当前待排序部分是整个数组: [【5,1,3,4,2】] 内层遍历，当前元素和后面的元素比较大小，如果逆序就交换位置 [(5,1),3,4,2] => [(1,5),3,4,2] [1,(5,3),4,2] => [1,(3,5),4,2] [1,3,(5,4),2] => [1,3,(4,5),2] [1,3,4,(5,2)] => [1,3,4,(2,5)] 5已排好序，5之前的部分是待排序部分当前待排序部分: [【1,3,4,2】,/5/] 内层遍历，当前元素和后面的元素比较大小，如果逆序就交换位置 [(1,3),4,2,/5/] => [(1,3),4,2,/5/] [1,(3,4),2,/5/] => [1,(3,4),2,/5/] [1,3,(4,2),/5/] => [1,3,(2,4),/5/] 4已排好序，4之前的部分是待排序部分...以此类推

时间复杂度：
最坏情况：
冒泡排序一共要进行(n-1)次循环,每一次循环都要进行当前n-1次比较
所以一共的比较次数是: (n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2;
所以冒泡排序的时间复杂度是 O(n2)
最好情况：待排序数组本身就是正序的，一轮扫描即可完成排序，此时时间复杂度仅为比较时的时间复杂度，为O(n)
平均情况：O(n2)
空间复杂度：
就是在交换元素时那个临时变量所占的内存空间，最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为0，最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为O(n)，平均的空间复杂度为O(1)
快速排序快速排序有种二分法+双指针+递归的感觉
选择一个基准值，设置两个指针left和right，left负责小于基准值的部分，right负责大于基准值的部分，将数组分成小于该值、大于等于该值两部分
再将这两部分当成一个新的数组，重复上面的步骤
直到最终两部分只有1个元素为止
具体流程：

数组= [4,3,5,7,6,1,2,4]设置一个基准值，一般选择数组第一个元素即可基准值：4 设置两个指针，left在头，right在尾基准值：4 [4(l),3,5,7,6,1,2,4(r)] 因为left指向的元素就是基准值本身，所以我们先去比较right指向的元素 right也指向4，>=基准值，属于right的范围，不做改变，right向前移动基准值：4 [4(l),3,5,7,6,1,2(r),4] right指向2，<基准值，属于left的范围，将2赋值给left指针，left向后移动基准值：4 [2,3(l),5,7,6,1,2(r),4] left指向3，<基准值，属于left的范围，不做改变，left向后移动基准值：4 [2,3,5(l),7,6,1,2(r),4] left指向5，>=基准值，属于right的范围，将5赋值给right指针，right向前移动基准值：4 [2,3,5(l),7,6,1(r),5,4] right指向1，<基准值，属于left的范围，将1赋值给left指针，left向后移动基准值：4 [2,3,1,7(l),6,1(r),5,4] left指向7，>=基准值，属于right的范围，将7赋值给right指针，right向前移动基准值：4 [2,3,1,7(l),6(r),7,5,4] right指向6，>=基准值，属于right的范围，不做改变，right向前移动基准值：4 [2,3,1,7(l,r),6,7,5,4] 此时left和right相遇，将该值改为基准值基准值：4 [2,3,1,4(l,r),6,7,5,4] 此时指针的左半部分[2,3,1]都是小于基准值4的指针的右半部分[6,7,5,4]都是大于等于基准值4的这两个部分重新选额各自的基准值，重复上述快排步骤，直到递归结束最终就将整个数组完成排序

时间复杂度：

最好情况：O(nlogn)
最好情况时，每次基准值都在在数组中间并且刚好将数组平分，经过logn次划分，就分出了左右两部分
每一次划分，都涉及到n个元素
所以总共时间为O(n)*O(logn)=O(nlogn)
最坏情况：O(n^2)
最坏情况时，每次基准值都在数组开头，并且数组完全正序，那么就需要划分n次，才能分出左右两部分
每一次划分，都涉及到n个元素
所以总共时间为O(n)*O(n)=O(n^2)
平均：O(nlogn)

空间复杂度：
最优的情况下空间复杂度为：O(logn)；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n )；退化为冒泡排序的情况
选择排序将数组分为已排序部分和待排序部分
多次遍历数组的待排序部分
每次遍历，选出待排序部分的最小值，它和待排序部分的第一个元素交换位置，变成已排序部分

数组：[5,1,3,4,2]开始时，整个数组都是待排序部分 [【5,1,3,4,2】]待排序部分最小值为1，和待排序部分第一个元素5交换位置，1变成已排序 [1,【5,3,4,2】]待排序部分最小值为2，和待排序部分第一个元素5交换位置，2变成已排序 [1,2,【3,4,5】]待排序部分最小值为3，和待排序部分第一个元素3交换位置，3变成已排序 [1,2,3,【4,5】]待排序部分最小值为4，和待排序部分第一个元素4交换位置，4变成已排序 [1,2,3,4,【5】]此时待排序部分只有一个元素5，不需要排序了，就完成了全部排序 [1,2,3,4,5]

时间复杂度：O(n^2)
第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。
共比较的次数是 (N - 1) + (N - 2) + ... + 1，求等差数列和，得 (N - 1 + 1)* N / 2 = N^2 / 2。
舍去最高项系数，其时间复杂度为 O(N^2)。
插入排序将数组分为已排序部分和待排序部分
开始时将数组的第一个元素当作已排序部分
遍历待排序部分的每个元素，与已排序部分的元素比较，插入到已排序部分中的正确位置上

数组：[5,1,3,4,2]开始时，第一个元素5当作已排序部分，遍历待排序部分的元素 [/5/,(1),3,4,2]待排序的1，小于已排序的5，将1放在5前面 [/1,5/,(3),4,2]待排序的3，小于已排序的5，将3放在5前面 [/1,3,5/,(4),2] 待排序的3，大于已排序的1，将3放在1后面，即不改变位置 [/1,3,5/,(4),2]待排序的4，小于已排序的5，将4放在5前面 [/1,3,4,5/,(2)] 待排序的4，大于已排序的3，将4放在3后面，即不改变位置 [/1,3,4,5/,(2)]待排序的2，小于已排序的5，将2放在5前面 [/1,3,4,2,5/] 待排序的2，小于已排序的4，将2放在4前面 [/1,3,2,4,5/] 待排序的2，小于已排序的3，将2放在3前面 [/1,2,3,4,5/] 待排序的2，大于已排序的1，将2放在1后面，即不改变位置 [/1,2,3,4,5/]排序完毕

时间复杂度：

最好情况：[1,2,3,4,5]，遍历n-1次，移动0次，时间复杂度O(n)
最差情况：[5,4,3,2,1]，遍历n-1次，移动1+2+...+n-1次，时间复杂度O(n^2)
平均：O(N^2)

归并排序先将数组不断向下二分，一直分到子数组只有一个元素不可再分为止。
然后开始向上排序合并子数组，用两个指针指向两个子数组，比较指针位置元素的大小，较小的元素先添加到数组中，并且移动该指针继续比较。

数组：[8,4,5,7,1,3,6,2]先向下递归二分数组，直到子数组不可再分 [8,4,5,7][1,3,6,2] [8,4] [5,7][1,3] [6,2] [8][4][5][7][1][3][6][2]开始向上递归，通过两个指针比较元素大小，排序合并每层子数组 [8][4][5][7] [1][3][6][2] [4,8] [5,7][1,3] [2,6] [4,5,7,8][1,2,3,6] [1,2,3,4,5,6,7,8]指针排序过程: 例如 [4,8] [5,7]两个子序列开头设置指针 [4(i),8] [5(j),7]比较指针元素大小，较小的放入结果中，并向前移动该指针 [ ,8(i)] [5(j),7] res=[4]重复上述步骤 [ ,8(i)] [,7(j)] res=[4，5][ ,8(i)] [ , ] res=[4,5,7][ ,] [ , ] res=[4,5,7,8]

时间复杂度：O(nlogn)
一个长度为n的序列，它的排序时间就等于，它二分后的2个长度为n/2的子序列的排序时间，加上它们的合并时间。
假设长度为n的序列，排序时间为T(n)，那么长度为n/2的子序列，排序时间就为T(n/2)，两个n/2的子序列合并，需要操作n个元素，所以T(n)的合并时间为n
所以，T(n)=2*T(n/2)+n
【常见排序算法及复杂度】以此类推，
长度为n/2的子序列，它的排序时间T(n/2)=2*T(n/4)+n/2
长度为n/4的子序列，它的排序时间T(n/4)=2*T(n/8)+n/4
...
将T(n/4)带入到T(n/2)，再将T(n/2)带入到T(n)
得到每一层T(n)
T(n)=2*T(n/2)+n
T(n)=4*T(n/4)+2n
T(n)=8*T(n/8)+3n
...
最后一层的子序列长度为1，所以最后一层的排序时间是T(1)，用T(1)表示T(n)就是
logn表示：长度为n的数组，通过二分logn次，能达到不可分
T(n)=n*T(1)+(logn)*n
因为T(1)=0，所以T(n)=nlogn