一、直接插入排序
1、算法思想
直接插入排序(straight insertion sort),有时也简称为插入排序,是减治法的一种典型应用。其基本思想如下:
对于一个数组A[0,n]的排序问题,假设认为数组在A[0,n-1]排序的问题已经解决了。
考虑A[n]的值,从右向左扫描有序数组A[0,n-1],直到第一个小于等于A[n]的元素,将A[n]插在这个元素的后面。
很显然,基于增量法的思想在解决这个问题上拥有更高的效率。
2、直接插入的效率和特点
直接插入排序对于最坏情况(严格递减的数组),需要比较和移位的次数为n(n-1)/2;对于最好的情况(严格递增的数组),需要比较的次数是n-1,需要移位的次数是0。当然,对于最好和最坏的研究其实没有太大的意义,因为实际情况下,一般不会出现如此极端的情况。然而,直接插入排序对于基本有序的数组,会体现出良好的性能,这一特性,也给了它进一步优化的可能性。直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1),同时也是稳定排序。
3、举例
现有一个无序数组,共7个数:89 45 54 29 90 34 68。使用直接插入排序法,对这个数组进行升序排序。
89 45 54 29 90 34 68
45 89 54 29 90 34 68
45 54 89 29 90 34 68
29 45 54 89 90 34 68
29 45 54 89 90 34 68
29 34 45 54 89 90 68
29 34 45 54 68 89 90
4、C++代码实现(核心在InsertSort函数中)
#include <iostream>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct
{
KeyType key;
InfoType otherinfo;
} ElemType;
typedef struct
{
ElemType R[11];
int length;
}SqList;
void Init_SqList(SqList &L)
{
int i, flag=-1;
L.length= 11;
for(i=1; i<L.length; i++)
{
L.R[i].key= i*flag;
flag*=-1;
}
}
void InsertSort(SqList &L)
{
int i, j;
for(i=2; i<=L.length; i++)
{
if(L.R[i].key<L.R[i-1].key)
{
L.R[0]= L.R[i];
L.R[i]= L.R[i-1];
for(j=i-2; L.R[0].key<L.R[j].key; j--)
L.R[j+1]= L.R[j];
L.R[j+1]= L.R[0];
}
}
}
int main()
{
int i;
SqList sq;
Init_SqList(sq);
cout << "原表: ";
for(i=1; i<sq.length; i++)
cout << sq.R[i].key << " ";
cout << endl;
InsertSort(sq);
cout << "排序后:";
for(i=1; i<sq.length; i++)
cout << sq.R[i].key << " ";
}
二、冒泡排序
1、算法思想: 依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。
1)第一次比较,首先比较第一和第二个数,将小数放在前面,将大数放在后面。
2)比较第2和第3个数,将小数 放在前面,大数放在后面。
3))如此继续,知道比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成。
4)在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。
5)在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。
6)依次类推,每一趟比较次数减少依次。
2、C++代码实现(核心在BubbleSort函数中)
#include <iostream>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct
{
KeyType key;
InfoType otherinfo;
} ElemType;
typedef struct
{
ElemType R[11];
int length;
}SqList;
void Init_SqList(SqList &L)
{
int i, flag=-1;
L.length= 11;
for(i=1; i<L.length; i++)
{
L.R[i].key= i*flag;
flag*=-1;
}
}
void BubbleSort(SqList &L)
{
int m= L.length-1;
int flag=1;
int j;
ElemType t;
while((m>0) && (flag==1))
{
flag= 0;
for(j=1; j<=m; j++)
if(L.R[j].key>L.R[j+1].key)
{
flag= 1;
t=L.R[j];
L.R[j]=L.R[j+1];
L.R[j+1]= t;
}
--m;
}
}
3、测试部分
int main()
{
int i;
SqList sq;
Init_SqList(sq);
cout << "原表: ";
for(i=1; i<sq.length; i++)
cout << sq.R[i].key << " ";
cout << endl;
BubbleSort(sq);
cout << "排序后:";
for(i=1; i<sq.length; i++)
cout << sq.R[i].key << " ";
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)