排序（排序大师）

1.冒泡排序

思路:

一个列表有n个数字就循环n-1次,循环一次就会将最大数字放到了最后(相邻数字进行比较,大的就放在右边,每次对比后数字大的都放右边,这样一行数字每两个相邻的数字都进行一次比较下来后,最大的数字就放到了最右边,

也就是本列表的-1索引位置,这样做n-1次,就把整个列表排序做好了,n是整个列表长度,因为最后一次就剩最左边一个元素了就不用再比较了.)

2.选择排序

思路:

先循环换找到最大的数字(并且获取到对应的索引),再将最后一个数字和最大数字交换位置,这样省去了每相邻两个数字做比较大小.

选择排序改进了冒泡排序，每次遍历列表只做一次交换。为了做到这一点，一个选择排序在他遍历时寻找最大的值，并在完成遍历后，将其放置在正确的位置。

如图:

3.插入排序

分析:

需要将原始的序列假装拆分成两部分

有序部分：默认为序列中的第一个元素

无序部分：默认为序列中除了第一个元素剩下的元素

关键：将无序部分的元素逐一插入到有序部分中即可

定义一个变量叫做i

i表示的是有序部分元素的个数

i还可以表示无序部分中第一个元素的下标

原始序列：[3,8,5,2,6,10,1]

[3,  8,5,2,6,10,1] ==》i=1

[3,8,  5,2,6,10,1] ==》i=2

思路:

插入排序的主要思想是每次取一个列表元素与列表中已经排序好的列表段进行比较，然后插入从而得到新的排序好的列表段，最终获得排序好的列表。比如，待排序列表为[49,38,65,97,76,13,27,49]，则比较的步骤和得到的新列表如下：(带有背景颜色的列表段是已经排序好的，红色背景标记的是执行插入并且进行过交换的元素）

4.快速排序

分析:

alist = [66,13,51,76,81,26,57,69,23]

基数：

默认情况下序列中第一个元素作为基数

原始序列中比基数大的值放置到基数右侧，比基数小的值放置到基数左侧

将列表中第一个元素设定为基准数字，赋值给mid变量，然后将整个列表中比基准小的数值放在基准的左侧，比基准大的数字放在基准右侧。然后将基准数字左右两侧的序列在根据此方法进行排放。

定义两个指针，low指向最左侧，high指向最右侧

然后对最右侧指针进行向左移动，移动法则是，如果指针指向的数值比基准小，则将指针指向的数字移动到基准数字原始的位置，否则继续移动指针。

如果最右侧指针指向的数值移动到基准位置时，开始移动最左侧指针，将其向右移动，如果该指针指向的数值大于基准则将该数值移动到最右侧指针指向的位置，然后停止移动。

如果左右侧指针重复则，将基准放入左右指针重复的位置，则基准左侧为比其小的数值，右侧为比其大的数值。

思路:

一排数字(这些数字最好不要随便拿因为有时候会出bug),快排是所有排序算法里面速度最快的.

一排数字,先取第一个数字作为基数,这样第一个位置就空了,然后定义两个变量low和high,low暂时定义为0,high暂时为列表的长度(其实low和high就是索引)

先从右边起,将high对应的数字与基数比大小,如果high比基数大,那么high对应的数字的位置就不动,将high重新赋值(向左挪一个数字),如果high比基数小,那么就将这个数字赋值给low,而这里的high对应的数字就算是空了,再往下,就从low这边开始算,刚赋值给了low一个数字(从右边第二个数字移动到了最左端第一个数字),现在再将low向右移动一个数字,将最左端第二个数字赋值给low,再把low和基数对比,如果low小于基数,就继续将low向左移动,如果low大于基数,就将low对应的数字移动到刚才high对应的数字的位置上去,移动之后,再从high向左推算,后面依次继续.

直到low等于了high,这俩索引最终就指向了基数,基数左边都比基数小,右边都比基数大,但是左边一半(可能左右数字个数不一样多)和右边一半还没排序,左边一半继续用刚才的方法,左端low定为0,右端high定为基数左边的第一个数字的索引(就是刚才low和high),右边一半也像刚才的方法,左边的low数字定位为基数右边第一个数字的索引,high就用列表总长度,和最初的一样,再继续下去迭代.直到出现low>high,迭代才停止.

5.希尔排序

思路:

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本,该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量（gap）”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率比直接插入排序有较大提高。下面借用一下网上找的图:

6.归并排序

归并排序采用分而治之的原理：

将一个序列从中间位置分成两个序列；

在将这两个子序列按照第一步继续二分下去；

 直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

如何合并？

下图中的倒数第三行表示为第一次合并后的数据。其中一组数据为 4 8  ，  5 7。该两组数据合并方式为：每一小组数据中指定一个指针，指针指向每小组数据的第一个元素，通过指针的偏移指定数据进行有序排列。排列情况如下：

1. p1指向4，p2指向5，p1和p2指向的元素4和5进行比较，较小的数据归并到一个新的列表中。经过比较p1指向的4会被添加到新的列表中，则p1向后偏移一位，指向了8，p2不变。

2.p1和p2指向的元素8，5继续比较，则p2指向的5较小，添加到新列表中，p2向后偏移一位，指向了7。

3.p1和p2指向的元素8，7继续比较，7添加到新列表中，p2偏移指向NULL，比较结束。

4.最后剩下的指针指向的数据（包含该指针指向数据后面所有的数据）直接添加到新列表中即可。

借用一下网上找的图:

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。