下面说一下交换排序，交换排序主要有：冒泡排序和快速排序，快速排序（Quicksort）其实是对冒泡排序的一种改进。
为了方便描述，使用顺序表类型定义如下：
#define MAXSIZE 1000 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; }RecType; typedef struct { RecType r[MAXSIZE+1]; int length; }SqList;
冒泡排序
基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。整个排序过程最多执行n-1趟，它是一种稳定的算法。
C Code：
void BubbleSort(SqList &q) { int j,h,p=q.length-1,temp; for(h=1;h<=p;) for(j=0;jq.r[j+1].key) { temp=q.r[j]; q.r[j]=q.r[j+1]; q.r[j+1]=temp; p=j } }
冒泡排序法存在这不足,当排序的数据比较多时排序的时间会明显延长。具体做法：任意选取某一记录（通常取第一个记录），比较其关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完 ,这就是改进的方法：快速排序。
快速排序
设要排序的数组是a[0]……a[n-1]，
一趟快速排序的算法是：
1）设置两个变量low、high，排序开始的时候：low=0，low=n-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=a[0]；
3）从J开始向前搜索，即由后开始向前搜索（high=high-1），找到第一个小于key的值a[high]，并与a[low]交换；
4）从I开始向后搜索，即由前开始向后搜索（low=low+1），找到第一个大于key的a[low]，与a[high]交换；
5）重复第3、4、5步，直到 low=high；
示意图：
C Code:
void QuickSort(SqList &R ,int s,int t) { int low, high,Key; low=s; high=t; Key=R.r[s].key; R.r[0]=R.r[s]; while(low
作者：王迪(flute)
出处:http://www.cnblogs.com/flute-di/
转载时须注明本文的详细链接，否则作者将保留追究其法律责任
最新评论