c-实现选择、直接插入、堆、希尔排序

  • 时间:
  • 浏览:
  • 来源:互联网
选择排序、直接插入排序、堆排序、希尔排序
```c
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct heap
{
	int *a;
	int n;
	int capacity;
}heap;
//实现直接插入排序-直接插入排序的时间复杂度为O(n*n)
void insertsort(int *a, int n)
{
	//[0,end] 把一个插入到已经排好序的数组里面
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;//[0,end]-这是一个已经排好序的数组
		int temp = a[i + 1];//temp保存将要排序的那个数
		while (end >= 0)
		{
			if (a[end] > temp)//如果排序的数比已经有序的数组里面的数要小,就向后移动,
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;//找到正确的位置之后,将temp进行插入
	}
}
//实现希尔排序-希尔排序分两步:1.预排序(数组接近于有序);2.直接插入排序 
//时间复杂度为O(N*1.3)
void shellsort(int *a, int n)
{
	//1.gap
	//2.gap组同时进行排序[0,end](间隔gap)
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//缩小gap;+1保证最后一次gap=1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;//里面做的跟一趟直接排序是一样的思路,只是不是+1,而是+gap
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else {
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}
void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void printsort(int *a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
//实现选择排序-一次选一个最大的和最小的
void selectsort(int *a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int max = end;//将最大值的下标记录在max当中,
		int min = begin;//将最小值的下标记录在min当中,
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[max])
				max = i;//遇到比a[max]大,则更新下标
			if (a[i] < a[min])
				min = i;//遇到比a[min]小,同样更新下标
		}
		//1.从这里出来之后max保存了最大值的下标,min保存了最小值的下标
		//2.交换,使得最大值和最小值到达相应的位置
		swap(&a[end], &a[max]);
		if (max == begin)
		{
			max = min;
		}
		swap(&a[begin], &a[min]);

		begin++;
		end--;
	}
}
//实现堆排序,如果排升序就应该建立大根堆,向下调整,把数组里面的数看成完全二叉树。
//1.向下调整函数。
void adjustdown(int *a, int n,int root)//数组,数组长度,结点
{
	int parent = root;
	int child = 2 * parent + 1;
	//1.找出大的孩子
	if (a[child] < a[child + 1] && child+1<n)
	{
		child++;
	}
	while(child < n)
	{
		if (a[parent] < a[child])
		{
			int temp = a[parent];
			a[parent] = a[child];
			a[child] = temp;
		}
		parent = child;
		child = 2 * parent + 1;
	}
}
//2.建立堆
int* createheap(int *a, int n)
{
	heap* hp = (heap*)malloc(sizeof(heap));
	hp->a = (int*)malloc(sizeof(int)*n);
	memcpy(hp->a, a, sizeof(int)*n);
	hp->n = n;
	hp->capacity = n;
	//从倒数第一个非叶子结点开始,进行向下调整
	for(int i = (n - 2) / 2; i >= 0; i--)
	{
		adjustdown(hp->a, hp->n, i);
	}
	return hp->a;

}
//3.堆排序
int* heapsort(int *a, int n)
{
	//1.建堆
	/*for (int i = (n - 2) / 2; i >= 0; i--)
	{
		adjustdown(a, n, i);
	}*/
	int*p=createheap(a, n);
	//2.将最大的数放在最后,然后n-1,依次调整堆。
	int end = n - 1;
	/*while (end)
	{
		int temp = a[0];
		a[0] = a[end];
		a[end] = temp;
		adjustdown(a, end, 0);
		end--;
	}*/
	while (end)
	{
		int temp = p[0];
		p[0] = p[end];
		p[end] = temp;
		adjustdown(p, end, 0);
		end--;
	}
	return p;
}


int main()
{
	int a[] = { 5,2,4,1,6,3,3};
	int sz = sizeof(a) / sizeof(a[0]);
	int *p;
	p = NULL;
//	insertsort(a, sz);
//  printsort(a, sz);

//	shellsort(a, sz);
//	printsort(a, sz);

	//selectsort(a, sz);
	//printsort(a, sz);

	//p=createheap(a, sz);
	//printsort(p,sz);
	p=heapsort(a, sz);
	printsort(p, sz);
	return 0;
}

本文链接http://www.dzjqx.cn/news/show-617023.html