面试准备-排序

面试准备-排序

插入排序

最简单的排序算法，由N-1趟排序组成，根据已知事实：0~p-1的元素已经按序排列（p当前第几趟）

E.G.原始数组34/8/64/51/32/21

a.(34)插入8得（8/34）

b.(8/34)插入64得（8/34/64）...

算法复杂度O（N二次方）-插入n-1次，每次插入都会导致数组移动

希尔排序，别称缩减增量排序

增量序列：h1, h2, h3 (如1， 3， 5)

a. 5排序：把间隔5的元素排序

X 1 X X X X 3 X X X X 2 X X X X 调整为 X 1 X X X X 2 X X X X 3 X X X X

b. 进行3排序和1排序

算法复杂度最坏情况O（N二次方）

堆排序，基于优先队列思想，一种树形选择排序

a.先构造最大堆(反之最小堆亦然)，首先产生完全二叉树，从最后一个非叶节点主机调整产生最大堆

每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)

b.再不断deleteMax ，拿掉堆顶，逐级调整

c.直至仅剩最后一个元素

算法复杂度O（NlogN）

选择排序，每次选择一个当前最小值

将初始序列(A[0]~A[n-1])作为待排序序列，第一趟在待排序序列(A[0]~A[n-1])中找到最小值元素，将其与第一个元素A[0]交换，这样子序列(A[0])已经有序，下一趟在排序在待排序子序列(A[1]~A[n-1])中进行。第i趟排序在待排序子序列(A[i-1]~A[n-1])中找到最小值元素，与该子序列中第一个元素A[i-1]交换。经过 n-1 趟排序后使得初始序列有序。

冒泡排序

第一趟在序列(A[0]~A[n-1])中从前往后进行两个相邻元素的比较，若后者小，则交换，比较 n-1 次；第一趟排序结束，最大元素被交换到A[n-1]中下一趟排序只需要在子序列(A[0]~A[n-2])中进行；冒泡排序最多进行 n-1 趟。

基本的冒泡排序可以利用旗标的方式稍微减少一些比较的时间，当寻访完序列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的比较与交换动作。

快速排序

算法复杂度O（NlogN）-平均运行时间，O（N二次方）-最坏的情况

通过一趟排序将要排序的数据分割成独立的两部分（枢纽元），其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行

如何选取枢纽元？

错误：选择第一个元素

安全：随机选取

三数中值分割法：使用左端，右端，中心位置的三个元素的中值作为枢纽元

分割策略？

1. 将枢纽元和最后的元素交换使得枢纽元离开被分割的数据段