排序算法汇总总结 - as_ - 博客园
随笔 - 150, 文章 - 0, 评论 - 80, 引用 - 0
一、插入排序
直接插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
代码实现：
#include &stdio.h&
#include &stdlib.h&
void swap(int *p1, int *p2)
void insertSort(int *a,int len)
for(i=0;i&i++)
for(j=i+1;j&=1;j--)
if(a[j]&a[j-1])
swap(&a[j],&a[j-1]);
希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。它的基本思想是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2&d1重复上述的分组和排序，直至所取的增量dt=1(dt&dt-l&&&d2&d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
代码实现：
#include &stdio.h&
#include &stdlib.h&
void swap(int *p1, int *p2) {
temp = *p1;
*p1 = *p2;
void shell(int *a, int d, int len) {
for (i = d - 1; i & i++) {
for (j = i + j &= i && j & j--) {
if (a[j] & a[j-d]) {
swap(&a[j], &a[j-d]);
void shellSort(int *a, int d, int len) {
while (d &= 1) {
shell(a, d, len);
d = d / 2;
二、交换排序
&冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢&浮&到数列的顶端。
代码实现：(swap函数同前 以后同)
void bubbleSort(int *a,int len)
for(i=0;i&i++)
for(j=len-1;j&i;j--)
if(a[j]&a[j-1])
swap(&a[j],&a[j-1]);
if(!change)
快速排序是由东尼&霍尔所发展的一种排序算法&& 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码实现：
int partition(int *a ,int s, int e)
int roll=a[s], i,
for (i=s+1,j=i&=e; i++)
if (a[i] & roll)
swap(&a[i],&a[j]);
swap(&a[s],&a[j-1]);
return j-1;
void quickSort(int *a, int start,int end)
if(start&=end)
int split=partition(a,start,end);
quickSort(a,start,split-1);
quickSort(a,split+1,end);
三、选择排序
直接选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾(目前已被排序的序列)。以此类推，直到所有元素均排序完毕。
代码实现：
void selectSort(int *a, int len)
int i,j,min,
for(i=0;i&i++)
for(j=i+1;j&j++)
if(a[j]&min)
if(min!=a[i])
swap(&a[i],&a[mark]);
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点
代码实现：
void shift(int *a,int r,int len)
for(j=r;j&=len/2;)
if(2*j&len && a[2*j]&a[j])
maxid=2*j;
if(2*j+1&len && a[2*j+1]&a[maxid])
maxid=2*j+1;
if(maxid!=j)
swap(&a[maxid],&a[j]);
void buildHeap(int *a, int len)
//为便宜计算 a的下标从1开始 构建大顶堆
for(i=len/2;i&0;i--)
shift(a,i,len);
void heapSort(int *a, int len)
buildHeap(a,len);
swap(&a[1],&a[len]);
for(clen=len-1;clen&0;clen--)
shift(a,1,clen);
swap(&a[1],&a[clen]);
四、归并排序
归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并操作的过程如下：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
代码实现：
void merge(int *a,int start,int mid,int end)
if(start&mid || mid &end ) return;
int i=start,j=mid+1,k=0;
int *L=(int *)malloc((end-start+1)*sizeof(int));
while(i&=mid && j&=end)
if(a[i]&a[j])
L[k++]=a[i++];
L[k++]=a[j++];
while(i&=mid)
L[k++]=a[i++];
while(j&=end)
L[k++]=a[j++];
for(i=start,j=0;i&=i++,j++)
a[i]=L[j];
void mergeSort(int *a, int start,int end)
if(start&end)
int mid=(start+end)/2;
mergeSort(a,start,mid);
mergeSort(a,mid+1,end);
merge(a,start,mid,end);
五、基数排序
基数排序(Radix sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
算法实现（未验证正确性）：
struct DNode
struct Table
int digit(int num,int loc)
for(int i=1;i&i++)
int res=num%10;
int maxCount(int *a,int len)
int max=0,n,
for(int i=0;i&i++)
while(num)
void radixSort(int *a,int len)
int maxloc=maxcount(a,len);
Table *t=(Table *)malloc(10 * sizeof(Table));
for(int i=0;i&10;i++)
t[i]-&id=i;
t[i]-&first=NULL;
for(int j=1;j&j++)
for(int k=0;k&k++)
int idm=digit(a[k],j);
DNode *p=t[idm]-&
while(pt-&next!=NULL)
DNode *d=(DNode *)malloc(sizeof(DNode));
d-&data=a[k];
d-&next=p-&
p-&next=d;
for(int i=0,k=0;i&=9;i++)
while(t[i]-&first!=NULL)
a[k--]=t[i]-&first-&
ptemp=t[i]-&
t[i]-&first=t[i]-&first-&
free(ptemp);
六、排序算法特点，算法复杂度和比较
直接插入排序
如果目标是把n个元素的序列升序排列，那么采用直接插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。直接插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说直接插入排序算法复杂度为O(n2)。因而，直接插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么直接插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。
希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法.
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的
时间复杂度为O（n^2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：1.&编程复杂度&很低，很容易写出代码；2.具有稳定性。
其中若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。
在最好的情况，每次我们执行一次分割，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递回调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作 log n 次巢状的调用。这个意思就是调用树的深度是O(log n)。但是在同一阶层的两个程序调用中，不会处理到原来数列的相同部份；因此，程序调用的每一阶层总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一阶层仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。
另外一个方法是为T(n)设立一个递回关系式，也就是需要排序大小为n的数列所需要的时间。在最好的情况下，因为一个单独的快速排序调用牵涉了O(n)的工作，加上对n/2大小之数列的两个递回调用，这个关系式可以是：
T(n) = O(n) + 2T(n/2)
解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。
事实上，并不需要把数列如此精确地分割；即使如果每个基准值将元素分开为 99% 在一边和 1% 在另一边，调用的深度仍然限制在 100log n，所以全部执行时间依然是O(n log n)。
然而，在最坏的情况是，两子数列拥有大各为 1 和 n-1，且调用树（call tree）变成为一个 n 个巢状（nested）呼叫的线性连串（chain）。第 i 次呼叫作了O(n-i)的工作量，且递回关系式为：
T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)
这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = O(n2)。
讨论平均复杂度情况下，即使如果我们无法随机地选择基准数值，对于它的输入之所有可能排列，快速排序仍然只需要O(n log n)时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来，除以n这个因子，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与乱数快速排序有一样的执行时间。
更精确地说，对于输入顺序之所有排列情形的平均比较次数，可以借由解出这个递回关系式可以精确地算出来。
在这里，n-1 是分割所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。
这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。这意味着，它比最坏情况较接近最好情况。这个快速的平均执行时间，是快速排序比其他排序算法有实际的优势之另一个原因。
讨论空间复杂度时 被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何递回呼叫前，仅会使用固定的額外空間。然而，如果需要产生O(log n)巢状递回呼叫，它需要在他们每一个储存一个固定数量的资讯。因为最好的情况最多需要O(log n)次的巢状递回呼叫，所以它需要O(log n)的空间。最坏情况下需要O(n)次巢状递回呼叫，因此需要O(n)的空间。
然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log2 n)空间的位元数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，因为如果一个数列大部份都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。
非原地版本的快速排序，在它的任何递回呼叫前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递回的每一阶中，使用与上一次所使用最多空间的一半，且
它的最坏情况是很恐怖的，需要
空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部份都是不同的，每一个将会需要大约O(log n)为原来储存，导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。
直接选择排序
选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。
比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
堆排序的平均时间复杂度为Ｏ(nlogn)，空间复杂度为Ｏ(1)。
由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为Ｏ(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。
归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。
基数排序的时间复杂度是 O(k&n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n&log(n))，因为k的大小一般会受到 n 的影响。 以排序n个不同整数来举例，假定这些整数以B为底，这样每位数都有B个不同的数字，k就一定不小于logB(n)。由于有B个不同的数字，所以就需要B个不同的桶，在每一轮比较的时候都需要平均n&log2(B) 次比较来把整数放到合适的桶中去，所以就有：
k 大于或等于 logB(n)
每一轮(平均)需要 n&log2(B) 次比较
所以，基数排序的平均时间T就是：
T & logB(n)&n&log2(B) = log2(n)&logB(2)&n&log2(B) = log2(n)&n&logB(2)&log2(B) = n&log2(n)
所以和比较排序相似，基数排序需要的比较次数：T & n&log2(n)。 故其时间复杂度为 &O(n&log2(n)) = &O(n&log n) 。
&七、不同条件下，排序方法的选择
(1)若n较小(如n&50)，可采用直接插入或直接选择排序。 &&& 　
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 &&& 　
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； &&& 　
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 &&& 　
若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的& 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。
(4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。 &&& 　
当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。 &&& 　
箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n)时间内完成对n个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合(例如实数型关键字)时，无法使用箱排序和基数排序，这时只有借助于"比较"的方法来排序。 &&& 　
若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要增加相应的时间。
(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。
(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0&i&n)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系： &&&&&&&
R[t[0]].key&R[t[1]].key&&&R[t[n-1]].key &
若要求最终结果是： &&&&&&
R[0].key&R[1].key&&&R[n-1].key
则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。
八、各排序算法时间复杂度和空间复杂度折半插入排序_百度百科
折半插入排序
本词条缺少名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！
折半插入排序（binary insertion sort）是对算法的一种改进，所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。
折半插入排序（binary insertion sort）是对算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。[1]
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low&=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。[1]
稳定性及复杂度
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比算法快，但记录移动的次数没有变，所以折半插入排序算法的仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。[1]
折半查找只是减少了比较次数，但是元素的移动次数不变，所以时间复杂度为O(n^2)是正确的！
#define _CRT_SECURE_NO_WARNINGS
#include &iostream&
#define LEN 8 // 有LEN个元素要排
struct Record { // 为了考察排序的稳定性，定义元素是
void BInsertSort(Record *arr, int length) // length是要排序的元素的个数，0号单元除外
for (int i = 2; i &= ++i) {
arr[0] = arr[i]; // 将arr[i]暂存到arr[0]
int low = 1;
int high = i - 1;
while (low &= high) { // 在arr[low..high]中折半查找有序插入的位置
int m = (low + high) / 2; // 折半
if (arr[0].key & arr[m].key) // 关键字相同时，使low = m + 1，到高半区，保证稳定性
high = m - 1; // 插入点在低半区
low = m + 1; // 插入点在高半区
for (int j = i - 1; j &= high + 1; --j)
arr[j + 1] = arr[j]; // 记录后移
arr[high + 1] = arr[0]; // 插入
int main()
(&in.txt&, &r&, stdin);
Record a[LEN + 1] = {0};
for (int i = 1; i &= LEN; i++)
cin && a[i].key && a[i].
BInsertSort(a, LEN);
for (int i = 1; i &= LEN; i++)
cout && a[i].key && '\t' && a[i].otherinfo &&
public class MyBinaryInsertionSort
public static void main(String[] args)
// 待排序的数组
int[] array = { 1, 0, 2, 5, 3, 4, 9, 8, 10, 6, 7};
binaryInsertSort();
// 显示排序后的结果。
System.out.print(&排序后： &);
for(int i = 0; i & array. i++)
System.out.print(array[i] + & &);
// Binary Insertion Sort method
private static void binaryInsertSort(int[] array)
for(int i = 1; i & array. i++)
int temp = array[i];
int low = 0;
int high = i - 1;
while(low &= high)
int mid = (low + high) / 2;
if(temp & array[mid])
high = mid - 1;
low = mid + 1;
for(int j = j &= low + 1; j--)
array[j] = array[j - 1];
array[low] =
#include &stdio.h&
typedef int ElemT
ElemType arr[]={0,9,8,7,6,5,4,3,2,1};
ElemType n=10,i,j;
ElemType low,high,
void BinSort(ElemType r[],ElemType n)
for(i=2;i&=n;i++)
r[0]=r[i];
low=1; high=i-1;
while (low&=high)
mid=(low+high)/2;
if(r[0]&r[mid])
high=mid-1;
low=mid+1;}
for(j=i-1;j&=j--)
r[i]=r[j];
r[low]=r[0];} }
void put(ElemType r[],ElemType n)
for(j=1;j&n;j++)
(&%d\t&,r[j]);
printf(&\n&);
void main()
BinSort(arr,n);
put(arr,n);
．博客园[引用日期]
．csdn[引用日期]线性表、树表、哈希表
顺序查找、折半查找、分块查找
1.1.1顺序查找。
顺序查找。
1.1.2折半查找
折半查找，只适用于有序表，且仅限于顺序存储结构，对线性链表无法进行有效的折半查找(折半查找low会指向一个元素而high会指向相邻的下一个元素，然后low和high指向同一个元素，再然后low&high，循环结束，所以循环结束的条件为low&=high)。注意不要忘记最会返回-1。
#include&stdafx.h&
#include&iostream&
//返回所查找数值在数组中的位置，如果没有则返回-1
int binarySearch(int* data, int n, int v){
if(data == NULL || n &= 0)
return -1;
int low = 0;
int high = n - 1;
while(low &= high){
middle = (low + high)/2;
if(data[middle] == v)
if(data[middle] & v)
low = middle + 1;
high = middle -1;
return -1;
int main(){
int data[] = {1,2};
cout&&binarySearch(data, 2 ,2);
1.1.3分块查找（索引顺序查找）
分块查找：分块查找又称为索引顺序查找，索引表采用（折半查找），块内（顺序查找）处理线性表既希望有较快的查找速度又需要动态的变化，则可以采用分块查找的方法。
二叉排序树（二叉查找树）、平衡二叉树
哈希表的构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留取余法、随机数法。&
解决冲突的方法：&开放定址法、再哈希法、链地址法。 &
插入排序、快速排序、选择排序、归并排序
2.1插入排序
直接插入排序、折半插入排序、希尔排序
2.1.1直接插入排序
待排记录的数量很小时使用。
#include&stdafx.h&
#include&iostream&
void insertSort(int* a,int n){
if(a == NULL || n &= 0){
for(i = 1; i & i++){
for(j = j & 0 && a[j] & a[j-1]; j--){
temp = a[j];
a[j] = a[j-1];
int main(){
int a[] = {5,3,6,3,1,4,7,2};
insertSort(a,8);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
2.1.2折半插入排序
在直接插入排序的基础上减少比较的次数。
算法关键：1.折半查找最后high和low会指向同一个元素，所以循环中判定条件为low&=high
2.关键字相同时，要到高半区，包装算法的稳定性
3.元素插入位置在high+1处
#include&stdafx.h&
#include&iostream&
void binaryInsertSort(int* a,int n){
if(a == NULL || a &= 0)
for(int i = 1; i & i++){
high = i -1;
//折半查找最后low和high会指向同一个元素
while(low &= high){
middle = (low + high)/2;
//关键字相同时，到高半区，保证稳定性
if(a[i] &= a[middle]){
low = middle + 1;
high = middle -1;
temp = a[i];
for(int j = j &= high + 2; j--){
a[j] = a[j-1];
//插入位置在high+1处
a[high + 1] =
int main(){
int a[] = {5,3,6,3,1,4,7,2};
binaryInsertSort(a,8);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
2.1.3希尔排序
当待排记录序列基本有序且数目较少时，直接插入排序效率较高，希尔排序正是从这两点分析出发对直接插入排序进行改进得到的一种插入排序算法。
#include&stdafx.h&
#include&iostream&
void shellInsert(int* a,int n, int k){
if(a == NULL || a &= 0 || k &= 0)
for(i = i & i++){
for(j = j & 0;){
if(a[j] & a[j-k]){
temp = a[j];
a[j] = a[j-k];
void shellSort(int* a ,int n,int ks[],int t){
for(int i = 0; i & i++){
shellInsert(a,n,ks[i]);
int main(){
int ks[] = {4,2,1};
int a[] = {5,3,6,3,1,4,7,2};
shellSort(a,8,ks,3);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
2.2快速排序
冒泡排序和快速排序是借助“交换”进行排序的方法。
2.2.1冒泡排序
一般算法（最好情况下时间复杂度也为n^2）：
#include &stdafx.h&
#include &iostream&
void bubbleSort(int* a, int n){
if(a == NULL || n &=0){
for(i = 0; i & i++){
for(j = n-1; j & j--){
if(a[j] & a[j-1]){
temp = a[j];
a[j] = a[j-1];
int main(){
int a[] = {5,3,6,3,1,4,7,2};
bubbleSort(a,8);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
优化算法，往上冒（最好情况下时间复杂度为n）：
#include &stdafx.h&
#include &iostream&
void bubbleSort(int* a, int n){
if(a == NULL || n &=0){
for(i = 0; i & i++){
for(j = n-1; j & j--){
if(a[j] & a[j-1]){
temp = a[j];
a[j] = a[j-1];
if(!move){
int main(){
int a[] = {5,3,6,3,1,4,7,2};
bubbleSort(a,8);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
优化算法，往下沉（最好情况下时间复杂度为n）：
#include &stdafx.h&
#include &iostream&
void bubbleSort(int* a, int n){
if(a == NULL || n &= 0){
for(i = n-1; i &=1; i--){
for(j =0; j & j++){
if(a[j] & a[j+1]){
temp = a[j+1];
a[j+1] = a[j];
int main(){
int a[] = {5,3,6,3,1,4,7,2};
bubbleSort(a,8);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
2.2.2快速排序
include&stdafx.h&
#include&iostream&
void quickSort(int* a,int l,int h){
if(a == NULL || l & 0 || h & 0){
cout&&&invalid param&&&
if(l & h){
int high =
int temp = a[low];
while(low & high){
while(low & high){
if(a[high] &= temp){
a[low] = a[high];
while(low & high){
if(a[low] &= temp){
a[high] = a[low];
quickSort(a,l,high-1);
quickSort(a,high+1,h);
int main(){
int a[] = {5,3,6,3,1,4,7,2};
quickSort(a,0,7);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
上述代码选取第一个元素为枢纽，若要随机选取枢纽元素，则首先将选取的元素与第一个元素对换即可。
2.3选择排序
简单选择排序、堆排序
2.3.1简单选择排序
#include &stdafx.h&
#include &iostream&
void simpleSelectSort(int* a, int n){
if(a == NULL || n &= 0){
int i,j,min,
for(i = 0; i &= n -2; i++){
for(j = j &= n-1; j++){
if(a[j] & a[min]){
temp = a[i];
a[i] = a[min];
int main(){
int a[] = {5,3,6,3,1,4,7,2};
simpleSelectSort(a,8);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
2.3.2堆排序
（1）将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆；
（2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)；
（3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区
(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
#include &stdafx.h&
#include &iostream&
//a[s..m]中除a[s]之外均满足堆的定义，
//本函数调整a[s],使a[s..m]成为一个大顶堆
void heapAdjust(int* a, int s, int m){
int temp = a[s];
for(int i = 2 * s + 1; i &= i = i * 2 + 1){
if(i & m && a[i] & a[i+1])
if(temp &= a[i])
a[s] = a[i];
int main(){
int a[] = {5,3,6,3,1,4,7,2};
int n = 8;
for(int i = n/2-1; i &= 0; i--){
heapAdjust(a,i,n-1);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &&&
for(int i = n-1; i &= 1; i--){
temp = a[0];
a[0] = a[i];
heapAdjust(a,0,i-1);
for(int i = 0; i & 8; i++){
cout&&a[i]&&& &;
2.4归并排序
与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。但在一般情况下很少利用2-路归并排序法进行内部排序。实现归并排序需和待排记录等数量的辅助空间，时间复杂度为O（nlogn）。
#include &stdafx.h&
#include &iostream&
void merge(int a[],int start,int mid,int end,int temp[])
int j = mid +1;
while(i&=mid&&j&=end)
if(a[i]&=a[j])
temp[k++]=a[i++];
temp[k++]=a[j++];
while(i&=mid)
temp[k++]=a[i++];
while(j&=end)
temp[k++]=a[j++];
for(int m=m&=m++)
a[m] = temp[m];
void mSort(int a[],int start,int end,int temp [])
if(start&end)
int mid = (start+end)/2;
mSort(a,start,mid,temp);
mSort(a,mid+1,end,temp);
merge(a,start,mid,end,temp);
void mergeSort(int a[],int n)
int* temp = new int[n];
mSort(a,0,n-1,temp);
int main()
int a[] = {3,5,7,2,1,6};
int n = 6;
mergeSort(a,n);
for(int i=0;i&n;i++)
cout&&a[i]&&& &;
平均情况（时间复杂度）
空间复杂度
直接插入排序
折半插入排序
简单选择排序
1.折半插入排序的元素比较次数由于采用了折半查找，相对与直接插入排序减少了，时间复杂度为n*logn，但是元素的移动次数并未减少，因此时间复杂度仍未n^2。
2.希尔排序是不稳定的。（希尔排序的时间复杂度是O（n的1.25次方）~O(1.6n的1.25次方) 这是一个经验公式，好像没人解释过，就是一句经验得出的。
希尔排序的分析是一个复杂的问题，以为它的时间是所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题。 数据结构书上这么说的 ）
3.快速排序会递归log（n）次，每次对n个数进行一次处理，所以他的时间复杂度为n*log(n)。
4.简单选择排序稳定性：举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
5.冒泡排序和简单选择排序的区别：冒泡算法，每次比较如果发现较小的元素在后面，就交换两个相邻的元素。而选择排序算法的改进在于：先并不急于调换位置，先从A[1]开
始逐个检查，看哪个数最小就记下该数所在的位置P，等一躺扫描完毕，再把A[P]和A[1]对调，这时A[1]到A[10]中最小的数据就换到了最前面的位置。
所以，选择排序每扫描一遍数组，只需要一次真正的交换，而冒泡可能需要很多次。比较的次数是一样的。
6.堆排序在最坏的情况下时间复杂度也为n*logn，相对于快速排序来说这是堆排序的最大优点。
附：冒泡排序最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。
举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列，第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4，4比5小，交换位置变成4 5 3 2
1；比较5和3，3比5小，交换位置变成4 3 5 2 1……最后比较5和1，1比5小，交换位置变成4 3 2 1 5。这时候共进行了4次比较交换运算，最后1个数变成了数列最大数。
第二次大循环从第一个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。……所以总的比较次数为 4 + 3 + 2 + 1 = 10次。
对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数。而O(N^2)表示的是复杂度的数量级。
计算时间复杂度时要找基本操作，比如在冒泡排序中，比较是基本操作，而交换不是，因为比较每次都需要做，而交换不一定。
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：7601次
排名：千里之外
转载：27篇
(7)(17)(4)(6)