sort是稳定排序吗（什么是稳定的排序方法）

本文目录

• 什么是稳定的排序方法
• c＋＋的stdlib.h里的qsort函数是不是稳定排序
• C++中关于泛型算法sort()用法的问题C++达人进！
• 怎么让Heap sort 变为稳定排序
• sort 函数是稳定的吗
• Python中既然有了sort()可以排序，那还有必要实现其他排序算法吗例如堆排序，快速排序
• 稳定排序有哪些
• 数据结构内部排序问题
• sorth 是什么意思

什么是稳定的排序方法

所谓稳定的排序算法就是你排序之后相同大小的数值没有发生变化，比如： 2 4 4 1 6 3 排序之后第二4的位置依然在一个4之后就是他们两个没有发生位置变化;称之为稳定；

c＋＋的stdlib.h里的qsort函数是不是稳定排序

• qsort是快速排序，不是稳定排序

• sort是C++的。qsort是C语言里的快速排序。

C++中关于泛型算法sort()用法的问题C++达人进！

首先实现这个排序有两种方式，一个自己定义一个返回值为bool的比较函数。一个是自己定义类中的《操作函数。第一种方式可以简单写为。bool cmp(node x,node y){return x.key1《b.key1;}sort(vec.begin,vec.end.cmp);这种排序是从小到大的，也就是如果cmp(a,b)为真，则a一定在b的前面，如果cmp(a,b)和cmp(b,a)都为false.的话，也就是a.key1==b.key1,则他们的先后顺序则是不一定的，可能a在b前面，也可能b在a前面。也就是说这种排序算法是不稳定的。第二种方式struct node{ int key1; int key2; book operator 《(const node &m) { return key1《m.key1; }}这样就不用自己定义比较函数。对与sort()排序是不稳定的，正如前面说的，如果需要稳定排序的话，可以使用stable_sort，它可以保证相等的元素原来的相对次序是不变的。

怎么让Heap sort 变为稳定排序

算法引进：在这里我直接引用《大话数据结构》里面的开头：在前面讲到 简单选择排序 ，它在待排序的 n 个记录中选择一个最小的记录需要比较 n - 1 次，本来这也可以理解，查找第一个数据需要比较这么多次是正常的，否则如何知道他是最小的记录。可惜的是，这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较重，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。如果可以做到每次在选择到最小记录的同时，并根据比较结果对其他记录做出相应的调整，那样排序的总体效率就会非常高了。而堆排序，就是对简单选择排序进行的一种改进，这种改进的效果是非常明显的。基本思想：在介绍堆排序之前，我们先来介绍一下堆：《大话数据结构》里的定义：堆 是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，成为大顶堆（大根堆）；或者每个节点的值都小于或等于其左右节点的值，成为小顶堆（小根堆）。当时我在看到这里的时候也对有“堆是否是完全二叉树”有过疑问，网上也有说不是完全二叉树的，但是无论堆是不是完全二叉树，尚且保留意见。我们只要知道，在这里我们采用完全二叉树形式的大根堆（小跟堆），主要是为了方便存储和计算（后面我们会看到带来的便利）。堆排序算法：堆排序就是利用堆（假设利用大根堆）进行排序的方法，它的基本思想是：将待排序的序列构造成一个大根堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n - 1 个序列重新构造成一个堆，这样就会得到 n 个元素中的次小的值。如此反复执行，便能得到一个有序序列了。大根堆排序算法的基本操作：①建堆，建堆是不断调整堆的过程，从 len/2 处开始调整，一直到第一个节点，此处 len 是堆中元素的个数。建堆的过程是线性的过程，从 len/2 到 0 处一直调用调整堆的过程，相当于 o(h1) + o(h3) …+ o(hlen/2) 其中 h 表示节点的深度， len/2 表示节点的个数，这是一个求和的过程，结果是线性的 O(n)。②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点 left(i) , right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是 lgn 的操作，因为是沿着深度方向进行调整的。③堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面 len-1 个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是 O(nlgn)。因为建堆的时间复杂度是 O(n)（调用一次）；调整堆的时间复杂度是 lgn，调用了 n-1 次，所以堆排序的时间复杂度是 O(nlgn)。在这个过程中是需要大量的图示才能看的明白的，但是我懒。。。。。。算法实现：《?php //堆排序（对简单选择排序的改进） function swap(array &$arr,$a,$b){ $temp = $arr)重新调整为大根堆 HeapAdjust($arr,0,$i - 1); } } $arr = array(9,1,5,8,3,7,4,6,2); HeapSort($arr); var_dump($arr); 时间复杂度分析：它的运行时间只要是消耗在初始构建对和在重建堆屎的反复筛选上。总体上来说，堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最差和平均时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。堆排序是一种不稳定排序方法。本篇博客参考自《大话数据结构》，在此仅作记录，方便以后查阅，大神勿喷！

