简单排序及顺序查找算法及实现

① 各种排序算法实现和比较

1、 堆排序定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
注意：
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。
4、堆排序与直接插入排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
5、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
（1）用大根堆排序的基本思想
① 先将初始文件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]调整为堆。
……
直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
（3）堆排序的算法：
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i；
BuildHeap(R)； //将R[1-n]建成初始堆
for(i=n;i1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换
Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
} //endfor
} //HeapSort
（4） BuildHeap和Heapify函数的实现
因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。
① Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。
"筛选法"调整堆
R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。
具体的算法
②BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，…，1的结点作为根的子树都调整为堆即可。
具体算法。
5、大根堆排序实例
对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参见。
6、 算法分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。

② 快速排序算法原理与实现

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边。

然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

以下的代码中会常常使用交换数组中两个元素值的Swap方法，其代码如下

publicstaticvoidSwap(int[] A, inti, intj){

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(2)简单排序及顺序查找算法及实现扩展阅读：

快速排序算法 的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通 常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划 分序列的起始元素决定。

从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值 为 key。

③ 数据查找和排序

java:
Java排序算法
package com.cucu.test;

/**
* @author http://www.linewell.com <a href=mailto:[email protected]>[email protected]</a>
* @version 1.0
*/
public class Sort {

public void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

public int partition(int a[], int low, int high) {
int pivot, p_pos, i;
p_pos = low;
pivot = a[p_pos];
for (i = low + 1; i <= high; i++) {
if (a[i] > pivot) {
p_pos++;
swap(a, p_pos, i);
}
}
swap(a, low, p_pos);
return p_pos;
}

public void quicksort(int a[], int low, int high) {
int pivot;
if (low < high) {
pivot = partition(a, low, high);
quicksort(a, low, pivot - 1);
quicksort(a, pivot + 1, high);
}

}

public static void main(String args[]) {
int vec[] = new int[] { 37, 47, 23, -5, 19, 56 };
int temp;
//选择排序法(Selection Sort)
long begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length; j++) {
if (vec[j] > vec[i]) {
temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
}
}

}
}
long end = System.currentTimeMillis();
System.out.println("选择法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
// 冒泡排序法(Bubble Sort)
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length - 1; j++) {
if (vec[j + 1] > vec[j]) {
temp = vec[j + 1];
vec[j + 1] = vec[j];
vec[j] = temp;
}
}

}
}
end = System.currentTimeMillis();
System.out.println("冒泡法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}

//插入排序法(Insertion Sort)
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 1; i < vec.length; i++) {
int j = i;
while (vec[j - 1] < vec[i]) {
vec[j] = vec[j - 1];
j--;
if (j <= 0) {
break;
}
}
vec[j] = vec[i];
}
}
end = System.currentTimeMillis();
System.out.println("插入法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}

//快速排序法(Quick Sort)

Sort s = new Sort();
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
s.quicksort(vec, 0, 5);
}
end = System.currentTimeMillis();
System.out.println("快速法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
}

}
以下是运行结果：
选择法用时为：234
56
47
37
23
19
-5
冒泡法用时为：172
56
47
37
23
19
-5
插入法用时为：78
56
47
37
23
19
-5
快速法用时为：297
56
47
37
23
19
-5

④ 八大经典排序算法原理及实现

该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记录，每篇头部主要是另起博客的链接。

冒泡排序算法应该是大家第一个接触的算法，其原理都应该懂，但我还是想以自己的语言来叙述下其步奏：

按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2)
冒泡排序及其复杂度分析

空间复杂度就是在交换元素时那个临时变量所占的内存

给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为：

我们发现第一次外层循环之后就排序成功了，但是还是会继续循环下去，造成了不必要的时间复杂度，怎么优化？

冒泡排序都是相邻元素的比较，当相邻元素相等时并不会交换，因此冒泡排序算法是稳定性算法

插入排序是对冒泡排序的一种改进

插入排序的思想是数组是部分有序的，再将无序的部分插入有序的部分中去,如图：
（图片来自 这里 ）

空间复杂度就是在交换元素时那个临时变量所占的内存

插入排序的优化，有两种方案：

文章后面会给出这两种排序算法

由于插入排序也是相邻元素的比较，遇到相等的相邻元素时不会发生交换，也不会造成相等元素之间的相对位置发生变化

其原理是从未排序的元素中选出最小值(最大值)放在已排序元素的后面

空间复杂度就是在交换元素时那个临时变量所占的内存

选择排序是不稳定的，比如 3 6 3 2 4，第一次外层循环中就会交换第一个元素3和第四个元素2，那么就会导致原序列的两个3的相对位置发生变化

希尔排序算是改良版的插入排序算法，所以也称为希尔插入排序算法

其原理是将序列分割成若干子序列（由相隔某个 增量 的元素组成的），分别进行直接插入排序；接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序，我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理，真正的实现可以按下述步奏来：

