本文目录
最好的排序算法是什么算法呀
拿钱让别人替你排！事实上各种排序方法个有优缺点适用于不同的场合：排序（Sorting)插入排序（insertion sort）:直接插入排序 希尔排序（shell’s sort）(缩小增量排序Diminishing increment sort)交换排序：冒泡排序（bubble sort）快速排序（quick sort）选择排序:直接选择排序（straight selection sort），堆排序；归并排序（merge sort）：分配排序：箱排序（Bin sort）,基数排序（radix sort）更多的自己研究一下。排序方法的选取主要考虑算法的性能与资源占用。也就是速度和占用的存储空间。
文件局部有序或文件长度较小的情况下,最佳的排序方法是什么
直接插入排序。当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n-1趟排序，也即时间复杂度仍为O(n^2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(n log2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n^2)降至O(n)。各种排序方法的选择:①就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当n较大时，归并排序较堆排序省，但归并排序所需的辅助空间最大。 ②简单排序方法中，直接插入排序最简单，当待排序的结点已按键值“基本有序”且n较小时，则应采用直接插入排序或冒泡排序，直接插入排序比冒泡排序更快些，因此经常将直接插入排序和其他的排序方法结合在一起使用。 ③当n很大且键值位数较小时，采用基数排序较好；而当键值的最高位分布较均匀时，可先按其最高位将待排序结点分成若干子表，而后对各子表进行直接插入排序。 ④从方法的稳定性来比较，直接插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法；而直接选择排序、希尔排序、堆排序和快速排序都是不稳定的排序方法。 内部排序方法的选择:各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。 *若待排序的记录个数n较小时，可采用简单排序方法 *若n 较大时，应采用快速排序或堆排序。 若待排序的记录已基本有序，可采用起泡排序。
希尔排序图解流程图
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是希尔排序算法： 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位； 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。 1. 算法步骤 选择一个增量序列 t1，t2，……，tk，其中 ti 》 tj, tk = 1； 按增量序列个数 k，对序列进行 k 趟排序； 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 2. 动图演示 代码实现 JavaScript 实例 function shellSort ( arr ) { var len = arr. length , temp , gap = 1 ; while ( gap 0 ; gap = Math . floor ( gap / 3 ) ) { for ( var i = gap ; i = 0 && arr 》 temp ; j -= gap ) { arr ; } arr = temp ; } } return arr ; } Python 实例 def shellSort ( arr ) : import math gap = 1 while ( gap 0 : for i in range ( gap , len ( arr ) ) : temp = arr j = i-gap while j 》= 0 and arr 》 temp: arr j- = gap arr = temp gap = math . floor ( gap/ 3 ) return arr Go 实例 func shellSort ( arr int { length := len ( arr ) gap := 1 for gap 《 length / 3 { gap = gap * 3 + 1 } for gap 》 0 { for i := gap ; i 《 length ; i ++ { temp := arr j := i - gap for j 》 = 0 && arr 》 temp { arr j -= gap } arr = temp } gap = gap / 3 } return arr } Java 实例 public static void shellSort ( int arr ) { int length = arr. length ; int temp ; for ( int step = length / 2 ; step 》= 1 ; step /= 2 ) { for ( int i = step ; i = 0 && arr 》 temp ) { arr ; j -= step ; } arr = temp ; } } } PHP 实例 function shellSort ( $arr ) { $len = count ( $arr ) ; $temp = 0 ; $gap = 1 ; while ( $gap 0 ; $gap = floor ( $gap / 3 ) ) { for ( $i = $gap ; $i = 0 && $arr 》 $temp ; $j -= $gap ) { $arr ; } $arr = $temp ; } } return $arr ; } C 实例 void shell_sort ( int arr , int len ) { int gap , i , j ; int temp ; for ( gap = len 》》 1 ; gap 》 0 ; gap 》》= 1 ) for ( i = gap ; i = 0 && arr 》 temp ; j -= gap ) arr ; arr = temp ; } } C++ 实例 template void shell_sort ( T array , int length ) { int h = 1 ; while ( h = 1 ) { for ( int i = h ; i = h && array = tmp; } gap /= 3; } } 以上为希尔排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括： 关于时间复杂度 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序； O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。 关于稳定性 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。 名词解释： n：数据规模 k："桶"的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
选择排序，快速排序，冒泡排序，堆排序，插入排序，基排序的程序的运行速度
分析如下：冒泡排序：在最优情况下只需要经过n-1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。 冒泡排序2：它是冒泡排序的改良（一次下沉再一次上浮），最优情况和最坏情况与冒泡排序差不多，但是一般情况下它要好过冒泡排序，它一次下沉，再一次上浮，这样避免了因一个数的逆序，而造成巨大的比较。如（2,3,4,…,n-1,n,1），用冒泡排序需要n(n-1)/2次比较，而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次，第一轮1将上移一位，第二轮1将移到首位，第三轮将发现无数据交换，序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法，只适合于数据基本有序的排序。 快速排序：它同样是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度为O(nlog2n)。即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时，一串为空，另一串为m-1（程序中的100K正序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优）。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法，因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。 直接选择排序：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。 堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。 直接插入排序：简单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。 希尔排序：增量的选择将影响希尔排序的效率。但是无论怎样选择增量，最后一定要使增量为1，进行一次直接插入排序。但它相对于直接插入排序，由于在子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。 归并排序：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。 基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。 按平均时间将排序分为类： (1) 平方阶(O(n2))排序 各类简单排序，例如直接插入、直接选择和冒泡排序； (2) 线性对数阶(O(nlog2n))排序 如快速排序、堆排序和归并排序； (3) O(n1+§))排序 §是介于0和1之间的常数。希尔排序便是一种； (4) 线性阶(O(n))排序 本程序中的基数排序，此外还有桶、箱排序。 排序方法的选择 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要 (1)若n较小，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数； 但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。 这两种都是稳定排序算法。 (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。 (3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。 归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。 (4)特殊的箱排序、基数排序 它们都是一种稳定的排序算法，但有一定的局限性： 1、关键字可分解。 2、记录的关键字位数较少，如果密集更好 3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。 事实上各种排序方法个有优缺点适用于不同的场合：排序（Sorting)插入排序（insertion sort）:直接插入排序 希尔排序（shell’s sort）(缩小增量排序Diminishing increment sort)交换排序：冒泡排序（bubble sort）快速排序（quick sort）选择排序:直接选择排序（straight selection sort），堆排序；归并排序（merge sort）：分配排序：箱排序（Bin sort）,基数排序（radix sort）更多的自己研究一下。排序方法的选取主要考虑算法的性能与资源占用。也就是速度和占用的存储空间。希望对你有所帮助！
调用C++库函数快速排序
使用C++标准库的快速排序函数C++的标准库stdlib.h中提供了快速排序函数。请在使用前加入对stdlib.h的引用：#include 《cstdlib》 或 #include 《stdlib.h》qsort(void* base, size_t num, size_t width, int(*)compare(const void* elem1, const void* elem2))参数表*base: 待排序的元素（数组，下标0起）。num: 元素的数量。width: 每个元素的内存空间大小（以字节为单位）。可用sizeof()测得。int(*)compare: 指向一个比较函数。*elem1 *elem2: 指向待比较的数据。比较函数的返回值返回值是int类型，确定elem1与elem2的相对位置。elem1在elem2右侧返回正数，elem1在elem2左侧返回负数。控制返回值可以确定升序/降序。一个升序排序的例程：int Compare(const void *elem1, const void *elem2){ return *((int *)(elem1)) - *((int *)(elem2));}int main(){ int a; qsort(a, 100, sizeof(int), Compare); return 0;}
