一 常见排序算法
将无序的序列调整为有序序列,
1 时间复杂度O(n2)
冒泡排序,选择排序,插入排序,希尔排序,
1.冒泡排序(bubble sort):比较相邻两个元素的大小,前一个比后一个大,则交换元素,
1 | '''冒泡排序''' |
1 | class Solution { |
2.选择排序(selection sort):每次假定一个数最小,然后,再找一个最小的,如果有,就交换。
1.先在未排序序列中找到最小元素,放到数组第一个位置,从剩余未序列序列中找最小元素,然后放到已排序序列的末尾。
1 | '''选择排序''' |
1 | class Solution { |
3.插入排序(insertion sort): 将数组分为两个部分,前面是有序部分,后面是无序部分,每次从无序部分从前往后拿一个数,在有序部分从后向前比较,找到位置插入。
在前面已排序数组找到插入位置。
1 | def insert_sort(nums): |
2 时间复杂度O(nlogn)
1.快速排序(quick_sort):使用分治的思想,把一个序列分成较小和较大两个序列。
挑选左边第一个元素为基准,进行分割,所有比基准小的放在基准前面,反之放基准后面,对基准的排序完成;递归的将小于基准的子序列和大于基准的子序列分别排序,同样的方法;递归结束的边界条件是序列的大小是1或0(显然已有序)。
1 | def quick_sort(nums): # 快排python |
1 | class Solution { //快排C++ |
小结:
冒泡,选择,插入,都有两个for循环,所以时间复杂度为O(n2),
快排因为有一个for循环,所以有n,再每次循环有一次减半,log,故为nlogn