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

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

按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为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 = 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这二个子区间重复上述步骤就可以了

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

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

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

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

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

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

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

一、八大排序算法的总体比较

二、算法各自的特点（具体实现见后面博客）

1.快排

（1）算法思想

选择一个基准元素，将比基准元素小的元素放在其前面，比基准元素大的元素放在其后面，然后在将小于基准值元素的子数列和大于基准元素的子数列按原来的方法排序，直到整个序列有序;

（2）优缺点

优点：极快数据移动少；

缺点：不稳定；

（3）效率分析

此排序算法的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序；

（4）对于基准的选择

a.三数取中

具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴；

b.随机选取基准

引入原因：在待排序列是部分有序时，固定选取枢轴使快排效率低下；

具体思想：取在待排序列中任意一个元素作为基准；

（5）优化方法

a.当待排序序列的长度分割到一定大小后，使用插入排序；

原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排；

b.在一次分割结束后，可以把与key相等的元素聚集在一起，继续下次分割时，不必再对于key相等元素分割；

（6）应用场景

 a.求数组中第k小的数

将数组中某一个元素m作为划分依据,即m=arr。若m前面的元素个数大于k，则第k小的数一定在m前面的元素中，这时我们只需要继续在m前面的元素中找第k小的数；若m前面的元素小于k，则第k小的数一定在m后面的元素中，这时我们只需要在m后面的元素中找第k小的数；

2.冒泡排序

（1）基本原理

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。

（2）优缺点

优点：稳定

缺点：慢，每次只能移动两个相邻的数据；

3.插入排序

（1）基本思想

将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。即先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。

（2）优缺点

优点：稳定，快

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是数据量庞大的时候

4.堆排序

4.1、二叉堆定义：

二叉堆是完全二叉树或近似完全二叉树。二叉堆满足两个特性:

（1）父结点的键值总是大于或者等于（小于或者等于）任何一个子节点的键值；

（2）每个结点的左子树和右子树都是一个二叉堆；

当父结点的键值总是大于或者等于任何一个子节点的键值时为大根堆。当父结点的键值总是小于或等于任何一个子节点的键值时为小根堆；

4.2、堆的存储：

一般都用数组来表示堆，i结点的父结点下标就为（i-1）/2.它的左右子节点的下标分别为2*i+1和2*i+2.

4.3、堆的插入：

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中

（1）用大根堆排序的基本思想

先将初始数组建成一个大根堆，此对为初始的无序区；

再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足《=的值；

由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值《=的值，同样要将其调整为堆；

..........

直到无序区只有一个元素为止；

4.4：应用

寻找M个数中的前K个最小的数并保持有序；

时间复杂度：O(K)

5.希尔排序

（1）基本思想

先将整个待排序元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）；

（2）适用场景

比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；

6.归并排序

（1）基本思想

首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止；

（2）适用场景

若n较大，并且要求排序稳定，则可以选择归并排序；

7.简单选择排序

（1）基本思想

第一趟：从第一个记录开始，将后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；

第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；

...........

第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到其中最小的记录和第i个记录进行交换；

以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录直接排在最后；

#include 《iostream》#include 《stdio.h》#include《stdlib.h》 #include《time.h》   using namespace std;int bubble;int quickCount;int between(int* a, int low, int high);void quick(int a, int low, int high){ int value;if (low 《 high){value = between(a, low, high) ;quick (a, low, value-1 );//左边quick (a, value+1,high); //右边}} int between(int* a, int low, int high){int value = a;//中间值`while (low 《 high){while (low 《 high && a 》=value){quickCount++;high--;}a; while (low 《 high && a  《=value){low++;quickCount++; }a; }a = value;return low;}void Bbubble(int a,int length){int i;//少执行10次for(int x=0; x《length; x++)for(int y = x; y《length-1; y++){bubble++;if (a){    i  = a; a; a = i; }}//多执行10次/*for(int x=0; x《length; x++)for(int y = x; y《length; y++){bubble++;if (a){    i  = a;a;a = i;}}*/} void put(int a,int length){for (int i = 0; i《 length; i++){cout 《《 a 《《 “  “;}  cout 《《 endl;}int main(){int a = {1,3,4,2,5,6,7,8,9,0};int b = {1,3,4,2,5,6,7,8,9,0};Bbubble(a,10);quick(b,0,9);put(a,10);put(b,10);cout 《《 “Bbubble “《《 bubble《《endl;cout 《《 “quick “  《《 quickCount 《《endl;return 0;}

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

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

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

