常见排序算法

墨蓝 2022-01-06 03:01 305阅读 0赞

稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。（即原本a在b前，a=b,排序之后位置任然不变。）

• 不稳定的排序算法：快速排序、希尔排序、堆排序、直接选择排序；  
• 稳定的排序算法：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序  
![1625675-20190408163346493-2026881032.png][]

In/out-place: 不占/占额外内存

![1625675-20190408163413180-629919951.png][]

**冒泡排序**

原理：比较两个相邻的元素，将值大的元素交换至右端。

思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。  
• 第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；  
• 第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；  
• 依次类推，每一趟比较次数-1；

N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次。

时间复杂度来说：  
1.如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。  
2.如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为：O(n2) 。  
综上所述：冒泡排序总的平均时间复杂度为：O(n2) 。

**选择排序**  
原理：每一趟从待排序的记录中选出最小（最大）的元素，顺序放在已排好序的序列最后（待排序的数列最前），直到全部记录排序完毕。也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序  
基本思想：给定数组：int\[\] arr=\{里面n个数据\}；第1趟排序，在待排序数据arr\[1\]~arr\[n\]中选出最小的数据，将它与arrr\[1\]交换；第2趟，在待排序数据arr\[2\]~arr\[n\]中选出最小的数据，将它与r\[2\]交换；以此类推，第i趟在待排序数据arr\[i\]~arr\[n\]中选出最小的数据，将它与r\[i\]交换，直到全部排序完成。

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2。

**插入排序**  
直接插入排序  
原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。  
将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

步骤  
1.从第一个元素开始，该元素可以认为已经被排序  
2.取出下一个元素，在已经排序的元素序列中从后向前扫描  
3.如果该元素（已排序）大于新元素，将该元素移到下一位置  
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置  
5.将新元素插入到该位置中  
6.重复步骤2

**希尔排序**  
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。  
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。  
希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

**归并排序**  
分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。  
核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

快速排序

基本思想：快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。（采用分治法）

排序过程

1.  基准（pivot）元素的选择

可以选择第一个元素或随机选择一个元素。  
选择第一个元素作为基准元素，可能导致快速排序时间复杂度退化为O(n^2)【在原本逆序的数列时】  
随机选择一个元素：也可能存在问题。每一次也有极小的几率选到数列的最大值或最小值，同样会影响到分治的效果。

快速排序的平均时间复杂度是 O（nlogn），最坏情况下的时间复杂度是 O（n^2）。平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是 O（nlogn）。

1.  元素的移动

选定了基准元素以后，如何进行元素移动？两种方法  
1.挖坑法  
2.指针交换法

挖坑法  
• 首先，我们选定基准元素Pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素：

• 接下来，从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。  
在当前数列中，1<4，所以把1填入基准元素所在位置，也就是坑的位置。这时候，元素1本来所在的位置成为了新的坑。同时，left向右移动一位。

此时，left左边绿色的区域代表着小于基准元素的区域。

• 接下来，我们切换到left指针进行比较。如果left指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把left指向的元素填入坑中。  
在当前数列中，7>4，所以把7填入index的位置。这时候元素7本来的位置成为了新的坑。同时，right向左移动一位。

此时，right右边橙色的区域代表着大于基准元素的区域。  
8>4，元素位置不变，right左移

2<4，用2来填坑，left右移，切换到left。

6>4，用6来填坑，right左移，切换到right。

3<4，用3来填坑，left右移，切换到left。

5>4，用5来填坑，right右移。这时候left和right重合在了同一位置。

这时候，把之前的pivot元素，也就是4放到index的位置。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。

指针交换法  
何谓指针交换法？我们来看一看详细过程。  
给定原始数列如下，要求从小到大排序：

开局和挖坑法相似，我们首先选定基准元素Pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素：

接下来是第一次循环，从right指针开始，把指针所指向的元素和基准元素做比较。如果大于等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针。  
在当前数列中，1<4，所以right直接停止移动，换到left指针，进行下一步行动。  
轮到left指针行动，把指针所指向的元素和基准元素做比较。如果小于等于pivot，则指针向右移动；如果大于pivot，则left指针停止移动。  
由于left一开始指向的是基准元素，判断肯定相等，所以left右移一位。

由于7 > 4，left指针在元素7的位置停下。这时候，我们让left和right指向的元素进行交换。

接下来，我们进入第二次循环，重新切换到right向左移动。right先移动到8，8>2，继续左移。由于2<8，停止在2的位置。

切换到left，6>4，停止在6的位置。

元素6和2交换。

进入第三次循环，right移动到元素3停止，left移动到元素5停止。

元素5和3交换。

进入第四次循环，right移动到元素3停止，这时候请注意，left和right指针已经重合在了一起。

当left和right指针重合之时，我们让pivot元素和left与right重合点的元素进行交换。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。

来自 <http://www.sohu.com/a/246785807\_684445>

**堆排序**  
基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

转载于:https://www.cnblogs.com/zoe1101/p/10671438.html

[1625675-20190408163346493-2026881032.png]: /images/20211228/7216cfe3621441379a63ac3400705b9b.png
[1625675-20190408163413180-629919951.png]: /images/20211228/7e3713b244844f518944230b5ef9266d.png