希尔排序的效率取决于 增量值gap 的选取，这涉及到数学上尚未解决的难题，但是某些序列中复杂度可以为O(N 1.3)，当然最好肯定是O(N)，最坏是O(N 2)

空间复杂度就是在交换元素时那个临时变量所占的内存

希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化，所以希尔排序是不稳定的

理解堆排序，就必须得先知道什么是堆？

二叉树的特点：

当父节点的值总是大于子结点时为 最大堆 ；反之为 最小堆 ，下图就为一个二叉堆

一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2 i + 1)、(2 i + 2)

怎么将给定的数组序列按照堆的性质，调整为堆？

这里以建立最小堆为示例，

很明显对于其叶子结点来说，已经是一个合法的子堆，所以做堆调整时，子节点没有必要进行，这里只需从结点为A[4] = 50的结点开始做堆调整，即从（n/2 - 1）位置处向上开始做堆调整：

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)，二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N * logN)。

空间复杂度就是在交换元素时那个临时变量所占的内存

由于堆排序也是跨越式的交换数据，会导致相同元素之间的相对位置发生变化，则算法不稳定。比如 5 5 5 ,堆化数组后将堆顶元素5与堆尾元素5交换，使得第一个5和第三个5的相对位置发生变化

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

快速排序在应该是大家经常看到、听到的算法，但是真正默写出来是有难度的。希望大家看了下面 挖坑填数 方法后，能快速写出、快速排序。

其原理就这么几句话，但是现实起来并不是这么简单，我们采取流行的一种方式 挖坑填数分治法

对于序列： 72 6 57 88 60 42 83 73 48 85

数组变为： 48 6 57 88 60 42 83 73 88 85
再重复上面的步骤，先从后向前找，再从前向后找：

数组变为： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了

空间复杂度，主要是递归造成的栈空间的使用:

快速排序的优化主要在于基准数的选取

快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定

前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定
具体步骤，设数组为a[0…n]：

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
所以，二分查找排序比较次数为：x=log2n
二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

二分查找排序在交换数据时时进行移动，当遇到有相等值插入时也只会插入其后面，不会影响其相等元素之间的相对位置，所以是稳定的

白话经典算法排序
冒泡排序选择排序
快速排序复杂度分析
优化的插入排序

⑤ 排序算法是怎样的

一、背景介绍

在计算机科学与数学中，排序算法（Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。

最常用到的排序方式是数字顺序以及字典顺序。

有效的排序算法在一些算法（例如搜寻算法与合并算法）中是重要的， 如此这些算法才能得到正确解答。

排序算法也用在处理文字资料以及产生人类可读的输出结果。

基本上，排序算法的输出必须遵守下列两个原则：

1、输出结果为递增序列（递增是针对所需的排序顺序而言）；

2、输出结果是原输入的一种排列、或是重组；

虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。 更多的新算法仍在不断的被发明。

二、知识剖析

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。 所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。

一般在面试中最常考的是快速排序和冒泡排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。除此之外，还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。

三、常见的几种算法：

冒泡算法、选择排序、插入排序、希尔排序、归并排序、快速排序

算法的特点：

1、有限性：一个算法必须保证执行有限步之后结束。

2、确切性： 一个算法的每一步骤必须有确切的定义。

3、输入：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件。

4、输出：一个算法有一个或多个输出。没有输出的算法毫无意义。

5、可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

⑥ 常见查找和排序算法

查找成功最多要n 次，平均（n+1）/2次， 时间复杂度为O(n) 。
优点：既适用顺序表也适用单链表，同时对表中元素顺序无要求，给插入带来方便，只需插入表尾即可。
缺点：速度较慢。

改进：在表尾设置一个岗哨，这样不用去循环判断数组下标是否越界，因为最后必然成立。

适用条件：

二分查找的判定树不仅是二叉排序树，而且是一棵理想平衡树。 时间复杂度为O(lbn) 。

循环实现

递归实现

待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 ~N2/2 次比较和 ~N 次交换，==它的运行时间与输入无关==，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

从左到右不断 交换相邻逆序的元素 ，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

每次都 将当前元素插入到左侧已经排序的数组中 ，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

==插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低==。

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并方法将数组中两个已经排序的部分归并成一个。

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

先归并那些微型数组，然后成对归并得到的微型数组。

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 大的元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

将新元素放到数组末尾，然后上浮到合适的位置。

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，==计数排序要求输入的数据必须是有确定范围的整数==。

当输入的元素是 n 个 0 到 k 之间的整数时，它的==运行时间是 O(n + k)==。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。比较适合用来排序==小范围非负整数数组的数组==。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

当输入数据均匀分配到每一个桶时最快，当都分配到同一个桶时最慢。

实间复杂度N*K

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。