冒泡排序(稳定)
特点:从后两两对比,更小的往前放.
时间复杂度:最坏情况O(n),最好情况O(n^2).
选择排序(不稳定)
特点:每次从待排序列中选出一个最小值,然后放在序列的起始位置,直至排完.
时间复杂度:O(n^2).
插入排序(稳定)
特点:从第下个元素开始,从已排序的元素序列从后往前扫描,如果该元素大于tem,则将该元素移至下一位.重复该步骤,直到找到已排序元素中小于等于tem的元素.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置.
一直重复上述步骤,直至排序完成.
时间复杂度:最坏情况O(n^2),最好情况O(n).
归并排序(稳定)
特点:采用分治算法.
- 分:将待排序的线性表不断地切分成若干个子表,直到每个子表只包含一个元素,这时,可以认为只包含一个元素的子表是有序表.
- 治:将子表两两合并,每合并一次,就会产生一个新的且更长的有序表,重复这一步骤,直到最后只剩下一个子表,这个子表就是排好序的线性表.
时间复杂度:O(nlogn).
快速排序(不稳定)
是对冒泡排序的一种改进
特点:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序流程:
- 首先设定一个分界值Key,通过该分界值将数组分成左右两部分.
- 将大于或等于Key的数据集中到数组右边,小于分界值的数据集中到数组的左边.此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值.
- 然后,左边和右边的数据可以独立排序.对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值.右侧的数组数据也可以做类似处理.
- 重复上述过程,可以看出,这是一个递归定义.通过递归将左侧部分排好序后,再递归排好右侧部分的顺序.当左右两个部分各数据排序完成后,整个数组的排序也就完成了.
