电脑知识
排序方法(排序方法的稳定性是指)
2023-04-12 11:39

1、蛮力排序(Brute-force sorting):蛮力排序又称为暴力排序,是最简单直观的一种排序方法,它采用了枚举解法,依次给定每种可能排序的情况,类似于静态搜索,然后从这些情况中寻找一种最优的排序方式,根据排序需求和数据状况,决定数据的最终排列顺序。

2、选择排序(Selection sort):选择排序的基本思想是在要排序的一组数中,选出最小(或者最大)的一个数与第一个位置的数交换;然后从剩下的数当中继续寻找最小(或者最大)的与第二个位置的数交换,以此完成整个数组排序。

同时,选择排序也是一种不稳定的排序方法,它会出现相同数据值情况下相对位置发生变化。

3、冒泡排序(Bubble sort):两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。因为记录的比较和调整是趟失败的,结束时最大的记录在后面,所以称为冒泡排序。

算法特性:冒泡排序是以数据交换的方式进行排序,特点是只要数据出现反序,就会出发交换动作,它不断把最大值移动到最后位置,它是一种稳定的排序算法。

4、插入排序(Insertion sort):插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。

特点:插入排序属于稳定排序,最好是正序排序,正序排序时,时间效率可以达到最快,空间效率为1,排序时间取决于输入中元素的初始顺序。

5、希尔排序(Shell sort):它是插入排序的一种又称缩小增量排序。它是先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。它是不稳定的排序算法,时间复杂度为o(nlogn)。

6、归并排序(Merge sort):采用分治法,将目标数组分解成若干个子序列,在子序列内进行排序,然后合并排序结果,使整个序列被排序。它是基于比较的排序方法,同时也是一种稳定的排序方法,时间复杂度为O(nlogn)。

7、快速排序(Quick sort):它的基本思想是:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。它是不稳定的排序方法,它的速度仅次于冒泡排序和简单选择排序,时间复杂度为O(nlogn)。

1. 冒泡排序

冒泡排序是一个简单而有效的排序算法,利用数组中元素之间的比较和交换来排序,它的基本操作是通过趟数的过程一次比较两个元素的值的大小,如果需要排序的则进行交换。这个算法的时间复杂度是O(n2),它也是一种稳定的排序算法,因为它维护着稳定性,也就是说如果a原本在b前面,则最后a在b前面。

2. 选择排序

选择排序是一个简单的排序算法,它依次遍历待排序数组中的元素,并选取最小的元素,将其交换到第一位置,之后再从剩余的元素中选取最小的元素,将其交换到第二位置,以此类推直至数组有序。它的时间复杂度也是O(n2),但是它是一种不稳定的排序算法,它会改变原有的顺序。

3. 插入排序

插入排序是一种简单但有效的排序算法,它通过比较待排序序列中的每个元素,将它们依次插入到有序序列中的适当位置而达到排序的目的。插入排序的时间复杂度是O(n2),它也是一种稳定的排序算法,同冒泡排序一样,如果a原本在b前面,则最后a在b前面。

4. 希尔排序

希尔排序是一种改进的插入排序,它是通过将数据分割到几个部分,先对每一部分进行排序,然后再将这几部分排序完的数据合并在一起而实现排序的功能。这种算法的时间复杂度可以降低到O(nlogn),它也是一种不稳定的排序算法,在原本存在的顺序可能会改变。

5. 快速排序

快速排序是一种简单而有效的排序算法,它将序列化切分为两个子序列,分别按照大小排序,最终达到全序列排序的目的。它的时间复杂度是O(nlogn),也是一种不稳定的排序算法。

6. 堆排序

堆排序也是一种简单而有效的排序算法,它利用堆这种数据结构来达到排序的目的,通过不断的下沉和上浮实现对堆中元素的排序。它的时间复杂度是O(nlogn),也是一种不稳定的排序算法。

7. 归并排序

归并排序是一种分治策略的排序算法,它利用分治思想将序列化切分,分别用其他排序算法排好序之后再将排好序的子序列归并。它的时间复杂度是O(nlogn),它也是一种稳定的排序算法,同冒泡排序一样,如果a原本在b前面,则最后a在b前面。

发表评论
0评