数据结构6种排序方法

大学课程、数据结构、C代码、 以下问题要求统一在一个大程序里解决。 1折半插入排序 2冒泡排序 3快速排序 4简单选择排序 5归并排序 6堆排序

// chazhao.cpp : Defines the entry point for the console application.
//以下问题要求统一在一个大程序里解决。
//1折半插入排序//2冒泡排序//3快速排序
//4简单选择排序//5归并排序//6堆排序

#include “stdafx.h“
#include “stdio.h“
#include “malloc.h“
#include “stdlib.h“
#define MAX 6
#define BOOL int
#define TRUE 1
#define FALSE 0

typedef struct{     //结构体
	int  key;
}BIAO;
typedef struct{				//定义线性表的存储形式
	BIAO r[MAX];
	int length;
	int listsize;
}SqList;

void createlist（SqList*L）	{		//创建并初始化线性表
	L->length = MAX-1;			////////////
	L->listsize = MAX;
}

SqList BiInsertionSort （ SqList L ） {		//折半插入排序
	int lowhighmij;
	for （ i=2; i<=L.length; ++i ） {
		L.r[0] = L.r[i];      // 将 L.r[i] 暂存到 L.r[0]
		low = 1;   
		high = i-1;
		while （low<=high） { 
			m = （low+high）/2;           // 折半
			if （L.r[0].key < L.r[m].key）
				high = m-1;   // 插入点在低半区
			else  
				low = m+1; // 插入点在高半区
		}
		for （ j=i-1;  j>=high+1; --j ）
			L.r[j+1] = L.r[j];      // 记录后移
		L.r[high+1] = L.r[0];  // 插入
	} // for
	return L;
} // BInsertSort


//2冒泡排序
SqList BubbleSort（SqList L） 
{ //R（l..n）是待排序的文件，采用自下向上扫描，对R做冒泡排序 
	int ij; 
	bool exchange = TRUE;		 //交换标志 
	for（i=1 ;i		exchange=FALSE;			 //本趟排序开始前，交换标志应为假 
		for（j=L.length-1 ;j>=i ;j--）		 //对当前无序区R[i..n]自下向上扫描 
			if（L.r[j+1].key < L.r[j].key）{//交换记录 
				L.r[0] = L.r[j+1];	 //R[0]不是哨兵，仅做暂存单元 
				L.r[j+1] = L.r[j]; 
				L.r[j] = L.r[0]; 
				exchange=TRUE;			//发生了交换，故将交换标志置为真 
			} 
			if（!exchange） //本趟排序未发生交换，提前终止算法 
				break;
	} //endfor
	return L;
} //BubbleSort 


//3快速排序
void QSort （int h[]  int s  int  t ） {			// 对记录序列R[s..t]进行快速排序
	if （s < t） {             // 长度大于1
		int i = s j = t;
		h[0] = h[i];
		while （i			while （i=h[0]） {
				j--;
			}
			h[i] = h[j];
			while （i				i++;
			}
			h[j] = h[i];
		}
		h[i] = h[0];
		QSort（h s i-1）;
		QSort（h i+1 t）;	
	}
} // QSort
void QuickSort（int h[] ） {      // 对顺序表进行快速排序
	QSort（h 1 5）;
	int i;
	printf（“快速排序后的序列为:“）;
	for（i=1 ;i<6 ;i++）
		printf（“ %d“h[i]）;
	printf（“\n“）;
} // QuickSort

//4简单选择排序 
int SelectMinKey （SqList L int i） {
	int jminp;
	min = L.r[i].key;
	p=i;
	for（j=i+1 ;j<6 ;++j） {
		
		if（ min>L.r[j].key ） {
			min = L.r[j].key;
			p = j;
		}
	}
	return p;
}
SqList SelectSort （SqList L int n ） {	// 对记录序列R[1..n]作简单选择排序。
	int ij;
	int k;
	for （i=1; i		
		j = SelectMinKey（L i）;			// 在 R[i..n] 中选择关键字最小的记录
		if （i!=j）  {
			
			k = L.r[i].key;
			L.r[i].key = L.r[j].key;
			L.r[j].key = k;		// 与第 i 个记录交换
		}
	}
	return L;
} // SelectSort

//6堆排序
void HeapAdjust （int h[] int m int n）	{  
	int temp = h[m];
	int mm = m;
	int j（0）;
	for （ j=2*mm; j<=n ; j*=2 ） { // j 初值指向左孩子
		if （ j			j++;     
		}
		if （ h[j] <= temp ）  {
			break; 
		}
		h[mm] = h[j];   
		mm = j;    
	}
	h[mm] = temp;  // 将调整前的堆顶记录插入到 s 位置
} // HeapAdjust

vo

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       7216  2014-06-17 15:34  8排序（6个方法）\chazhao.cpp

     文件       3413  2014-06-17 16:16  8排序（6个方法）\chazhao.dsp

     文件        522  2014-06-17 16:18  8排序（6个方法）\chazhao.dsw

     文件      50176  2014-06-17 16:18  8排序（6个方法）\chazhao.ncb

     文件      48640  2014-06-17 16:18  8排序（6个方法）\chazhao.opt

     文件        248  2014-06-17 16:17  8排序（6个方法）\chazhao.plg

     文件     188482  2014-06-17 16:16  8排序（6个方法）\Debug\chazhao.exe

     文件     243188  2014-06-17 16:16  8排序（6个方法）\Debug\chazhao.ilk

     文件      19610  2014-06-17 16:16  8排序（6个方法）\Debug\chazhao.obj

     文件     222980  2014-06-17 15:31  8排序（6个方法）\Debug\chazhao.pch

     文件     459776  2014-06-17 16:16  8排序（6个方法）\Debug\chazhao.pdb

     文件       1764  2014-06-06 15:40  8排序（6个方法）\Debug\StdAfx.obj

     文件      41984  2014-06-17 16:18  8排序（6个方法）\Debug\vc60.idb

     文件      53248  2014-06-17 16:16  8排序（6个方法）\Debug\vc60.pdb

     文件       1214  2014-06-06 14:40  8排序（6个方法）\ReadMe.txt

     文件        294  2014-06-06 14:40  8排序（6个方法）\StdAfx.cpp

     文件        667  2014-06-06 14:40  8排序（6个方法）\StdAfx.h

     目录          0  2012-07-02 19:24  8排序（6个方法）\Debug

     目录          0  2012-07-02 19:24  8排序（6个方法）

----------- ---------  ---------- -----  ----

              1343422                    19