各种排序算法的比较

Ⅰ 各种排序算法最好和最坏情况比较

最坏情况下比较次数最少的为D）堆排序：
A）冒泡排序 需要比较O(n^2)次（n(n - 1)/2次），即序列逆序的情况
B）简单选择排序，无论是否最坏都需要O(n^2)次（n(n - 1)/2次）
C）直接插入排序，最坏情况需要比较O(n^2)次（n(n - 1)/2次）
D）堆排序，无论是否最坏比较O(nlog2n)次
E）快速排序，最坏情况退化为冒泡排序，需要比较O(n^2)次（n(n - 1)/2次）

Ⅱ 几种常用的排序算法比较

排序，从小大，0坐标的在下面，即排序后小的在下面，大的在上面。

1，冒泡Bubble：从第0个开始，一直往上，与相邻的元素比较，如果下面的大，则交换。
Analysis：
Implementation：
void BubbleSort(int *pData, int iNum)

2，插入Insertion：与打扑克牌时整理牌很想象，假定第一张牌是有序的，从第二张牌开始，拿出这张牌来，往下比较，如果有比这张牌大的，则把它拨到上一个位置，直到找到比手上的这张更小的（或到顶了），
则把手上的这张牌插入到这张更小的牌的后面。
Analysis：
Implementation：
void InsertionSort(int *list, int length)
{
int i, j, temp;
for (i = 1; i < length; i++)
{
temp = list[i];
j = i - 1;
while ((j >= 0) && (list[j] > temp))
{
list[j+1] = list[j];
j--;
}
list[j+1] = temp;
}
}

