排序方法有哪几种（计算机排序方法有哪几种）

本篇文章给大家谈谈排序方法有哪几种，以及计算机排序方法有哪几种对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、排序算法有多少种
• 2、常见的几种排序算法总结
• 3、几种常见的排序（冒泡、选择、插入、希尔、堆排序）

排序算法有多少种

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：

(1)冒泡排序；

(2)选择排序；

(3)插入排序；

(4)希尔排序；

(5)归并排序；

(6)快速排序；

(7)基数排序；

(8)堆排序；

(9)计数排序；

(10)桶排序。

插入排序

插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。插入排序分直接差伏让插入排序、折半插入排序和希尔排序3类。

冒泡排序

冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第(n一1)个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一虚局种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。

选择排序

选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法。首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置，再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。使用这种排序时，要注意其中一个不同于冒泡法的细节。举例说明：序列58539．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。

快速排序

快速排序的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部厅贺分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，最终能够实现将所需排序的无序序列元素变为一个有序的序列。

归并排序

归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。

[img]

常见的几种排序算法总结

对于非科班生的我来说，算法似乎对我来说是个难点，查阅了一些吵族资料，趁此来了解一下几种排序算法。

首先了解一下，什么是程序

关于排序算法通常我们所说的往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法大体可分为两种：

一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等

冒泡排序它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

选择排序类似于冒泡排序，只不过选择排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

插入排序比冒泡排序和选择排序更有效率，插入排序类似于生活中抓扑克牌来。

插入排序具体算法描述，以数组[3, 2, 4, 5, 1]为例。

前面三种排序算法只有教学价值，因为效率低，很少实际使用。归并排序（Merge sort）则是一种被广泛使用的排序方法。

它的基本思想是，将两个已经排序的悉闹数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：

有了merge函数，就可以对任意数组排序了。基本方法是将数组不断地拆成两半，直到每一半只包含零个元素或一个元素为止，然后就用merge函数，将拆成两半的数组不断合并，直到升陆弊合并成一整个排序完成的数组。

快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。

快速排序算法步骤

参考：

常用排序算法总结(一)

阮一峰-算法总结

几种常见的排序（冒泡、选择、插入、希尔、堆排序）

内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;

外排序:由于排序的记录个数太多,不不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进⾏

1、顺序表结构

2、数据交换函数

3、数据打印

冒泡排序(Bubble Sort) 一种交换排序,它的基本思想就是: 两两⽐比较相邻的记录的关键字,如果 反序则交换,直到没有反序的记录为⽌.

也可以反过来，每次都把最大的值放到末尾。

简单排序算法(Simple Selection Sort) 就是通过n-i次关键词比较,从n-i+1个记录中找出关键 字最小的记录,并和第i(1=i=n) 个记录进行交换.

总结一句话就是(划重点)：从第一个位置开始比较，找出最小的，和第一个位置互换，开始下一轮。

（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；

（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；

（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；

冒泡排序优缺点：优点:比较简单，空间复杂度较低，是稳定的；

缺点:时间复杂度太高，效率慢；

选择排序优缺点：优点：一轮比较只需要换一次位置；

缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。

直接插入排序算法(Stright Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表 中,从而得到一个新的,记录数增1的有序表;

步骤1、将数据插入到有序表中与前信基一个比较，如果大于则不改变位置

2、如果插入数据小于前一个数据，则前面大的数据依次往后移动，然后找到合适位置滑绝谨插入该数据。

空间复杂度: O(1) 解读:在直接插⼊入排序中只使⽤用了了i,j,temp这三个辅助元素，与问题规模⽆无关，空间复杂度为O(1)

时间复杂度: O(n2)

希尔排序思想: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插⼊排序算法排 序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减⾄1时，整个序列恰被分成 一组，算法便终止.

其实就是分治法升级版的插入排序，又称为缩小增量排序。我们不断减半增量，直到增量为1时，退化为普通插入排序。

希尔排序通过增量进行了分组(分治)，比较的是L-r[j-increment]和L-[j]，跨度是increment，如果摸到的是较小的牌，只需要移动1次，而插入排序需要移动increment次。

也就是说希尔排序的优势是，能让较小的牌更容易来到数组的前面部分，节约了移动次数。

需要注意的是：

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。

或者

每个结宏谨点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图1为大顶堆：

下图为小顶堆：

我们用简单的公式来描述一下堆的定义就是：

大顶堆： arr[i] = arr[2i] arr[i] = arr[2i+1]

小顶堆： arr[i] = arr[2i] arr[i] = arr[2i+1]

1、用待排序序列构造一个大顶堆。

2、将其与末尾元素进行交换，此时末尾就为最大值。

3、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。

4、如此反复执行，便能得到一个有序序列了。

我们可以发现其实堆排序还是一种选择排序，用一句话概括思想：

利用堆结构特性，不断选出最大值，放到最后。

归并排序(Merging Sort) 就是利利⽤用归并的思想实现排序⽅方法. 它的原理理是假设初始序 列列含有n个记录,则可以看成n个有序的⼦子序列列. 每个⼦子序列列的⻓长度为1,然后两两合并.得 到[n/2]个⻓长度为2或1的有序⼦子序列列, 再两两归并. ......如此重复,直到得到⼀一个⻓长度为n 的有序序列列为此. 这种排序⽅方法称为2路路归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。

将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起。

进行合并时，我们需要一个额外的数组来进行辅助排序，再回填回原数组。

//6归并排序

首先设定一个分界值，通过该分界值将数组分成左右两部分。

将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。

此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

关于排序方法有哪几种和计算机排序方法有哪几种的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。