排序方法有哪几种 排序方法的相关知识

1、排序方法有10种，分别是：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。

2、冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。

3、选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法。

4、插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。

首先把所有数据填进一个完全二叉树中。然后对非终端结点n/2向下进行调整。建小根堆的时候方法是：

1、元素下调。比较它与两个孩子的大小。哪个孩子比它小也比兄弟小则把它调到那个孩子的位置。然后再判断该位置还要不要往下调。

2、从n/2开始，对它之前的所有元素进行1 *** 作。

扩展资料：

 

稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序。

1、时间复杂度：即从序列的初始状态到经过排序算法的变换移位等 *** 作变到最终排序好的结果状态的过程所花费的时间度量。

2、空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

3、使用场景：排序算法有很多，不同种类的排序算法适合不同种类的情景，可能有时候需要节省空间对时间要求没那么多，反之，有时候则是希望多考虑一些时间，对空间要求没那么高，总之一般都会必须从某一方面做出抉择。

4、稳定性：稳定性是不管考虑时间和空间必须要考虑的问题，往往也是非常重要的影响选择的因素。

参考资料来源：百度百科-堆排序

#include <stdioh>
#include <stdlibh>
#include <stringh>
int sort_function( const void a, const void b);
char list[5][4] = { "cat", "car", "cab", "cap", "can" };
int main(void)
{
int x;
qsort((void )list, 5, sizeof(list[0]), sort_function); // 调用快速排序
for (x = 0; x < 5; x++)
printf("%s\n", list[x]);
return 0;
}
int sort_function( const void a, const void b)
{ //自已要定义一个简单的比较函数就可
return( strcmp((char )a,(char )b) );
}
// C++中自身有一个通用的快速 qsort,可以用它 ,自已要定义一个简单的比较函数就可

1 快速排序（QuickSort）
快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序（HeapSort）
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell排序（ShellSort）
Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用DEKnuth的分组方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
5 插入排序（InsertSort）
插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
6 冒泡排序（BubbleSort）
冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。
7 交换排序（ExchangeSort）和选择排序（SelectSort）
这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。
8 基数排序（RadixSort）
基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。
9 总结
下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。
排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
基数 O(logRB) O(logRB) 稳定 O(n)
B是真数(0-9)，
R是基数(个十百)

Shell O(nlogn) O(ns) 1<s<2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

堆排序，也叫二叉堆排序。
完全二叉树：
1、左右子树的节点数满足 Ln/Rn=1
2、左右子树高度满足 Rh+1>=Lh>=Rh
3、子节点值统一比父节点大（小）。

最大堆：2叉树的所有子节点都比父节点小。所以根节点是最大的。
最小堆：2叉树的所有子节点都比父节点大。所以根节点是最小的。

建堆：假设最多有N个数据。开辟一段用来存这N个数据的空间。根节点位置为0。其子节点位置为1、2。所有子节点位置与父节点的位置（k）关系：k，2k+1，2k+2。 假设已经有了n个数据，那么新数据自然放在n位（因为位置是从0开始），定义一个函数 shift_up() 用来调整新数据。它的功能是：将新数据与 (n-1)/2 位置的数据（新数据的父节点）比较，如果比父节点大，那么就交换，继续比较，直到它比父节点小。

重新建堆： 当取数据时，就是将根节点取出来。因为根节点是最大的，所以自然还要将其所有子节点进行调整，以保证剩下的数据的根节点是最大的。方法是：将最后一个数放到根节点位置（因为根节点取出后，根节点就空了），然后调用 shift_down()函数将其与1、2位置的数比较，如果比它大，则交换，然后继续与2k+1，2k+2位置的比较，直到这两个位置的数都比它小。

堆排序时间复杂度，主要在每次选取最大数之后，重新建堆的过程以及初始化堆过程。

堆排序是指利用堆积树这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。

堆是一个优先级队列，对于大顶堆而言，堆顶元素的权值最大。将待排序的数组建堆，然后不断地删除堆顶元素，就实现了排序。

堆的 *** 作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种 *** 作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

---