3，选择Selection：从所有元素中找到最小的放在0号位置，从其它元素（除了0号元素）中再找到最小的，放到1号位置，......。
Analysis：
Implementation：
void SelectionSort(int data[], int count)
{
int i, j, min, temp;
for (i = 0; i < count - 1; i++)
{
/* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{
if (data[j] < data[min])
{
min = j;
}
}
/* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}

4，快速Quick：先拿出中间的元素来（值保存到temp里），设置两个索引（index or pointer），一个从0号位置开始往最大位置寻找比temp大的元素；一个从最大号位置开始往最小位置寻找比temp小的元素，找到了或到顶了，则将两个索引所指向的元素
互换，如此一直寻找交换下去，直到两个索引交叉了位置，这个时候，从0号位置到第二个索引的所有元素就都比temp小，从第一个索引到最大位置的所有元素就都比temp大，这样就把所有元素分为了两块，然后采用前面的办法分别排序这两个部分。总的来
说，就是随机找一个元素（通常是中间的元素），然后把小的放在它的左边，大的放右边，对左右两边的数据继续采用同样的办法。只是为了节省空间，上面采用了左右交换的方法来达到目的。
Analysis：
Implementation：
void QuickSort(int *pData, int left, int right)
{
int i, j;
int middle, iTemp;
i = left;
j = right;

middle = pData[(left + right) / 2]; //求中间值
do
{
while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
i++;

while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
j--;

if (i <= j) //找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
} while (i <= j); //如果两边扫描的下标交错，就停止（完成一次）

//当左边部分有值(left<j)，递归左半边
if(left < j)
QuickSort(pData, left, j);

//当右边部分有值(right>i)，递归右半边
if(right > i)
QuickSort(pData, i, right);
}

5，希尔Shell：是对Insertion Sort的一种改进，在Insertion Sort中，从第2个位置开始取出数据，每次都是与前一个（step/gap==1）进行比较。Shell Sort修改为，在开始时采用较大的步长step，
从第step位置开始取数据，每次都与它的前step个位置上的数据进行比较（如果有8个数据，初始step==4，那么pos(4)与pos(0)比较，pos(0)与pos(-4)，pos(5)与pos(1)，pos(1)与pos(-3)，
...... pos(7)与pos(3)，pos(3)与pos(-1)），然后逐渐地减小step，直到step==1。step==1时，排序过程与Insertion Sort一样，但因为有前面的排序，这次排序将减少比较和交换的次数。
Shell Sort的时间复杂度与步长step的选择有很大的关系。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合
于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
Analysis：
Implementation：
template<typename RandomIter, typename Compare>
void ShellSort(RandomIter begin, RandomIter end, Compare cmp)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;

diff_t size = std::distance(begin, end);
diff_t step = size / 2;
while (step >= 1)
{

for (diff_t i = step; i < size; ++i)
{
value_type key = *(begin+i);
diff_t ins = i; // current position

while (ins >= step && cmp(key, *(begin+ins-step)))
{
*(begin+ins) = *(begin+ins-step);
ins -= step;
}

*(begin+ins) = key;
}

if(step == 2)
step = 1;
else
step = static_cast<diff_t>(step / 2.2);
}
}

template<typename RandomIter>
void ShellSort(RandomIter begin, RandomIter end)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
ShellSort(begin, end, std::less<value_type>());
}

6，归并Merge：先将所有数据分割成单个的元素，这个时候单个元素都是有序的，然后前后相邻的两个两两有序地合并，合并后的这两个数据再与后面的两个合并后的数据再次合并，充分前面的过程直到所有的数据都合并到一块。
通常在合并的时候需要分配新的内存。
Analysis：
Implementation：
void Merge(int array[], int low, int mid, int high)
{
int k;
int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
int begin1 = low;
int end1 = mid;
int begin2 = mid + 1;
int end2 = high;

for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
{
if(array[begin1]<=array[begin2])
{
temp[k] = array[begin1++];
}
else
{
temp[k] = array[begin2++];
}
}
if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
{
memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
}
if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
{
memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
}
memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
free(temp);
}

void MergeSort(int array[], unsigned int first, unsigned int last)
{
int mid = 0;
if (first < last)
{
mid = (first+last)/2;
MergeSort(array, first, mid);
MergeSort(array, mid+1,last);
Merge(array,first,mid,last);
}
}

Ⅲ 综合排序算法的比较

#include "stdio.h "
#include "stdlib.h "
#define Max 100 //假设文件长度
typedef struct{ //定义记录类型
int key; //关键字项
}RecType;
typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵
int n; //顺序表实际的长度
//==========直接插入排序法======
void InsertSort(SeqList R) { //对顺序表R中的记录R[1¨n]按递增序进行插入排序
int i,j;
for(i=2;i <=n;i++) //依次插入R[2]，……，R[n]
if(R[i].key <R[i-1].key){ //若R[i].key大于等于有序区中所有的keys，则R[i]留在原位 R[0]=R[i];j=i-1; //R[0]是R[i]的副本 do { //从右向左在有序区R[1¨i-1]中查找R[i] 的位置 R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; }while(R[0].key <R[j].key); //当R[i].key≥R[j].key 是终止
R[j+1]=R[0]; //R[i]插入到正确的位置上
}//endif
}
//==========冒泡排序======= typedef enum{FALSE,TRUE} Boolean; //FALSE为0，TRUE为1
void BubbleSort(SeqList R) { //自下向上扫描对R做冒泡排序
int i,j;
bool exchange; //交换标志 for(i=1;i <n;i++) { //最多做n-1趟排序
exchange=false; //本趟排序开始前，交换标志应为假
for(j=n-1;j> =i;j--){ //对当前无序区R[i¨n] 自下向上扫描
if(R[j+1].key <R[j].key){ //两两比较，满足条件交换记录
R[0]=R[j+1]; //R[0]不是哨兵，仅做暂存单元
R[j+1]=R[j];
R[j]=R[0];
exchange=true; //发生了交换，故将交换标志置为真
}
if(! exchange) return; //本趟排序未发生交换，提前终止算法
}// endfor（为循环）
}
//==========快速排序=======
//1.========一次划分函数=====
int Partition(SeqList R,int i,int j) {
// 对R[i¨j]做一次划分，并返回基准记录的位置
RecType pivot=R[i]; //用第一个记录作为基准
while(i <j) { //从区间两端交替向中间扫描，直到i=j
while(i <j &&R[j].key> =pivot.key) //基准记录pivot相当与在位置i上
j--; //从右向左扫描，查找第一个关键字小于pivot.key的记录R[j]
if(i <j) //若找到的R[j].key < pivot.key，则
R[i++]=R[j]; //交换R[i]和R[j]，交换后i指针加1
while(i <j &&R[i].key <=pivot.key) //基准记录pivot相当与在位置j上
i++; //从左向右扫描，查找第一个关键字小于pivot.key的记录R[i]
if(i <j) //若找到的R[i].key > pivot.key，则
R[j--]=R[i]; //交换R[i]和R[j]，交换后j指针减1
}
R[i]=pivot; //此时，i=j，基准记录已被最后定位
return i; //返回基准记录的位置
}
//2.=====快速排序===========
void QuickSort(SeqList R,int low,int high) { //R[low..high]快速排序
int pivotpos; //划分后基准记录的位置
if(low <high) { //仅当区间长度大于1时才排序
pivotpos=Partition(R,low,high); //对R[low..high]做一次划分，得到基准记录的位置
QuickSort(R,low,pivotpos-1); //对左区间递归排序
QuickSort(R,pivotpos+1,high); //对右区间递归排序
}
}
//======直接选择排序========
void SelectSort(SeqList R) {
int i,j,k;
for(i=1;i <n;i++){ //做第i趟排序（1≤i≤n-1）
k=i;
for(j=i+1;j <=n;j++) //在当前无序区R[i¨n]中选key最小的记录R[k]
if(R[j].key <R[k].key)
k=j; //k记下目前找到的最小关键字所在的位置
if(k!=i) { //交换R[i]和R[k]
R[0]=R[i];R[i]=R[k];R[k]=R[0];
} //endif
} //endfor
}
//======堆排序========
//==========大根堆调整函数=======
void Heapify(SeqList R,int low,int high) {
// 将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质
int large; //large指向调整结点的左、右孩子结点中关键字较大者
RecType temp=R[low]; //暂存调整结点
for(large=2*low; large <=high;large*=2){ //R[low]是当前调整结点
//若large> high,则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子
if(large <high && R[large].key <R[large+1].key)
large++; //若R[low]的右孩子存在且关键字大于左兄弟，则令large指向它
//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者
if(temp.key> =R[large].key) //temp始终对应R[low]
break; //当前调整结点不小于其孩子结点的关键字，结束调整
R[low]=R[large]; //相当于交换了R[low]和R[large]
low=large; //令low指向新的调整结点，相当于temp已筛下到large的位置
}
R[low]=temp; //将被调整结点放入最终位置上
}
//==========构造大根堆==========
void BuildHeap(SeqList R) { //将初始文件R[1..n]构造为堆
int i;
for(i=n/2;i> 0;i--)
Heapify(R,i,n); //将R[i..n]调整为大根堆
}
//==========堆排序===========
void HeapSort(SeqList R) { //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i;
BuildHeap(R); //将R[1..n]构造为初始大根堆
for(i=n;i> 1;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]可能违反堆性质。
}
}
//==========二路归并排序===========
//===将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high]===
void Merge(SeqList R,int low,int m,int high) {
int i=low,j=m+1,p=0; //置初始值
RecType *R1; //R1为局部量
R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //申请空间
while(i <=m && j <=high) //两个子序列非空时取其小者输出到R1[p]上
R1[p++]=(R[i].key <=R[j].key)? R[i++]:R[j++];
while(i <=m) //若第一个子序列非空，则复制剩余记录到R1
R1[p++]=R[i++];
while(j <=high) //若第二个子序列非空，则复制剩余记录到R1中
R1[p++]=R[j++];
for(p=0,i=low;i <=high;p++,i++)
R[i]=R1[p]; //归并完成后将结果复制回R[low..high]
}
//=========对R[1..n]做一趟归并排序========
void MergePass(SeqList R,int length) {
int i;
for(i=1;i+2*length-1 <=n;i=i+2*length)
Merge(R,i,i+length-1,i+2*length-1); //归并长度为length的两个相邻的子序列
if(i+length-1 <n) //尚有一个子序列，其中后一个长度小于length
Merge(R,i,i+length-1,n); //归并最后两个子序列
//注意：若i≤n且i+length-1≥n时，则剩余一个子序列轮空，无须归并
}
//========== 自底向上对R[1..n]做二路归并排序===============
void MergeSort(SeqList R) {
int length;
for(length=1;length <n;length*=2) //做[lgn]趟排序
MergePass(R,length); //有序长度≥n时终止
}
//==========输入顺序表========
void input_int(SeqList R) {
int i;
printf( "Please input num(int): ");
scanf( "%d ",&n);
printf( "Plase input %d integer: ",n);
for(i=1;i <=n;i++)
scanf( "%d ",&R[i].key);
}
//==========输出顺序表========
void output_int(SeqList R) {
int i;
for(i=1;i <=n;i++)
printf( "%4d ",R[i].key);
}
//==========主函数======
void main() {
int i;
SeqList R;
input_int(R);
printf( "\t******** Select **********\n ");
printf( "\t1: Insert Sort\n ");
printf( "\t2: Bubble Sort\n ");
printf( "\t3: Quick Sort\n ");
printf( "\t4: Straight Selection Sort\n ");
printf( "\t5: Heap Sort\n ");
printf( "\t6: Merge Sort\n ");
printf( "\t7: Exit\n ");
printf( "\t***************************\n ");
scanf( "%d ",&i); //输入整数1-7，选择排序方式
switch (i){
case 1: InsertSort(R);
break; //值为1，直接插入排序
case 2: BubbleSort(R);
break; //值为2，冒泡法排序
case 3: QuickSort(R,1,n);
break; //值为3，快速排序
case 4: SelectSort(R);
break; //值为4，直接选择排序
case 5: HeapSort(R);
break; //值为5，堆排序
case 6: MergeSort(R);
break; //值为6，归并排序
case 7: exit(0); //值为7，结束程序
}
printf( "Sort reult: ");
output_int(R);
}

Ⅳ 各种排序算法比较

插入排序 n*n、希尔排序 <=n*n、起泡排序 <=n* n、快速排序 n *log 2 n、选择排序=n * n、堆排序n * log2 n、归并排序 n * n

Ⅳ 数据结构中几种常见的排序算法之比较

实话实说，关于数据结构中几种常见的排序算法（例如：冒泡排序、SHELL排序、归并排序、快速排序等）的性能好坏，还不只是学好了数据结构这门课程就能够解决的问题，还必须要学习好、且精通掌握计算机软件专业的另外一门非常重要的课程，才能够解决这个问题。即：计算机算法复杂性理论。
只有同时把这门课程学好了，那么才能够真正掌握数据结构中的各种排序算法、以及各种查找算法中所有涉及到的：比较次数、以及交换次数，最终才能够根据具体的开发软件规模的不同，选择出一个适合开发该软件的最佳算法。

Ⅵ 6．各种排序算法比较

什么意图
几乎全是垃圾算法。。。。。。
~~~~

Ⅶ 几种排序算法效率的比较

插入排序，选择排序，交换排序（冒泡），数据结构书上有详细的介绍
以下是直接插入排序，选择排序，希尔排序，冒泡排序的算法

/*直接插入排序的基本思想是：顺序地把待排序序
列中的各个记录按其关键字的大小，插入到已排
序的序列的适当位置。
*/

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;
}
}
}
}

