3 排序算法总结
3.1 直接插入排序
顺序遍历元素，并将其插入到其之前已经有序的数组中.
在最好情况下，即已经全部按所需的次序排列好，则比对次数仅为n-1，记录无需移动，时间复杂度为O(n-1);
在最坏情况下，即已经全部按所需的次序反序排列好，则比对次数仅为n(n-1)/2，记录移动次数为n(n+1)/2（与比对次数相比，每次都要多移动一个自身数据到指定位置，所以移动次数会比比对次数多n-1次），时间复杂度为O(n2);
算法实现：
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j= i-1;
int x = a[i]; //复制为哨兵，即存储待排序元素
a[i] = a[i-1]; //先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素后移
}
a[j+1] = x; //插入到正确位置
}
}
3.2 希尔排序
是对插入排序的一种改进，其基本思想是：
采用若干趟的插入排序使得最终结果的有序. 在每一趟中都会通过缩小增量以扩大插入排序的范围，最后直至增量为1，从而使得整个记录有序.
由于增量选取的任意性，所以很难计算希尔排序的时间复杂度，但大体上它的时间复杂度为O(n3/2
)
3.3快速排序
（2014.9 阿里面）
以升序为例，选择一个基准元素，进行一次排序后，使得其左边的元素全部不大于该基准元素，其右边的元素全部不小于该基准元素. 然后分别对该基准元素的左边数组和右边数据迭代进行重复的步骤，从而就可使得整个记录有序. （a）一趟排序的过程：
（b）排序的全过程
实现算法：
int partition(int a[], int low, int high)
{
int privotKey = a[low]; //基准元素
while(low < high){ //从表的两端交替地向中间扫描
while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
swap(&a[low], &a[high]);
while(low < high && a[low] <= privotKey ) ++low;
swap(&a[low], &a[high]);
}
print(a,10);
return low;
}
void quickSort(int a[], int low, int high){
if(low < high){
int privotLoc = partition(a, low, high); //将表一分为二
quickSort(a, low, privotLoc -1); //递归对低子表递归排序
quickSort(a, privotLoc + 1, high); //递归对高子表递归排序
}
}
复杂度分析：
1） 最好情况：
没有最好的情况，即不会达到O(n)的情况，只有在平均情况下时间复杂度为:O(nlogn)， 移动记录:等数量级
2）最坏情况
时间复杂度为:O (n2/4) = O (n2), 与冒泡排序一样，移动记录:等数量级
在初始记录基本有序时，会导致在一趟快排后，出现在递归过程中栈的最大深度达到n（如果一趟快排后两端的长度均分，则递归是栈的最大深度为+1），此时就会退化为冒泡排序.对快速排序进行优化的方法有：
1） 每次选枢轴的时候，将原来的第一个关键字当作枢轴，改为选取头关键字、尾
关键字和中间关键字三者中的中间值作为枢轴;
2） 在低端子记录序列和低端子记录序列中设置监视标志，如果低端子记录序列没
有发现记录移动，从而停止继续往下递归，同理，在高端中也采用类似做法.
3.4 起泡排序
逐个遍历记录，每趟将最大的记录沉到水底. 所以需要进行n-1 + n-2 + …+ 1 = n(n-1)/2次比较，并进行同数量级的记录移动.时间复杂度为O(n2).
3.5 堆排序
堆排序是选择排序中的一种. 其时间花在一直重构堆和取出顶端数值中.
堆排序其数值是用数组A[1..n]进行存储. 在建初始堆时，从最后一个非叶子节点处往回进行依次比对和记录调整. 所需时间时间为遍历节点n/2和每个节点进行重新调整堆所需的总共花费n/2. 在排序中，依次从堆顶取出数据，共遍历数据n次, 每次取完数据后又需调整堆所需时间，所以排序时间为n*. 因此堆排序总共花费时间为：n/2+n* = O(). 是不稳定的排序，辅助空间为1个即可. 如图建堆初始过程：无序序列：（
49，
38
，65，97，76，13，27，49）
3.6 归并排序
归并排序示例：
归并排序算法：
假定输入的是数组A[1..n]
1. 用一定的长度（如2路归并）将数组按顺序切分；
2. 对于切分后的记录进行排序；
3. 将排序后的每个块记录视为一个新的记录，按固定长度切分. 重复步骤2，直至最
终的切分块合并为一整个数组. 结束.
复杂度分析：
在一趟排序中，对于数组中相邻长度为h的有序段，需要进行次比对. 在总共的归并操作中，由于类似于折半查找，因此共需要进行次归并，因此总的时间复杂度为：* = O(n.logn). 由于数组的排序中需要交换位置，因此基本上需要同等数量（即n）的辅助空间.
适用场合：
是一个稳定的排序方法，一般用于外部排序.
3.7 基数排序
基数排序示例：
归并排序算法：
假定输入的是数组A[1..n]，且为整型数值
1. 用链表的方式进行最低位关键字的排序，完成第一趟
2. 对第一趟排过序的记录按最低第二位关键字排序，完成第二趟；
3. 一致循环到记录中的最高位关键字排序，完成第d（假设记录中关键字最长为
d, 每个关键字的取值范围为r个值）趟排序. 结束.
复杂度分析：
在一趟排序中，需要进行n次关键字比对与分配. 分配完后还要进行r次的收集，因此一趟排序花费n+r次时间. 总共需要进行d趟排序，因此总的时间复杂度为： O(d.(n+r)). 每个关键字比对时采用链式的形式进行存放，因此需要O(r)个辅助空间(每个关键字可能的取值范围).
适用场合：
是一个稳定的排序方法，一般用于n很大而关键字d很小的场合.
3.7 计数排序
计数排序算法：
1. 输入数组A[1..n],假定输入类型为整型，最大的记录数为K，那么用大小为K的
辅助存储空间，将数组A中的记录之间放入相应的位置，并将该位置的值加1.
2. 将辅助存储空间中K个数据内非零的项依次输出.完成.
复杂度分析：
n个关键字放入辅助空间中，用时为n；将大小为K的辅助存储空间内数据依次输出，用时为K，因此总的时间复杂度为： O(n+K). 需要O(K)个辅助空间.
适用场合：
是一个稳定的排序方法，一般用于记录中最大值为n的场合，属于非比较排序
.
3.7 桶排序
桶排序算法：
1. 首先要求输入数据均匀且独立地分布在[0,1)上，将区间[0,1)等分成n份，形成n个桶.
2. 将输入数据根据自身的数值依次分配到相应的桶中.
3. 对桶中的数据进行排序
4. 依次输入各个桶的数据. 结束.
复杂度分析：
将n个关键字放入桶中，用时为n；对桶中的数据进行插入排序，用时为， 因为，所以通排序总的时间复杂度为：O(n)+n.O() = O(n). 需要O(n)个辅助空间. 适用场合：
是一个稳定的排序方法，一般用于(0,1)之间记录的场合，属于非比较排序，.
（2014.9 阿里面）
第二篇：7种排序算法总结
7种排序算法总结：
整理的时候资源来自网络。不妥的联系我。谢谢。 事实上，目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。因此我们就来从多个角度来剖析一下提到的各种排序的长与短。
我们将7种算法的各种指标进行对比，如表9‐10‐1所示。
表9‐10‐1
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
O(n) O(n2) O(1) 稳定 O(n2) O(n2) O(1) 稳定 O(n) O(n2) O(1) 稳定 O(n1.3) O(n2) O(1) 不稳定 O(nlogn) O(1) 不稳定 O(nlogn) O(n) 稳定 O(n2) O(logn)～O(n) 不稳定 O(nlogn) O(nlogn) 冒泡排序 O(n2) 简单选择排序 O(n2) 直接插入排序 O(n2) 堆排序 O(nlogn) 快速排序 O(nlogn)
希尔排序 O(nlogn)-O(n2) 归并排序 O(nlogn) O(nlogn)
从算法的简单性来看，我们将7种算法分为两类：
简单算法：冒泡、简单选择、直接插入。
改进算法：希尔、堆、并、快速。
从平均情况来看，显然最后3种改进算法要胜过希尔排序，并远远胜过前3种简单算法。
从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑后4种复杂的改进算法。
从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。
从这三组时间复杂度的数据对比中，我们可以得出这样一个认识。堆排序和归并排序就像两个参加奥数考试的优等生，心理素质强，发挥稳定。而快速排序像是很情绪化的天才，心情好时表现极佳，碰到较糟糕环境会变得差强人意。但是他们如果都来比赛计算个位数的加减法，它们反而算不过成绩极普通的冒泡和直接插入。
从空间复杂度来说，归并排序强调要马跑得快，就得给马吃个饱。快速排序也有相应的空间要求，反而堆排序等却都是少量索取，大量付出，对空间要求是O(1)。如果执行算法的软件所处的环境非常在乎内存使用量的多少时，选择归并排序和快速排序就不是一个较好的决策了。
从稳定性来看，归并排序独占鳌头，我们前面也说过，对于非常在乎排序稳定性的应用中，归并排序是个好算法。
从待排序记录的个数上来说，待排序的个数n越小，采用简单排序方法越合适。反之，n越大，采用改进排序方法越合适。这也就是我们为什么对快速排序优化时，增加了一个阀值，低于阀值时换作直接插入排序的原因。
从表9‐10‐1的数据中，似乎简单选择排序在3种简单排序中性能最差，其实也不完全是，比如，如果记录的关键字本身信息量比较大（例如，关键字都是数十位的数字），此时表明其占用存储空间很大，这样移动记录所花费的时间也就越多，我们给出3种简单排序算法的移动次数比较，如表9‐10‐2所示。
表9-10-2
排序方法 平均情况 最好情况 最坏情况
冒泡排序 O(n2) 0 O(n2)
简单选择排序 O(n) 0 O(n)
直接插入排序 O(n2) O(n) O(n2)
你会发现，此时简单选择排序就变得非常有优势，原因也就在于，它是通过大量比较后选择明确记录进行移动，有的放矢。因此对于数据量不是很大而记录的关键字信息量较大的排序要求，简单排序算法是占优的。另外，记录的关键字信息量大小对那四个改进算法影响不大。
总之，从综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同的场合我们也应该考虑使用不同的算法来应对它。 一、冒泡排序：
原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。 要点：设计交换判断条件，提前结束以排好序的序列循环。
实现：
int BubbleSort(int L[],int length)
{
int i,j;
int temp;
int ischanged = 0;//设计跳出条件
printf("BubbleSort :\n");
for(i=1;i<length;i++)
{
ischanged = 0;
for(j=length-1;j>=i;j--)
{
if(L[j]<L[j-1])//如果发现较重元素就向后移动,这里比较前后两
// 个相邻元素的大小，若该条件一直不满足则说明数据是有序的
{
temp=L[j];
L[j]=L[j-1];
L[j-1]=temp;
ischanged = 1;
}
}
if(ischanged == 0)//若没有移动则说明序列已经有序，直接跳出
break;
}
return 0;
} 二、 简单选择排序：
原理：将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，使得有序区扩大一个，循环最终完成全部排序。
实现：
void SelectSort(int L[],int length)
{
int i,j,k,temp;//分别为有序区，无序区，无序区最小元素指针
for(i=0;i<length;i++)
{
k=i;
for(j=i+1;j<length;j++)
{
if(L[j]<L[k])
k=j;
}
if(k!=i)//若发现最小元素，则移动到有序区
{
temp=L[k];
L[k]=L[i];
L[i]=temp;
}
}
}
三、直接插入排序：
原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。
要点：设立哨兵，作为临时存储和判断数组边界之用。
实现：
int InsertSort(int L[],int length)
{
int i,j,temp;
printf("InsertSort :\n");
for(i=0;i<length-1;i++)
{
j = i+1;
if(L[j] < L[i])
{
temp = L[j]; //存储待排序元素
while(temp < L[i]){ //循环中找到需要插入的位置
L[i+1] = L[i];
i--;
}
L[++i] = temp;//将存储的元素数据插入到相应位置
i = j - 1;// 还原外部循环的下标
}
}
return 0; }
四、希尔排序：
原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。
要点：增量的选择以及排序最终以1为增量进行排序结束。
实现：
void ShellSort(int L[],int length)
{
int d = length>>1;//length = length/2;
int i,j,temp;
while(d >=1 ){
} for(i = d;i<length;i++) { } d >>= 1; temp = L[i]; j = i - d; while(j>=0 && temp < L[j]){ } L[j+d] = temp; L[j+d] = L[j]; j = j - d;
五、堆排序：
原理：利用大根堆或小根堆思想，首先建立堆，然后将堆首与堆尾交换，堆尾之后为有序区。
要点：建堆、交换、调整堆
实现：
int MAX_Heapify(int A[],int i,int length)
{
int l,r,largest;
//size = sizeof(A)/sizeof(int);
l = i*2+1;
r = i*2 + 2;
if(l < length && A[l] > A[i])
largest = l;
else
largest = i;
if(r < length && A[r] > A[largest])
largest = r;
if(largest != i)
{
int tmp = A[i];
A[i] = A[largest];
A[largest] = tmp;
MAX_Heapify(A,largest,length);
}
return 0;
}
int build_heap(int A[],int length)
{
int i;
//size = sizeof(A)/sizeof(int);
for(i = (length-1)/2;i>=0;i--)
MAX_Heapify(A,i,length);
return 0;
}
int heap_sort(int A[],int length)
{
int i,tmp;
int size = length;
build_heap(A,length);
for(i = size-1;i>0;i--)
{
tmp = A[0];
A[0] = A[i];
A[i]=tmp;
size--;
MAX_Heapify(A,0,size);
}
return 0;
}
六、归并排序：
原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。
要点：归并、分治
实现：
void Merge(int c[], int d[], int l, int m, int r)
{
// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] . int i=l; // 第一段的游标
int q;
int j=m+1; // 第二段的游标
int k=l; // 结果的游标
//只要在段中存在i和j，则不断进行归并 while ((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
d[k++]=c[i++];
else
d[k++]=c[j++];
}
// 考虑余下的部分
if(i>m)
{
for(q=j;q<=r;q++)
d[k++]=c[q];
}
else
{
for(q=i;q<=m;q++)
d[k++]=c[q];
}
}
void MergePass(int x[],int y[],int s,int n) {
// 归并大小为s的相邻段
int i=0,j;
while(i<=n-2*s)
{
// 归并两个大小为s的相邻段
Merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
// 剩下不足2个元素
if(i+s<n)
Merge(x,y,i,i+s-1,n-1);
else
for(j=i;j<=n-1;j++)
// 把最后一段复制到y
y[j] = x[j];
}
void MergeSort(int L[],int length)
{
//使用归并排序算法对a[0:n-1] 进行排序
int* b=(int*)malloc(sizeof(int)*length);
int s=1; // 段的大小
while(s<length)
{
MergePass(L,b,s,length); // 从a归并到b
s+=s;
MergePass(b,L,s,length); // 从b 归并到a
s+=s;
}
free(b);
}
七、快速排序：
原理：快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序的具体过程如下：
第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。
第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
代码如下:
void Quick(int L[],int low,int high) //low和high是数组的下标
{
if(low<high)
{
int t=L[low];
int l=low,h=high;
while(l<h)
{
while((L[h]>=t) && (l<h) ) h--; if(l<h)
{
L[l]=L[h];
l++; } while((L[l]<t)&&(l<h)) l++; if(l<h)
{
L[h]=L[l];
h--;
}
}
L[l]=t;
if(low < l){
Quick(L,low,l-1);
}
if(l < high){
Quick(L,l+1,high);
}
}
}
void Quick_Sort(int L[],int length) {
Quick(L,0,length-1);
}
自己测试用到的main()函数：
int main(void)
{
int *a,*b;
int num = 10;
int i = 0,j;
int (*fun[7])(int*,int);
fun[0] = BubbleSort;
fun[1] = SelectSort;
fun[2] = InsertSort;
fun[3] = HeapSort;
}
fun[4] = QuickSort; fun[5] = MergeSort; fun[6] = ShellSort; //函数指针 a = (int*)malloc(sizeof(int)*num); for(i=0;i<num;i++) { } printf("\nafter sort :\n"); b = (int*)malloc(sizeof(int)*num); for(i=0;i<7;i++) { } free(b); printf("i is %d\n",i); for(j=0;j<num;j++) b[j] = a[j]; (fun[i])(b,num); for(j = 0;j<num;j++){ } printf("\n"); printf("%d,",b[j]); a[i] = rand()%1000; printf("%d,",a[i]);
由于本人基础较差，整理的时候难免有问题，麻烦各位把看到的问题贴出来，共同学习学习，谢谢了。