1、冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，
交换也发生在这两个元素之间。所以，如果两个元素相等，是不用交换的；如果两个相等的元素没有相邻，
那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改 变，
所以冒泡排序是一种稳定排序算法
代码如下：
void bubble_sort(int a[],int n)
{
_FUNC;
for(int i=n-1;i>0;i--)
for(int j=0;j<i;j++)
if(a[j]>a[j+1])
swap(a[j],a[j+1]);
}
2、快速排序
快速排序（Quicksort）是对冒泡排 序的一种改进。由C. A. R. Hoare在1962年提出。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据都要小，然 后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归进行，以此达到整个数据变成有序序列
代码如下：
void qsort(int a[],int l,int r){
int pvt=a[(l+r)/2];
int i=l,j=r;
while(i<=j){
while(a[i]<pvt)
i++;
while(a[j]>pvt)
j--;
if(i<=j){
if(i!=j)
swap(a[i],a[j]);
i++;
j--;
}
}
if(j>l)
qsort(a,l,j);
if(i<r)
qsort(a,i,r);
}
void quick_sort(int a[],int n){
qsort(a,0,n-1);
}
3、直接插入排序
直接插入排序(straight insertion sort)的作法是：每次从无序表中取出第一个元素，
把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，
把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。
内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，
所以外层循环是从第二个数值开始的。当前一数值比待比较数 值大的情况下继续循环比较，
直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。（从小到大）
值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，
我们要将待比较数值置入比它小的数值的后一位。插入排序类似玩牌时整理手中纸牌的过程
代码如下：
void insert_sort(int a[],int n)
{
_FUNC;
for(int i=1;i<n;i++) {
int t=a[i];
int j;
for(j=i-1;j>=0&&a[j]>t;j--) {
a[j+1]=a[j];
}
a[j+1]=t;
print(a,n);
}
}
4、折半插入排序
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，
就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，
这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
折半插入排序算法的具体操作为：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，
将待插入区域的首元素设置为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]。
代码如下：
void binary_insert_sort(int a[],int n){
for(int i=1;i<n;i++){
int low=0;
int high=i-1;
int t=a[i];
int mid;
while(low<=high){
mid=(low+high)/2;
if(t<a[mid])
high=mid-1;
else
low=mid+1;
}
for(int j=i;j>mid;j--)
a[j]=a[j-1];
a[low]=t;
}
}
5、希尔排序
希尔排序（Shell Sort）又叫做缩小增量排序（diminishing increment sort），是一种很优秀的排序法，
算法本身不难理解，也很容易实现，而且它的速度很快。
基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入 排序；然后，
取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，
即所有记录放在同一组中进行直接插入排序为止。
void shell_sort(int a[],int n)
{
_FUNC;
int gap=n/2;
bool flag=true;
while(gap>1 flag)
{
flag=false;
for(int i=0;i+gap<n;i++)
if(a[i]>a[i+gap])
{
swap(a[i],a[i+gap]);
flag=true;
}
print(a,n);
if(gap>1)
gap/=2;
}
}
当前位置：
论坛首页 »
自由讨论区 »
Android, Python及开发编程讨论区
»
发起投票
技术讨论
加好友
发消息
2015-8-20 17:59:32 |
赞(
操作