Ⅷ 简述各种排序算法的优缺点

一、冒泡排序
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与 a[2]的值，若a[1]大于a[2]则交换 两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比 较a[3]与a[4]，以此 类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n- 1]以相同方法 处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理 n-1 轮 后a[1]、a[2]、……a[n]就以升序排列了。
优点：稳定；
缺点：慢，每次只能移动相邻两个数据。

二、选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数 据元素排完。
选择排序是不稳定的排序方法。
n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1 趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1 个记录R[1]交换，使R[1..1]和R[2..n]分别变 为记录个数增加1 个的新有序区和记录个数减少1 个的新无序区。
③第i 趟排序
第i 趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟 排序从当前无序区中选出关键字最 小的记录 R[k]，将它与无序区的第1 个记录R 交换，使R[1..i]和R 分别变为记录个数增加1 个的新有序区和记录个数减少 1 个的新无序区。
这样，n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果。
优点：移动数据的次数已知（n-1 次）；
缺点：比较次数多。

三、插入排序
已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、 b[2]、……b[m]，需将二者合并成一个升序数列。 首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值， 若b[1]仍然大于a[2]，则继续跳过，直 到b[1]小于a 数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来 a[x]的位置这就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1 的数组a）
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决 这个问题。

四、缩小增量排序
由希尔在1959 年提出，又称希尔排序(shell 排序)。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n 不大时，插入 排序的效果很好。首先取一增 量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、 a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……="" 列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操="" 作，直到d="1。"
优点：快，数据移动少；=""
缺点：不稳定，d="" 的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。=""

五、快速排序=""
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
="" 已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]="" 作为基准。比较a[x]与其它数据并="" 排序，使a[x]排在数据的第k="" 位，并且使a[1]~a[k-1]中的每一个数="" 据a[x]，然后采 用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。

Ⅸ 求各种排序算法的比较

给你一个国家集训队的快排吧，这个应该够用了。
这个是对a数组从小到大排序，把这个添加到任何程序中都很快。这个肯定要比堆排序快。对于插入排序快的快排肯定要较慢。但这个比较稳定，要不国家集训队怎么用它呢！！！！！！
procere qsort(l,r:longint);
var
i,j,x,yy:longint;
begin
i:=l;j:=r;x:=a[(i+j) shr 1];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
yy:=a[i];a[i]:=a[j];a[j]:=yy;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;