排序算法效率
① 几种排序算法效率的比较
插入排序，选择排序，交换排序（冒泡），数据结构书上有详细的介绍
以下是直接插入排序，选择排序，希尔排序，冒泡排序的算法
/*直接插入排序的基本思想是：顺序地把待排序序
列中的各个记录按其关键字的大小，插入到已排
序的序列的适当位置。
*/
void InsertSort(elemtype x[], int n)
{
int i,j;
elemtype s;
for(i=0;i<n-1;i )
{
s = x[i 1];
j = i;
while(j>-1 && s.key<x[j].key)
{
x[j 1] = x[j];
j--;
}
x[j 1]=s;
}
}
/*选择排序的基本思想是：不断从待排序的序列中
选取关键字最小的记录放到已排序的记录序列的
后面，知道序列中所有记录都已排序为止。
*/
void SelectSort(elemtype x[], int n)
{
int i,j,Small;
elemtype Temp;
for(i=0;i<n-1;i )
{
Small = i;
for(j=i 1;j<n;j )
{
if(x[j].key<x[Small].key)
Small = j;
}
if(Small!=i)
{
Temp = x[i];
x[i] = x[Small];
x[Small] = Temp;
}
}
}
/*希尔排序的基本思想是：不断把待排序的记录分
成若干个小组，对同一组内的记录进行排序，在
分组时，始终保证当前组内的记录个数超过前面
分组排序时组内的记录个数。
*/
void ShellSort(elemtype x[], int n, int d[], int Number)
{
int i, j, k, m, Span;
elemtype s;
for(m=0;m<Number;m )
{
Span = d[m];
for(k=0;k<Span;k )
{
for(i=k;i<n-Span;i =Span)
{
s = x[i Span];
j = i;
while(j>-1 && s.key<x[j].key)
{
x[j Span] = x[j];
j-=Span;
}
x[j Span] = s;
}
}
}
}
/*冒泡排序的基本思想是：将待排序序列中第一个
记录的关键字R1与第二个记录的关键字R2做比较，
如果R1>R2，则交换R1和R2的位置，否则不交换；
然后继续对当前序列中的第二个记录和第三个记
录同样的处理，依此类推。
*/
void BubbleSort(elemtype x[], int n)
{
int i,j,flag=1;
elemtype temp;
for(i=1;i<n && flag==1;i )
{
flag=0;
for(j=0;j<n-i;j )
{
if(x[j].key>x[j 1].key)
{
flag=1;
temp=x[j];
x[j]=x[j 1];
x[j 1]=temp;
}
}
}
}
② 数据结构中哪种排序方式效率最好
简单排序的算法（直接插入，冒泡，简单选择排序）简单且稳定，适合与待排记录较小的情况，当当待排序的关键码序列已经基本有序时，用直接插入排序最快。
就平均时间的性能而言，快速排序最佳，即排序速度最快，所以在随机情况下，快速排序是最佳选择。一般情况下，快速排序效率最好。
既要节省空间，又要有较快的排序速度，堆排序是最佳选择，其不足之处是建堆时需要消耗较多时间。
若希望排序是稳定的，且有较快的排序速度，则可选用2路归并排序，其缺点需要较大的辅助空间分配。
③ 在各类算法中那种算法排序是最快的
说句实话，没有最快这一说。
如果不在乎浪费空间，应该是桶排序最快
如果整体基本有序，插入排序最快
如果考虑综合情况，快速排序更加实用常见（希尔排序、堆排序等各种排序也各有优劣）
一般情况下，冒泡这种排序仅仅是名字起的有趣罢了，不太好用
④ 几种排序算法的比较
一、八大排序算法的总体比较
4.3、堆的插入：
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中
（1）用大根堆排序的基本思想
先将初始数组建成一个大根堆，此对为初始的无序区；
再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足<=的值；
由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值<=的值，同样要将其调整为堆；
..........
直到无序区只有一个元素为止；
4.4：应用
寻找M个数中的前K个最小的数并保持有序；
时间复杂度：O(K)[创建K个元素最大堆的时间复杂度] +（M-K）*log(K)[对剩余M-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个记录排到位，剩下一个最大记录直接排在最后；
⑤ 常见的排序算法哪个效率最高
快速排序法。
⑥ 几种排序算法的效率比较
[内部排序的主要算法及相关可实现程序.rar
] - 内部排序的所有算法，而且有相关可执行例子，包括插入排序，选择排序，希尔排序，快速排序，堆排序，归并排序等，很全，很孀。[排序算法、字典和B-树的C++语言实现.zip
] - 排序算法、字典和B-树的C++语言实现
代码内容 包括以下算法：
qui.c sort: quicksort
qsort.c sort: qsort
ins.c sort: insert sort
shl.c sort: shell sort
has.c dictionary:[几种排序方法的实现.rar
] - 用 插入排序, 希尔排序 ,冒泡, 快速排序 , 选择排序 ,堆排序, 归并排序 实现对任意随机数序列,并比较各种方法的运行快慢和复杂度[paixu.rar] - 内部排序算法比较
] - 一个用VC++6.0做的一个数据库方面的程序，是用来英语学习的，有助于VC数据库编程的学习。[各种排序方法比较.rar
] - 这个程序包括了各种常用内部排序算法在平均排序所需时间上的比较.[实现各种排序算法并分析与比较.rar
] - 本程序实现各种排序算法并分析与比较 直接插入排序， SHELL排序，冒泡排序，快速排序，简单选择排序，堆排序，归并排序[图论算法库 C++ 语言实现.zip
] - 图论算法库 C++ 语言实现
代码内容 图论算法库，包括以下算法：
⑦ 哪种排序算法的效率最高
没有最高，只有更高。不同数据结构有不同算法，没有可比性。同一种数据结构才能比
⑧ 谁帮我写一份c语言版的各种排序算法的效率比较
（1）“冒泡法” 冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ { int i,j,temp; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) /*注意循环的上下限*/ if(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } 冒泡法原理简单，但其缺点是交换次数多，效率低。 下面介绍一种源自冒泡法但更有效率的方法“选择法”。 （2）“选择法” 选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。void choise(int *a,int n) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; /*给记号赋值*/ for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/ if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } } } 选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。 （3）“快速法” 快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：void quick(int *a,int i,int j) { int m,n,temp; int k; m=i; n=j; k=a[(i+j)/2]; /*选取的参照*/ do { while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/ while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/ if(m<=n) { /*若找到且满足条件，则交换*/ temp=a[m]; a[m]=a[n]; a[n]=temp; m++; n--; } }while(m<=n); if(m<j) quick(a,m,j); /*运用递归*/ if(n>i) quick(a,i,n); } （4）“插入法” 插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。void insert(int *a,int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a[i]; /*temp为要插入的元素*/ j=i-1; while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/ a[j+1]=a[j]; j--; } a[j+1]=temp; /*插入*/ } } （5）“shell法” shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码：void shell(int *a,int n) { int i,j,k,x; k=n/2; /*间距值*/ while(k>=1) { for(i=k;i<n;i++) { x=a[i]; j=i-k; while(j>=0&&x<a[j]) { a[j+k]=a[j]; j-=k; } a[j+k]=x; } k/=2; /*缩小间距值*/ } } 上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。 #include<stdio.h> /*别偷懒，下面的"..."代表函数体，自己加上去哦！*/ void bubble(int *a,int n) { ... } void choise(int *a,int n) { ... } void quick(int *a,int i,int j) { ... } void insert(int *a,int n) { ... } void shell(int *a,int n) { ... } /*为了打印方便，我们写一个print吧。*/[code]void print(int *a,int n) { int i; for(i=0;i<n;i++) printf("%5d",a[i]); printf("\n"); } main() { /*为了公平，我们给每个函数定义一个相同数组*/ int a1[]={13,0,5,8,1,7,21,50,9,2}; int a2[]={13,0,5,8,1,7,21,50,9,2}; int a3[]={13,0,5,8,1,7,21,50,9,2}; int a4[]={13,0,5,8,1,7,21,50,9,2}; int a5[]={13,0,5,8,1,7,21,50,9,2}; printf("the original list:"); print(a1,10); printf("according to bubble:"); bubble(a1,10); print(a1,10); printf("according to choise:"); choise(a2,10); print(a2,10); printf("according to quick:"); quick(a3,0,9); print(a3,10); printf("according to insert:"); insert(a4,10); print(a4,10); printf("according to shell:"); shell(a5,10); print(a5,10); }