sort 函数是稳定的吗

既然有稳定排序函数STL stable_sort，说明sort()函数的算法不是稳定算法（这并不代表在所有情况下都不稳定）。排序算法的稳定性是指对排序指标项相同的记录，在排序后不改变其相对顺序。你验证的数据多并不一定就有代表性。如果排序指标项都是两两不同的，就不存在稳定性的问题。如果能够找到函数的详细说明，根据其算法就可以很快确定是否稳定。如果找不到函数的详细说明，而要自行验证其稳定性，应该先设计各种情况下的数据再进行检验。可以参见如下位置的例子：***隐藏网址***

Python中既然有了sort()可以排序，那还有必要实现其他排序算法吗例如堆排序，快速排序

肯定有必要的，sort是基于快速排序，但我们编程的时候不单单要会用，而且要知道原理此外，有些情况下冒泡、选择排序的时间复杂度也不差，而且实现简单，更适用于一些小数据量的情况，这时候这些排序反而有优势而且有时候数据结构不一定是整型等， 是我们自定义的类型，要对其中的某个成员变量排序，知道原理就更容易理解

稳定排序有哪些

1.稳定的排序冒泡排序（bubble sort） — O(n2) 鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2) 插入排序 （insertion sort）— O(n2) 桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体 归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体 原地归并排序 — O(n2) 二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体 鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体 基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体 Gnome sort — O(n2) Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体 2.不稳定的排序选择排序 （selection sort）— O(n2) 希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本 Comb sort — O(n log n) 堆排序 （heapsort）— O(n log n) Smoothsort — O(n log n) 快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）

数据结构内部排序问题

是的在N个中排序，冒泡排序使用的时间是比较稳定的而直接排序则视数列刚开始的排列有很大的差别冒泡排序的时间复杂度是O（n^2）选择排序的时间复杂度最好为O（nlog2n）最坏为O（n^2）二、几种常见算法的介绍及复杂度分析1.基本概念 1.1稳定排序(stable sort)和非稳定排序 稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。1.2内排序( internal sorting )和外排序( external sorting) 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。1.3算法的时间复杂度和空间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。2.几种常见算法 2.1冒泡排序 （Bubble Sort）冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。 冒泡排序是稳定的。算法时间复杂度是O(n ^2)。2.2选择排序 （Selection Sort）选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。选择排序是不稳定的。算法复杂度是O(n ^2 )。2.3插入排序 （Insertion Sort）插入排序的基本思想是，经过i-1遍处理后,L时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。 直接插入排序是稳定的。算法时间复杂度是O(n ^2)2.4堆排序堆排序是一种树形选择排序，在排序过程中，将A看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。堆排序是不稳定的。算法时间复杂度O(nlog n)。2.5归并排序设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。2.6快速排序 快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。

sorth 是什么意思

是C++中的一种函数。

sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，sort函数包含在头文件为#include《algorithm》的c++标准库中。

参数：

（1）start表示要排序数组的起始地址；

（2）end表示数组结束地址的下一位；

（3）cmp用于规定排序的方法，可不填，默认升序。

sort类函数总结

sort：对给定区间所有元素进行排序。

stable_sort：对给定区间所有元素进行稳定排序。

partial_sort：对给定区间所有元素部分排序。

partial_sort_copy：对给定区间复制并排序。

nth_element：找出给定区间的某个位置对应的元素。

is_sorted：判断一个区间是否已经排好序。

partition：使得符合某个条件的元素放在前面。

stable_partition：相对稳定的使得符合某个条件的元素放在前面。