排序算法的python实现

本文用python实现常用的排序算法，按时间复杂度分为：

1. 时间复杂度为O(n^2)：冒泡排序，选择排序，插入排序。
2. 时间复杂度为O(nlogn)：快速排序，归并排序，堆排序。
3. 时间复杂度为O(n)：计数排序，桶排序，基数排序

1. 时间复杂度为O(n^2)的排序算法

1.1 冒泡排序

基本思想：从左到右遍历数组，比较相邻两个数字的大小，如果前者比后者大，则交换他们的位置（从小到大排列）。一次遍历，使得最大值到最右端。重复n次遍历，则数据为从小到大排列。

在这里插入图片描述

1.2插入排序

基本思想：从列表中选择一个元素，与左边的元素进行比较，找到合适的位置插入，保持左边的元素有序。

插入排序

1.3 选择排序

基本思想：遍历待排序的列表中选择出小的元素，并将它与第一个元素互换，然后从第二元素开始再选择最小的元素，与第二个元素互换，以此类推，直到列表有序。（从大到小排则选择最大的元素放在最前面）。

选择排序

2. 时间复杂度为O(nlogn)的排序算法

2.1 快速排序

在冒泡排序中，每轮循环只能确定一个元素的位置，所以，需要n轮循环才能确定所有元素的位置。而快速排序的思想是：选定一个基准元素，通过一次循环将数组分成两部分，左边比基准元素小，右边比基准元素大（或者相等）。这样一次循环确定了n个元素的相对位置。对左右边的数组迭代进行刚才的操作（分治的思想）。最后组合在一起，就成了有序数组。

快速排序

利用双边循环：