if (i < j) //表示找到了R[i],使R[i].key>pivot.key R[j--] = R[i]; //相当于交换R[i]和R[j],交换后j指针减1 } //endwhile R[i] = pivot; //基准记录已被最后定位 return i; } //partition //-----------------------------选择排序------------------------------------------- /* 直接选择排序 */ 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记下目前找到的最小关键字所在的位置
//-----------------------------插入排序-------------------------------------------/* 直接插入排序 */
void lnsertSort(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]; //R[0]是哨兵,且是R[i]的副本
j = i-1;
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
} //endfor
} //InsertSort
/* 希尔排序 */
void ShellPass(SeqList R, int d)
{
int i, j;
//希尔排序中的一趟排序,d为当前增量
for (i=d+1; i<N; i++) //将R[d+1..n]分别插入各组当前的有序区
{
if (R[i].key < R[i-d].key) {
R[0] = R[i]; //R[0]只是暂存单元,不是哨兵
j = i-d;
do {
//查找R[i]的插入位置
R[j+d] = R[j]; //后移记录
j = j - d; //查找前一记录
} while (j>0 && R[0].key < R[j].key);
R[j+d] = R[0]; //插入R[i]到正确的位置上
} //endif
} //enfor
} //ShellPassvoid ShellSort(SeqList R)
{
int increment = N; //增量初值,不妨设n>0
do {
increment=increment/3+1; //求下一增量
ShellPass(R, increment); //一趟增量为increment的Shell插入排序
} while (increment > 1);
} //ShellSort
//-----------------------------交换排序-------------------------------------------
/* 冒泡派讯 */
void BubbleSort(SeqList R)
{
//R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序
int i, j;
Boolean 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(外循环)
} //BubbleSort /* 快速排序 */
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); //对右区间递归排序
}
} //QuickSortint Partition(SeqList R, int i, int j)
{
//调用Partition(R,low,high)时,对R[low..high]做划分,
//并返回基准记录的位置
RecType pivot = R[i]; //用区间的第1个记录作为基准 '
while (i < j) { //从区间两端交替向中间扫描,直至i=j为止
while(i<j && R[j].key>=pivot.key) //pivot相当于在位置i上
j--; //从右向左扫描,查找第1个关键字小于pivot.key的记录R[j]
if (i < j) //表示找到的R[j]的关键字<pivot.key
R[i++] = R[j]; //相当于交换R[i]和R[j],交换后i指针加1
while(i<j && R[i].key<=pivot.key) //pivot相当于在位置j上
i++; //从左向右扫描,查找第1个关键字大于pivot.key的记录R[i]
if (i < j) //表示找到了R[i],使R[i].key>pivot.key
R[j--] = R[i]; //相当于交换R[i]和R[j],交换后j指针减1
} //endwhile
R[i] = pivot; //基准记录已被最后定位
return i;
} //partition //-----------------------------选择排序-------------------------------------------
/* 直接选择排序 */
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[0]作暂存单元
R[i] = R[k];
R[k] = R[0];
} //endif
} //endfor
} //SeleetSort多贴几种方法,参考参考当然是c的喽,不过都差不多
最好的情况下是:O(n)
最坏的情况下是:O(n*n);
平均情况是:O(n*n)
你的排序算法,确实没有见过。
不过可以看出你的程序的最坏的情况下是:O(n*n);
平均情况是:O(n*n)和插入,冒泡,选择都是一个级别的。
而且,那代码我也没有实现过~ 呵呵 一切都只是凭空想出来的 我根本就没用过 哪位仁兄有时间又刚好有聊的话就帮我给试试吧...