vlambda博客
学习文章列表

1.冒泡排序（Bubble Sort）

    冒泡排序是一种简单的排序方法，其核心思想就是交换，所以属于交换排序，数据大的记录下沉，小的记录上移，所以这种算法叫做冒泡排序算法。通过重复执行若干冒泡排序算法，终可以得到一个顺序的排序序列，它重复地遍历要排列的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说数列已经排序完成。

排序思路：

1.相邻元素之间的比较，如果第一个元素比第二个元素大，则他们两个进行交换。（若第一个元素小于第二个元素，则不交换位置，第二个和第三个进行比较）

2.对每一对的元素进行同样的工作，直到最后一对元素。则最后一个元素是最大的元素。（所以在下一轮比较时，除了最后一个元素重复以上的步骤）

3. 重复以上的步骤直到没有任何一对数字需要比较则结束。

Python代码举例：

2. 快速排序（Quick Sort）

快速排序：以左边第一个元素作为轴，l,r分别指向最左最右元素。当l小于r时不断循环【右边的元素大于轴时，r往左移，反之，把右边的该元素放到l位置，然后比较左边的元素；左边的元素小于轴的元素时，l往右移，反之，把左边的元素，给到r位置；】当l等于r的时候，轴的位置确定了，然后递归处理轴左边的数列和右边的数列。

算法步骤

a. 选择第一个元素作为轴

b. l<r< span="">时，r的值大于等于轴时，r- -;

    l<r< span="">时 and r的值小于轴时，交换两者的值

    l<r< span="">时，l的值小于等于轴时，l++;

    l<r< span="">时 and r的值大于轴时，交换两者的值

<r时 and="" r的值大于轴时，交换两者的值<="" p="">

c. l==r时：轴的值唯一确定

d. l>r时，直接return

e. 递归轴左边和右边的序列

python代码举例（将无序数列变有序）

插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

    从第二个元素开始和前面的元素进行比较，如果前面的元素比当前元素大，则将前面元素 后移，当前元素依次往前，直到找到比它小或等于它的元素插入在其后面然后选择第三个元素，重复上述操作，进行插入依次选择到最后一个元素，插入后即完成所有排序。

Python代码举例

易忘点和易错点

a. 不要忘记列表长度为1的情况。

b. 注意break的使用以及位置，是放在if语句下面，如果放到第二层for循环下，就会一直循环。

4. 希尔排序（Shell Sort）

    希尔排序是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，基本思想是把记录按下标的一定增量分组，对每组使用直接插入排序算法程序；随着增量的逐渐减少，每组包括的关键词越来越多，当增量减少至1时，整个文件恰好被分成一组，算法便终止，希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本,该方法的基本思想是：先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况)，效率是很高的，因此希尔排序在时间效率比直接插入排序有较大提高。

Python代码举例

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

5. 简单选择排序（Select Sort ）

简单选择排序算法:选择排序的思路是固定位置，选择排序，

即：先从序列中，找到最小的元素，放到第一个位置，

然后找到第二小的元素，放到第二个位置，以此类推，直到排好所有的值。

算法：

对于一组关键字{K1,K2,…,Kn}， 首先从K1,K2,…,Kn中选择最小值，假如它是 Kz，则将Kz与 K1对换；

然后从K2，K3，… ，Kn中选择最小值 Kz，再将Kz与K2对换。

如此进行选择和调换n-2趟，第(n-1)趟，从Kn-1、Kn中选择最小值 Kz将Kz与Kn-1对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成。

Python 代码举例

排序算法的稳定性是针对所有记录而言的，在所有的待排序的记录中，只要有一组关键字的实例不满足稳定性要求，则该排序就是不稳定的。虽然稳定的排序方法排序结果不同，但不能说不稳定的方法就是不好，各有各的适用场所。

到这里小编的故事就讲完了，如果觉得好的话就多多支持小编。