public static void Swap(int A, int i, int j){

int tmp;

tmp = A;

A;

A = tmp;

扩展资料：

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

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

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

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

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

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

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

#include《iostream》using namespace std;//插入排序--直接插入排序void insert_sort(int v,int lenth){ int i,j; for(i=1;i《lenth;i++) { int tem = v; for(j=i-1;j》=0&&tem《v;j--) v; v = tem; }}//插入排序--shell（希尔）排序（快速插入排序）void shell(int v,int lenth)//在直接插入排序的基础上分段做插入排序{ int i,j,step; for(step=lenth/2;step》=1;step=step/2) { for(i=step;i《lenth;i++) { int tem = v; for(j=i-step;j》=0&&tem《v;j=j-step) v; v = tem; } }}//交换排序--泡沫排序void bubble(int v,int lenth){ int i,j; for(i=1;i《lenth;i++) for(j=lenth-1;j》=i;j--)//从后向前，一次排序后较小的被排在前面 if(v) { int tem = v; v; v = tem; }}//交换排序--快速排序int partition(int v,int low,int high)//一种分段方法{ int i=low,j=high; int tem = v; while(i《j) { while(i《j&&v》=tem) j--; if(i《j) { v; } while(i《j&&v《=tem) i++; if(i《j) { v; } } v =tem; return i;}void quicksort(int v,int low,int high){ int point; if(low《high) { point = partition(v,low,high); quicksort(v,low,point-1); quicksort(v,point+1,high); }}//选择排序--直接选择排序void select(int v,int lenth){ int i,j; int tem_data; int tem_i; for(i=0;i《lenth;i++) { tem_data = v; tem_i = i; for(j=i+1;j《lenth;j++) if(v《tem_data) { tem_data = v; tem_i = j; } if(i!=tem_i) { v; v = tem_data; } }}void show(int v,int lenth){ int i; for(i=0;i《10;i++) cout《《v《《“ “;}int main(void){ int a = {10,49,38,65,97,76,3,49,27,1}; cout《《endl《《“insert_sort:“《《endl; insert_sort(a,10); show(a,10); int b = {10,49,38,65,97,76,3,49,27,1}; cout《《endl《《“shell sort“《《endl; shell(b,10); show(b,10); int c = {10,49,38,65,97,76,3,49,27,1}; cout《《endl《《“bubble sort“《《endl; bubble(c,10); show(c,10); int d = {10,49,38,65,97,76,3,49,27,1}; cout《《endl《《“quicksort:“《《endl; quicksort(d,0,9); show(d,10); int e = {10,49,38,65,97,76,3,49,27,1}; cout《《endl《《“select order:“《《endl; select(e,10); show(e,10);}

一、简单排序算法　　由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境　　下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么　　问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。1.冒泡法：　　这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：　　#include 《iostream》　　using namespace std;　　void BubbleSort(int * pData, int Count)　　{　　int iTemp;　　for (int i=0; i《Count; i++)　　{　　for (int j=Count-1; j》i; j--)　　{　　if (pData)　　{　　iTemp = pData;　　pData;　　pData = iTemp;　　}　　}　　}　　}　　void main()　　{　　int data = {10,9,8,7,6,5,4};　　BubbleSort(data,7);　　for (int i=0; i《7; i++)　　{　　cout《《data《《“ “;　　}　　cout《《endl;　　system(“PAUSE“);　　}　　倒序(最糟情况)　　第一轮：10，9，8，7-》10，9，7，8-》10，7，9，8-》7，10，9，8(交换3次)　　第二轮：7，10，9，8-》7，10，8，9-》7，8，10，9(交换2次)　　第一轮：7，8，10，9-》7，8，9，10(交换1次)　　循环次数：6次　　交换次数：6次　　其他：　　第一轮：8，10，7，9-》8，10，7，9-》8，7，10，9-》7，8，10，9(交换2次)　　第二轮：7，8，10，9-》7，8，10，9-》7，8，10，9(交换0次)　　第一轮：7，8，10，9-》7，8，9，10(交换1次)　　循环次数：6次　　交换次数：3次　　上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，　　显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。　　写成公式就是1/2*(n-1)*n。　　现在注意，我们给出O方法的定义：　　若存在一常量K和起点n0，使当n》=n0时，有f(n)《=K*g(n)，则f(n) = O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）　　现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n《=1/2*n*n=K*g(n)。所以f(n)　　=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。　　再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的　　有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），　　复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的　　原因，我们通常都是通过循环次数来对比算法。2.交换法：　　交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。　　#include 《iostream.h》　　void ExchangeSort(int* pData，int Count)　　{　　int iTemp;　　for(int i=0;i《Count-1;i++)　　{ //共（count-1)轮，每轮得到一个最小值　　for(int j=i+1;j《Count;j++)　　{ //每次从剩下的数字中寻找最小值，于当前最小值相比，如果小则交换　　if(pData9，10，8，7-》8，10，9，7-》7，10，9，8(交换3次)　　第二轮：7，10，9，8-》7，9，10，8-》7，8，10，9(交换2次)　　第一轮：7，8，10，9-》7，8，9，10(交换1次)　　循环次数：6次　　交换次数：6次　　其他：　　第一轮：8，10，7，9-》8，10，7，9-》7，10，8，9-》7，10，8，9(交换1次)　　第二轮：7，10，8，9-》7，8，10，9-》7，8，10，9(交换1次)　　第一轮：7，8，10，9-》7，8，9，10(交换1次)　　循环次数：6次　　交换次数：3次　　从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样　　也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以　　只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。3.选择法：　　现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）　　这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中　　选择最小的与第二个交换，这样往复下去。　　#include 《iostream.h》　　void SelectSort(int* pData，int Count)　　{　　int iTemp;　　int iPos;　　for(int i=0;i《Count-1;i++)　　{　　iTemp = pData;　　iPos = i;　　for(int j=i+1;j《Count;j++)　　{　　if(pData《iTemp)　　{　　iTemp = pData;　　iPos = j;　　}　　}　　pData = pData;　　pData = iTemp;　　}　　}　　void main()　　{　　int data = {10，9，8，7，6，5，4};　　SelectSort(data，7);　　for (int i=0;i《7;i++)　　cout《《data《《“ “;　　cout《《“\n“;　　}　　倒序(最糟情况)　　第一轮：10，9，8，7-》(iTemp=9)10，9，8，7-》(iTemp=8)10，9，8，7-》(iTemp=7)7，9，8，10(交换1次)　　第二轮：7，9，8，10-》7，9，8，10(iTemp=8)-》(iTemp=8)7，8，9，10(交换1次)　　第一轮：7，8，9，10-》(iTemp=9)7，8，9，10(交换0次)　　循环次数：6次　　交换次数：2次　　其他：　　第一轮：8，10，7，9-》(iTemp=8)8，10，7，9-》(iTemp=7)8，10，7，9-》(iTemp=7)7，10，8，9(交换1次)　　第二轮：7，10，8，9-》(iTemp=8)7，10，8，9-》(iTemp=8)7，8，10，9(交换1次)　　第一轮：7，8，10，9-》(iTemp=9)7，8，9，10(交换1次)　　循环次数：6次　　交换次数：3次　　遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。　　我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)《=n　　所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。4.插入法：　　插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张　　#include 《iostream.h》　　void InsertSort(int* pData，int Count)　　{　　int iTemp;　　int iPos;　　for(int i=1;i《Count;i++)　　{　　iTemp = pData; //保存要插入的数　　iPos = i-1; //被插入的数组数字个数　　while((iPos》=0) && (iTemp9，10，8，7(交换1次)(循环1次)　　第二轮：9，10，8，7-》8，9，10，7(交换1次)(循环2次)　　第一轮：8，9，10，7-》7，8，9，10(交换1次)(循环3次)　　循环次数：6次　　交换次数：3次　　其他：　　第一轮：8，10，7，9-》8，10，7，9(交换0次)(循环1次)　　第二轮：8，10，7，9-》7，8，10，9(交换1次)(循环2次)　　第一轮：7，8，10，9-》7，8，9，10(交换1次)(循环1次)　　循环次数：4次　　交换次数：2次　　上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，　　因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)《=　　1/2*n*(n-1)《=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单　　排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似　　选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’　　而这里显然多了一些，所以我们浪费了时间。　　最终，我个人认为，在简单排序算法中，选择法是最好的。二、高级排序算法　　高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。　　它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后　　把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使　　用这个过程（最容易的方法——递归）。　　1.快速排序：　　#include 《iostream.h》　　void run(int* pData，int left，int right)　　{　　int i，j;　　int middle，iTemp;　　i = left;　　j = right;　　middle = pData;　　do{　　while((pData《middle) && (i《right))//从左扫描大于中值的数　　i++;　　　while((pData》middle) && (j》left))//从右扫描大于中值的数　　j--;　　if(i《=j)//找到了一对值　　{　　//交换　　iTemp = pData;　　pData;　　pData = iTemp;　　i++;　　j--;　　}　　}while(i《=j);//如果两边扫描的下标交错，就停止（完成一次）　　//当左边部分有值(left《j)，递归左半边　　if(left《j)　　run(pData，left，j);　　//当右边部分有值(right》i)，递归右半边　　if(right》i)　　run(pData，i，right);　　}　　void QuickSort(int* pData，int Count)　　{　　run(pData，0，Count-1);　　}　　void main()　　{　　int data = {10，9，8，7，6，5，4};　　QuickSort(data，7);　　for (int i=0;i《7;i++)　　cout《《data《《“ “;　　cout《《“\n“;　　}　　这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况　　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(log2(n)*n)　　其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变　　成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全　　不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。　　如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢

小朋友啊，你这不是问题是作业啊。

插入排序n*n、希尔排序《=n*n、起泡排序《=n*n、快速排序n*log2n、选择排序=n*n、堆排序n*log2n、归并排序n*n