江西师范大学865数据结构考研排序

#define MAXSIZE 100
typedef struct{
	int key;
	int other;
}recordtype;
typedef struct{
	recordtype r[MAXSIZE+1];
	int length;
}table;

//无哨兵插入排序
void insertsort(int a[], int n) {
	int i, j, x;
	for (i = 1; i < n; i++) 
	{
		x = a[i];
		j = i - 1;
		while (j >= 0 && a[j] > x) 
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = x;
	}
}

 //有哨兵
void insertsprt2(table* tab)
{
	int i,j;
	for (i = 2; i <= tab->length; i++)
	{
		j = i - 1;
		tab->r[0] = tab->r[i];
		while (tab->r[0].key < tab->r[j].key) 
		{
			tab->r[j + 1] = tab->r[j];
			j = j - 1;
		}
		tab->r[j + 1] = tab->r[0];
	}
}

void binarysort(table* tab)
{
	int i, j, left, right, mid;
	for (i = 2; i <= tab->length; i++)
	{
		tab->r[0] = tab->r[i];  //保存待插入元素
		left = 1; right = i - 1;
		while (left <= right) 
		{
			mid = (left + right) / 2;
			if (tab->r[i].key < tab->r[mid].key)
				right = mid - 1;
			else
				left = mid + 1;		//插入位置是left
		}
		for (j = i - 1; j >= left; j--)
			tab->r[j + 1] = tab->r[j];
		tab->r[left] = tab->r[0];
	}
}

//Shell排序
void shellinsertsort(table* tab)
{
	int i, j, d;
	d = tab->length / 2;
	while (d >= 1) {
		for (i = d + 1; i <= tab->length; i++);
		{
			tab->r[0] = tab->r[i];	//保存第i个元素
			j = i - d;	//向前找插入位置
			while (j > 0 && tab->r[0].key < tab->r[j].key)
			{
				tab->r[j + d] = tab->[j];
				j = j - d;
			}
			tab->r[j+d] = tab->r[0];
		}
		d / 2;
	}
}

void shellinsertsort(int a[], int length)
{
	int i, j, x, d;
	d = length / 2;
	while (d >= 1) 
	{
		for (i = i + d; i < length; i++)
		{
			x = a[i];
			j = i - d;
			while (x < a[j] && j>=0)
			{
				a[j + d] = a[j];
				j = j - d;
			}
			a[j + d] = x;
		}
		d / 2;
	}
}

void simpleselectsort(table* tab)
{
	int i, j, k;
	for (j = i + 1; j <= tab->length; j++)
	{
		if (tab->r[j].key < tab->r[k].key) k = j;
		if (k != i)
		{
			tab->r[0] = tab->r[k];
			tab->r[k] = tab->r[i];
			tab->r[i] = tab->r[0];
		}
	}
}

void heapsort(table* tab)
{
	int i;
	for(i=tab->length/2;i>=1;i++)
		shft(tab,i,tab->length);//堆所有元素建堆
	for(i=tab->length/2;i>=2;i--)//i表示当前堆的大小，即等待排序的元素个数
	{
		tab->r[0]=tab->r[i];
		tab->r[i]=tab->r[1];
		tab->r[1]=tab->r[0];
		shft(tab,i,i-1);
	}
}

void bubblesort(table* tab)
{
	int i, j, done;
	i = 1;
	done = 1;
	while (i <= tab->length && done)	//最多进行tab->length次排序
	{
		done = 0;
		for(j=1;j<=tab->length;j++)
			if (tab->r[j + 1].key < tab->r[j].key)
			{
				tab->r[0] = tab->r[j];
				tab->r[j] = tab->r[j + 1];
				tab->r[j + 1] = tab->r[0];
				done = 1;
			}
		i++;
	}
}

void quicksort(table* tab, int left, int right)
{
	int i, j;
	if (left < right)
	{
		i = left; j = right;
		tab->r[0] = tab->r[i];
		
		do {
			while (tab->r[j].key > tab->r[0].key && i < j) 
				j--;
			if (i < j)
			{
				tab->r[i].key = tab->r[j].key;
				i++;
			}
			while (tab->r[i].key < tab->r[0].key && i < j)
				i++;
			if (i < j)
			{
				tab->r[j].key = tab->r[i].key;
				j--;
			}
		} while (i != j);
		tab->r[i]=tab->r[0];
		quicksort(tab, left, i - 1);
		quicksort(tab, i + 1, right);
	}
}

8.二路归并排序
9.基数排序