下载文档原格式
⼗⼤经典排序算法总结最近⼏天在研究算法，将⼏种排序算法整理了⼀下，便于对这些排序算法进⾏⽐较，若有错误的地⽅，还请⼤家指正0、排序算法说明0.1 排序术语稳定：如果a=b,且a原本排在b前⾯，排序之后a仍排在b的前⾯不稳定：如果a=b,且a原本排在b前⾯，排序之后排在b的后⾯时间复杂度：⼀个算法执⾏所耗费的时间空间复杂度：⼀个算法执⾏完所需内存的⼤⼩内排序：所有排序操作都在内存中完成外排序：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏0.2算法时间复杂度、空间复杂度⽐较0.3名词解释n:数据规模k:桶的个数In-place:占⽤常数内存，不占⽤额外内存Out-place:占⽤额外内存0.4算法分类1.冒泡排序冒泡排序是⼀种简单的排序算法。
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。
⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端1.1算法描述⽐较相邻的元素，如果前⼀个⽐后⼀个打，就交换对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾最后⼀对，这样在最后的元素应该会是最⼤的数针对所有的元素重复以上的步骤，除了最后⼀个重复步骤1-3，知道排序完成1.2动图演⽰1.3代码实现public static int[] bubbleSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++)for (int j = 0; j < array.length - 1 - i; j++)if (array[j + 1] < array[j]) {int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}return array;}1.4算法分析最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)2.选择排序表现简单直观的最稳定的排序算法之⼀，因为⽆论什么数据都是O(n2)的时间复杂度，⾸先在未排序序列中找到最⼩（⼤）元素，与数组中第⼀个元素交换位置，作为排序序列的起始位置，然后再从剩余未排序元素中继续寻找最⼩（⼤）的元素，与数组中的下⼀个元素交换位置，也就是放在已排序序列的末尾2.1算法描述1.初始状态：⽆序区为R[1..n],有序区为空2.第i躺排序开始时，当前有序区和⽆序区R[1..i-1]、R[i..n]3.n-1趟结束，数组有序化2.2动图演⽰2.3代码实现public static int[] selectionSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i; j < array.length; j++) {if (array[j] < array[minIndex]) //找到最⼩的数minIndex = j; //将最⼩数的索引保存}int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}return array;}2.4算法分析最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)3、插⼊排序是⼀种简单直观的排序算法，通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描，找到相应位置并插⼊，需要反复把已排序元素逐步向后挪位，为最新元素腾出插⼊空间3.1算法描述1.从第⼀个元素开始，该元素可以认为已经被排序2.取出下⼀个元素（h），在已排序的元素序列中从后往前扫描3.如果当前元素⼤于h，将当前元素移到下⼀位置4.重复步骤3，直到找到已排序的元素⼩于等于h的位置5.将h插⼊到该位置6.重复步骤2-53.2动图演⽰3.3代码实现public static int[] insertionSort(int[] array) {if (array.length == 0)return array;int current;for (int i = 0; i < array.length - 1; i++) {current = array[i + 1];int preIndex = i;while (preIndex >= 0 && current < array[preIndex]) {array[preIndex + 1] = array[preIndex];preIndex--;}array[preIndex + 1] = current;}return array;}3.4算法分析最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)4、希尔排序是简单插⼊排序经过改进之后的⼀个更⾼效的版本，也称为缩⼩增量排序，同时该算法是冲破O(n2）的第⼀批算法之⼀。
10种常用典型算法1. 冒泡排序(Bubble Sort)冒泡排序是一种简单的排序算法。
它通过依次比较相邻的两个元素，如果顺序不对则交换位置。
这样，每一趟排序都会将最大的元素移动到末尾。
通过多次重复这个过程，直到所有元素按照升序排列为止。
2. 选择排序(Selection Sort)选择排序也是一种简单的排序算法。
它通过每次从未排序的部分中选出最小的元素，放到已排序部分的末尾。
通过多次重复这个过程，直到所有元素按照升序排列为止。
3. 插入排序(Insertion Sort)插入排序是一种简单且稳定的排序算法。
它通过将未排序的元素逐个插入到已排序部分的正确位置。
每次插入一个元素，已排序部分都是有序的。
通过多次重复这个过程，直到所有元素按照升序排列为止。
4. 快速排序(Quick Sort)快速排序是一种高效的排序算法。
它通过选择一个基准元素，将数组分成两部分，一部分元素小于基准，另一部分元素大于基准。
然后对这两部分递归地进行快速排序。
通过多次重复这个过程，直到所有元素按照升序排列为止。
5. 归并排序(Merge Sort)归并排序是一种稳定的排序算法。
它通过将数组递归地分成两半，分别对这两半进行归并排序，然后将排序好的两部分合并起来。
通过多次重复这个过程，直到所有元素按照升序排列为止。
6. 堆排序(Heap Sort)堆排序是一种高效的排序算法。
它利用堆的性质来进行排序，通过构建一个最大堆或最小堆，并不断地取出堆顶元素并调整堆。
通过多次重复这个过程，直到所有元素按照升序排列为止。
7. 计数排序(Counting Sort)计数排序是一种非比较性的整数排序算法。
它通过统计每个元素的个数来排序。
首先统计每个元素出现的次数，然后根据元素的大小顺序将其放入新的数组中。
通过多次重复这个过程，直到所有元素按照升序排列为止。
8. 桶排序(Bucket Sort)桶排序是一种非比较性的排序算法。
它通过将元素划分到不同的桶中，每个桶内再使用其他排序算法进行排序。
各种排序算法的总结和比较1 快速排序（QuickSort ）快速排序是一个就地排序，分而治之，大规模递归的算法。
从本质上来说，它是归并排序的就地版本。
快速排序可以由下面四步组成。
（1 ）如果不多于1 个数据，直接返回。
（2 ）一般选择序列最左边的值作为支点数据。
（3 ）将序列分成2 部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4 ）对两边利用递归排序数列。
快速排序比大部分排序算法都要快。
尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。
快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序（MergeSort ）归并排序先分解要排序的序列，从1 分成2 ，2 分成4 ，依次分解，当分解到只有1 个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。
合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序( HeapSort )堆排序适合于数据量非常大的场合(百万数据)。
堆排序不需要大量的递归或者多维的暂存数组。
这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell 排序( ShellSort )Shell 排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。
平均效率是O(nlogn) 。
其中分组的合理性会对算法产生重要的影响。
现在多用D.E.Knuth 的分组方法。
Shell 排序比冒泡排序快5 倍，比插入排序大致快2 倍。
Shell 排序比起QuickSort ，MergeSort ，HeapSort 慢很多。
排序算法总结排序算法是计算机科学中最基础且常用的算法之一。
它们的作用是将一组数据按照指定的顺序进行排列。
根据数据量的大小和特点，选择适合的排序算法可以提高程序的性能。
常见的排序算法有冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序、堆排序和计数排序等。
冒泡排序是最简单、最直观的排序算法。
它通过多次比较相邻的元素，将较大的数往后移动，将较小的数往前移动，从而实现排序。
但是冒泡排序的时间复杂度较高，为O(n^2)。
插入排序的思想是将数组分为有序区和无序区，每次将无序区的第一个元素插入到有序区的合适位置。
它的时间复杂度也为O(n^2)，但在实际应用中对小规模数据进行排序时表现良好。
选择排序每次从数组中选择最小的元素，与数组的第一个元素交换位置，然后从剩下的元素中选择最小的元素，与数组的第二个元素交换位置，依此类推。
它的时间复杂度也为O(n^2)，但它的交换次数相对较少。
希尔排序是直接插入排序的改进版，它将数组按照一定的步长进行分组，对每组进行插入排序，然后缩小步长，直到步长为1，最后再进行一次插入排序。
希尔排序的时间复杂度介于O(n^1.3)和O(n^2)之间，具体取决于步长的选择。
归并排序是一种稳定且分治的排序算法，它将数组分为两个子数组，分别对子数组进行排序，然后将排好序的子数组合并成一个有序的数组。
归并排序的时间复杂度为O(nlogn)，但需要额外的空间来存储临时数组。
快速排序是一种高效且不稳定的排序算法，它通过选取一个基准元素，将数组分为左右两个子数组，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素，然后在左右子数组中递归地进行快速排序。
快速排序的时间复杂度为O(nlogn)，但在最坏情况下可能达到O(n^2)。
堆排序利用堆这种数据结构进行排序。
堆排序的思想是将数组构建成一个最大堆或最小堆，然后将堆顶的元素与数组的最后一个元素交换位置，再对剩余的元素进行调整，再重复执行这个过程。
数学排序知识点总结一、排序算法的概念及分类1.1 排序算法的概念排序算法是一种用来对一组数据进行排序的算法。
它使得数据按照一定的顺序排列，方便我们进行查找、统计、分析等操作。
在实际应用中，排序算法扮演着非常重要的角色，例如在数据库检索、数据压缩、图像处理等领域都有着广泛的应用。
1.2 排序算法的分类排序算法一般可以分为两大类，即比较排序和非比较排序。
比较排序是指通过比较待排序元素之间的大小关系来进行排序的算法，其时间复杂度一般为O(nlogn)，包括常见的快速排序、归并排序、堆排序等；非比较排序则是通过其他辅助信息来确定元素的顺序，其时间复杂度通常较低，包括计数排序、桶排序、基数排序等。
二、常见的排序算法及其应用2.1 快速排序快速排序是一种常用的比较排序算法，其基本思想是通过一次划分将待排序数组分成两个部分，使得左边的元素均小于右边的元素，然后再对左右部分递归进行排序。
快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。
快速排序可以在很多实际应用中发挥作用，例如在数据库查询、数据压缩、图像处理等领域都有着广泛的应用。
2.2 归并排序归并排序也是一种常用的比较排序算法，其基本思想是将待排序数组分成两个部分，分别进行递归排序，然后再将两个有序的子数组合并成一个有序的数组。
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
归并排序可以在很多实际应用中发挥作用，例如在文件排序、数据库排序等领域都有着广泛的应用。
2.3 堆排序堆排序是一种利用堆这种数据结构进行排序的算法，其基本思想是通过建立一个大顶堆或小顶堆，然后将堆顶元素与最后一个元素交换，并调整堆，再将堆顶元素与倒数第二个元素交换，以此类推，直到所有元素都有序。
堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。
堆排序在优先队列、事件排序等领域有着广泛的应用。
2.4 计数排序计数排序是一种非比较排序算法，其基本思想是通过对待排序数组进行统计，然后根据统计信息将元素放置到正确的位置上。
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
冒泡法：这是最原始，也是众所周知的最慢的算法了。
他的名字的由来因为它的工作看来象是冒泡：复杂度为O(n*n)。
当数据为正序，将不会有交换。
复杂度为O(0)。
直接插入排序：O(n*n)选择排序：O(n*n)快速排序：平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情况下总是最好的。
归并排序：l og2(n)*n堆排序：l og2(n)*n希尔排序：算法的复杂度为n的1.2次幂这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况1.数组的大小是2的幂，这样分下去始终可以被2整除。
假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n所以算法复杂度为O(lo g2(n)*n) 其他的情况只会比这种情况差，最差的情况是每次选择到的midd le都是最小值或最大值，那么他将变成交换法（由于使用了递归，情况更糟）。
但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。
实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。
排序题方法总结
排序方法可以总结为以下几种：
1. 冒泡排序：重复比较相邻的两个元素，若顺序错误则交换位置，直至整个数组有序。
时间复杂度为O(n^2)。
2. 选择排序：每次从数组中选择最小（或最大）的元素，放到已排序的末尾，直至整个数组有序。
时间复杂度为O(n^2)。
3. 插入排序：将数组分为已排序和未排序两部分，每次从未排序部分中取出一个元素，并插入到已排序部分的适当位置，直至整个数组有序。
时间复杂度为O(n^2)。
4. 归并排序：将数组不断地分割成更小的子数组，然后再将子数组合并，直至整个数组有序。
时间复杂度为O(nlogn)。
5. 快速排序：选择一个基准元素，将数组分为小于和大于基准元素的两部分，再对两部分分别进行快速排序，直至整个数组有序。
时间复杂度为O(nlogn)。
6. 堆排序：将数组构建成大顶堆（或小顶堆），然后不断地将堆顶元素与最后一个元素交换，并重新调整堆，直至整个数组有序。
时间复杂度为O(nlogn)。
7. 计数排序：统计数组中每个元素出现的次数，然后根据计数从小到大将元素重新排列。
时间复杂度为O(n+k)，其中k是值的范围。
8. 基数排序：按照位数从低到高的顺序，将数组分配到桶中，然后重组桶中的元素，直至整个数组有序。
时间复杂度为
O(d*(n+k))，其中d是最大位数，k是每个桶的大小。
以上是常见的排序算法，每种算法都有不同的适用场景和特点，需要根据实际问题选择合适的算法。
排序算法十大经典方法
排序算法是计算机科学中的经典问题之一，它们用于将一组元素按照一定规则排序。
以下是十大经典排序算法：
1. 冒泡排序：比较相邻元素并交换，每一轮将最大的元素移动到最后。
2. 选择排序：每一轮选出未排序部分中最小的元素，并将其放在已排序部分的末尾。
3. 插入排序：将未排序部分的第一个元素插入到已排序部分的合适位置。
4. 希尔排序：改进的插入排序，将数据分组排序，最终合并排序。
5. 归并排序：将序列拆分成子序列，分别排序后合并，递归完成。
6. 快速排序：选定一个基准值，将小于基准值的元素放在左边，大于基准值的元素放在右边，递归排序。
7. 堆排序：将序列构建成一个堆，然后一次将堆顶元素取出并调整堆。
8. 计数排序：统计每个元素出现的次数，再按照元素大小输出。
9. 桶排序：将数据分到一个或多个桶中，对每个桶进行排序，最后输出。
10. 基数排序：按照元素的位数从低到高进行排序，每次排序只考虑一位。
以上是十大经典排序算法，每个算法都有其优缺点和适用场景，选择合适的算法可以提高排序效率。
10大排序方法10大排序方法在计算机科学和数据处理中，排序是一项基础且重要的任务。
通过排序，我们可以将一组数据按照特定规则进行排列，使得数据更易于查找和分析。
下面介绍了10种常用的排序方法，它们在不同场景下具有不同的优势和适用性。
1. 冒泡排序（Bubble Sort）冒泡排序是一种简单而直观的排序算法，它通过重复地比较相邻元素并交换位置来实现排序。
该算法的核心思想是将较大的元素逐渐“冒泡”到数列的末尾。
2. 选择排序（Selection Sort）选择排序的思想是从待排序的数据中选择出最小（或最大）的元素，放在已排序序列的末尾。
该过程不断重复，直到所有元素排序完成。
3. 插入排序（Insertion Sort）插入排序是一种简单且高效的排序算法，它的基本思想是将待排序数据分为已排序和未排序两部分，每次从未排序数据中取出一个元素，将其插入到已排序数据的合适位置。
希尔排序是插入排序的改进版本，它通过使用不同的间隔序列对数据进行多次分组排序，最终实现整体有序。
希尔排序在处理中等大小的数据集时具有较好的性能。
5. 归并排序（Merge Sort）归并排序是一种分治法的典型应用，它将待排序数据不断地分割成小块，然后逐步合并这些小块，以得到完整的有序序列。
归并排序在处理大规模数据时具有较好的稳定性和效率。
6. 快速排序（Quick Sort）快速排序是一种高效的排序算法，它采用分治的思想，通过选取一个基准元素将数据分为左右两部分，并分别对左右两部分进行排序。
快速排序通常是性能最好的排序算法之一。
7. 堆排序（Heap Sort）堆排序是利用堆这种数据结构的一种排序算法。
它通过建立最大（或最小）堆，并不断从堆顶取出最大（或最小）元素，实现排序的过程。
堆排序在处理大规模数据时具有较好的性能。
8. 计数排序（Counting Sort）计数排序是一种非比较性的排序算法，适用于数据范围较小且取值离散的情况。
计数排序通过统计每个元素出现的次数，从而确定每个元素在有序序列中的位置。
排序算法总结排序算法是计算机科学中的一种基本算法，其目的是将一组数据按照一定规则进行排序，以便于后续的查找、统计和分析。
排序算法应用广泛，例如在数据库的索引、数据压缩、图形处理等领域都有重要的作用。
常见的排序算法可以分为两大类：比较排序和非比较排序。
比较排序通过比较元素的大小来确定元素的相对顺序，而非比较排序则不需要通过比较来确定元素的相对顺序。
比较排序算法的时间复杂度通常为O(nlogn)，其中n表示待排序的元素个数。
最常见的比较排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等。
这些算法的实现思路各不相同，但都是通过比较元素的大小来实现排序的。
冒泡排序是一种简单同时也是一种经典的比较排序算法。
其基本思想是从待排序的数据元素序列的起始端开始，依次比较两个相邻的元素，若前者大于后者，则交换这两个元素，直到整个序列的最大元素被排到了最后的位置。
然后，再针对剩余的元素重复该过程，直到整个序列都有序为止。
插入排序是一种简单而有效的比较排序算法。
其基本思想也是将待排序的数据元素序列分为两部分，一部分是已经排序好的元素，另一部分是待排序的元素。
然后，逐个将待排序的元素插入已排序的元素序列中，直到所有的元素都插入完成。
选择排序是一种简单而直观的比较排序算法。
其基本思想是将待排序的数据元素序列划分为已排序的元素和未排序的元素两部分，然后每次从未排序的元素中选取最小的元素，将其放置到已排序的元素序列的末尾。
如此重复，直到所有的元素都被放置到已排序的元素序列中。
快速排序是一种高效的比较排序算法，也是最常用的排序算法之一。
其基本思想是通过一趟排序将待排序的元素序列划分成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小，然后再按照此方法对这两部分分别进行快速排序，最后将两部分排序好的元素序列拼接起来。
归并排序是一种稳定的比较排序算法，其基本思想是将待排序的元素序列分成两个长度相等的子序列，然后递归地对这两个子序列进行排序，最后再将这两个排好序的子序列逐个合并起来。
排序算法总结导读：范文排序算法总结【篇一：排序算法总结】1、稳定排序和非稳定排序简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。
反之，就是非稳定的。
比如：一组数排序前是a1，a2，a3，a4，a5，其中a2=a4，经过某种排序后为a1，a2，a4，a3，a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。
假如变成a1，a4，a2，a3，a5就不是稳定的了。
2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
3、算法的时间复杂度和空间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
功能：选择排序输入：数组名称、数组中元素个数算法思想简单描述：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。
【篇二：排序算法总结】在计算机科学所使用的排序算法通常被分类为：计算的复杂度，依据列表的大小。
一般而言，好的性能是O，且坏的性能是O。
对于一个排序理想的性能是O。
仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O。
内存使用量稳定度：稳定排序算法会依照相等的关键维持纪录的相对次序。
也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
一般的方法：插入、交换、选择、合并等等。
交换排序包含冒泡排序和快速排序。
选择排序包含希尔排序和堆排序【篇三：排序算法的总结】基数、冒泡、插入、简单选择、归并是稳定的，快速、堆、希尔是不稳定的。
一、插入排序一）直接插入排序定义：直接插入排序是一种最简单的排序方法。
它的基本操作是将一个记录插入到一个长度为m的有序表中，使之仍保持有序，从而得到一个新的长度为m＋1的有序表。
算法思路：设有一组关键字｛K1，K2，…，Kn｝；排序开始就认为K1是一个有序序列；让K2插入上述表长为1的有序序列，使之成为一个表长为2的有序序列；然后让K3插入上述表长为2的有序序列，使之成为一个表长为3的有序序列；依次类推，最后让Kn插入上述表长为n-1的有序序列，得一个表长为n的有序序列。
算法时间复杂度：此算法外循环n-1次，在一般情况下内循环平均比较次数的数量级为Ｏ，所以算法总时间复杂度为Ｏ。
直接插入排序的稳定性：直接插入排序是稳定的排序方法二）折半插入排序定义：当直接插入排序进行到某一趟时，对于r【i】。
key来讲，前边i-1个记录已经按关键字有序。
此时不用直接插入排序的方法，而改为折半查找，找出r【i】。
key应插的位置，然后插入。
三）2-路插入排序四）表插入排序五）希尔排序定义：希尔排序是D．Ｌ．希尔提出的“缩小增量”的排序方法。
它的作法不是每次一个元素挨一个元素的比较。
而是初期选用大跨步间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为1，这样记录移动次数大大减少，提高了排序效率。
希尔排序对增量序列的选择没有严格规定。
算法思路：①。
先取一个正整数d1，把全部记录分成d1个组，所有距离为d1的倍数的记录看成一组，然后在各组内进行插入排序；②。
然后取d2。
③。
重复上述分组和排序操作；直到取di=1，即所有记录成为一个组为止。
一般选d1约为n/2，d2为d1/2，d3为d2/2，…，di=1。
二、交换排序交换排序主要是根据记录的关键字的大小，将记录交换来进行排序的。
交换排序的特点是：将关键字值较大的记录向序列的后部移动，关键字较小的记录向前移动。
这里介绍两种交换排序方法，它们是冒泡排序和快速排序。
一）冒泡排序将被排序的记录数组R【1、n】垂直排列，每个记录R【i】看作是重量为R【i】。
key的气泡。
根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。
如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
1、算法思路让j取n至2，将r【j】。
key与r【j-1】。
key比较，如果r 【j】。
key【j-1】。
key，则把记录r【j】与r【j-1】交换位置，否则不进行交换。
最后是r【2】。
key与r【1】。
key对比，关键字较小的记录就换到r【1】的位置上，到此第一趟结束。
最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的前边。
让j取n至3，重复上述的比较对换操作，最终r【2】之中存放的是剩余n-1个记录中关键字最小的记录。
让j取n至i+1，经过一系列对联对比交换之后，r【i】之中是剩余若干记录中关键字最小的记录。
让j取n至n-1，将r【n】。
key与r【n-1】。
key对比，把关键字较小的记录交换到r【n-1】之中。
算法时间复杂度：该算法的时间复杂度为O。
但是，当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O。
二）快速排序快速排序由霍尔提出，它是一种对冒泡排序的改正。
由于其排序速度快，故称快速排序。
快速排序方法的实质是将一组关键字【K1，K2，…，Kn】进行分区交换排序。
算法思路①以第一个关键字K1为控制字，将【K1，K2，…，Kn】分成两个子区，使左区所有关键字小于等于K1，右区所有关键字大于等于K1，最后控制字居两个子区中间的适当位置。
在子区内数据尚处于无序状态。
②将右区首、尾指针保存入栈，对左区进行与第①步相类似的处理，又得到它的左子区和右子区，控制字居中。
③重复第①、②步，直到左区处理完毕。
然后退栈对一个个右子区进行相类似的处理，直到栈空。
由以上三步可以看出：快速排序算法总框架是进行多趟的分区处理；而对某一特定子区，则应把它看成又是一个待排序的文件，控制字总是取子区中第一个记录的关键字。
现在设计一个函数hoare，它仅对某一待排序文件进行左、右子区的划分，使控制字居中；再设计一个主体框架函数quicksort，在这里多次调用hoare函数以实现对整个文件的排序。
快速排序主体算法时间运算量约O，划分子区函数运算量约O，所以总的时间复杂度为O，它显然优于冒泡排序O。
三、选择排序选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
一）简单选择排序简单选择排序也是直接选择排序。
此方法在一些高级语言课程中做过介绍，是一种较为容易理解的方法。
算法思想：对于一组关键字{K1，K2，…，Kn}，首先从K1，K2，…，Kn中选择最小值，假如它是Kz，则将Kz与K1对换；然后从K2，K3，…，Kn中选择最小值Kz，再将Kz与K2对换。
如此进行选择和调换n-2趟，第趟，从Kn-1、Kn中选择最小值Kz将Kz与Kn-1对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成。
即：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。
该算法的时间复杂度为O。
并且排序是稳定的。
二）堆排序定义：树形选择排序，1964年威洛姆斯提出了进一步改正的排序方法，即堆排序。
堆是n个元素的有限序列{K1，K2，…，Kn}，它当且仅当满足如下关系：这是一个上小、底大的堆。
若是一个上大、底小的堆，只需把“=”即可。
堆是一种数据元素之间的逻辑关系，常用向量做存储结构。
对于满二叉树，当对它的结点由上而下，自左至右编号之后，编号为i 的结点是编号为2i和2i+1结点的双亲。
反过来讲，结点2i是结点i的左孩子，结点2i+1是结点i的右孩子。
图9、7表示完全二叉树和它在向量中的存储状态。
结点编号对应向量中的下标号。
用堆的概念分析向量中的数据，它显然满足堆的关系。
不难看出满足堆的逻辑关系的一组数据，可画成二叉树的形状，并且它是一棵完全二叉树树形。
因此，也可借助完全二叉树来描述堆的概念。
若完全二叉树中任一非叶子结点的值小于等于其左、右孩子结点的值，则从根结点开始按结点编号排列所得的结点序列就是一个堆。
在图9、8中、是堆，、不是堆。
堆排序的算法思想：堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简单。
用大根堆排序的基本思想①。
先将初始文件R【1、n】建成一个大根堆，此堆为初始的无序区②。
再将关键字最大的记录R【1】和无序区的最后一个记录R 【n】交换，由此得到新的无序区R【1、n-1】和有序区R【n】，且满足R【1、n-1】。
keys≤R【n】。
key③。
由于交换后新的根R【1】可能违反堆性质，故应将当前无序区R【1、n-1】调整为堆。
然后再次将R【1、n-1】中关键字最大的记录R【1】和该区间的最后一个记录R【n-1】交换，由此得到新的无序区R【1、n-2】和有序区R【n-1、n】，且仍满足关系R【1、n-2】。
keys≤R【n-1、n】。
keys，同样要将R【1、n-2】调整为堆。
④。
……⑤。
直到无序区只有一个元素为止。
大根堆排序算法的基本操作：①初始化操作：将R【1、n】构造为初始堆；②每一趟排序的基本操作：将当前无序区的堆顶记录R【1】和该区间的最后一个记录交换，然后将新的无序区调整为堆。
注意：①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。
堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的树高度log2n相关。
而heapsort中对heap的调用数量级为n，所以堆排序的整个时间复杂度为O。
并且堆排序是不稳定的。
四、归并排序归并排序是一类与插入排序、交换排序、选择排序不同的另一种排序方法。
归并的含义是将两个或两个以上的有序表合并成一个新的有序表。
归并排序有多路归并排序、两路归并排序，可用于内排序，也可以用于外排序。
这里仅对内排序的两路归并方法进行讨论。
两路归并排序算法思路：①。
把n个记录看成n个长度为l的有序子表；②。
进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表；③。
重复第②步直到所有记录归并成一个长度为n的有序表为止。
算法实现：此算法的实现不像图示那样简单，现分三步来讨论。
首先从宏观上分析，首先让子表表长L=1进行处理；不断地使L=2*L，进行子表处理，直到L>=n为止，把这一过程写成一个主体框架函数mergesort。
