本文共 5997 字，大约阅读时间需要 19 分钟。

#pragma once#include 
   
    #include 
    
     #include 
     
      #define N 100000000#define M 100#define SWAP(a,b) {int tmp; tmp = a; a = b; b = tmp;}void arrPrint(int* arr);void arr_bubble(int* arr);  //冒泡排序void arr_select(int* arr);  //选择排序void arr_Insert(int* arr);  //插入排序void Binary_Insert_sort(int* arr); //二分插入排序void shell_sort(int* arr);  //希尔排序int partition(int* arr, int left, int right);  //快速排序void arr_quick(int* arr, int left, int right);void arr_Heap(int* arr);         //堆排void adjust_Max_Heap(int* arr, int adjustPos, int arrLen);void heapSort(void* arr, size_t num, size_t size, int(*compare)(const void* a, const void* b));    //堆排类似快排sqort()的API接口void heapMax(void* arr, void* dadStartAddr, int len, int code_Num, int size, int(*compare)(const void* a, const void* b));void swap(char* a, char* b, int len);
     
    
   

#include "sort.h"void arrPrint(int* arr){
   	int i;	for (i = 0; i < N; i++)	{
   		printf("%3d", arr[i]);	}	printf("\n");}void arr_bubble(int* arr){
   	int i, j;	for (i = N - 1; i > 0; i--)	{
   		for (j = 0; j < i; j++)		{
   			if (arr[j] > arr[j + 1])			{
   				SWAP(arr[j], arr[j + 1]);			}		}	}}void arr_select(int* arr){
   	int i, j, min_pos;	for (i = 0; i < N - 1; i++)	{
   		min_pos = i;		for (j = i + 1; j < N; j++) 		{
   			if (arr[min_pos] > arr[j])			{
   				min_pos = j;			}		}		SWAP(arr[i], arr[min_pos]);	}}void arr_Insert(int* arr){
   	int i, j, insertval;	for (i = 1; i < N; i++)	{
   		insertval = arr[i];		for (j = i - 1; j >= 0; j--)		{
   			if (arr[j] > insertval)			{
   				arr[j + 1] = arr[j];			}			else {
   				break;			}		}		arr[j + 1] = insertval;	}}void Binary_Insert_sort(int* arr){
   	int middle;	for (int i = 1; i < N; i++)	{
   		int insertNum = arr[i];		int left = 0;		int right = i - 1;		while (left <= right)		{
   			middle = (left + right) / 2;			if (insertNum > arr[middle])			{
   				left = middle + 1;			}			else {
   				right = middle - 1;			}		}		for (int j = i; j > left; j--)		{
   			arr[j] = arr[j - 1];		}		arr[left] = insertNum;	}}void shell_sort(int* arr){
   	int gap, i, j;	int insertval;	for (gap = N >> 1; gap > 0; gap >>= 1)	{
   		for (i = gap; i < N; i++)		{
   			insertval = arr[i];			for (j = i - gap; j >= 0; j -= gap)			{
   				if (arr[j] > insertval)				{
   					arr[j + gap] = arr[j];				}				else {
   					break;				}			}			arr[j + gap] = insertval;		}	}}int partition(int* arr, int left, int right){
   	int i;	int k = left;	for (i = left; i < right; i++)	{
   		if (arr[i] < arr[right])		{
   			SWAP(arr[k], arr[i]);			k++;		}	}	SWAP(arr[right], arr[k]);	return k;}void arr_quick(int* arr, int left, int right){
   	int pivot;	if (left < right)	{
   		pivot = partition(arr, left, right);		arr_quick(arr, left, pivot - 1);		arr_quick(arr, pivot + 1, right);	}}/*堆排是从底向上的调整方式最后一个父亲节点的位置是 N / 2 - 1（数组是从0开始的）假设数组中有10个元素将最大的元素放在数组的最后这时候树中需要排序的数量减1，剩下9个元素在这9个元素中，只有刚才顶部交换的元素不符合大顶堆，其他元素都符合大顶堆再对现在的顶部元素的位置调用刚才的函数接口adjust_max_heap该函数接口运行一次只调整一个节点。调整后，再将该元素和数组中的倒数第二个元素进行交换，数组的len会不断变小堆排的所有时间复杂度都是nlog2n*/void adjust_Max_Heap(int* arr, int adjustPos, int arrLen){
   	int dad = adjustPos;   //adjustPos是要调整的节点位置	int son = 2 * dad + 1;	while (son < arrLen)    //arrLen代表数组的长度	{
   		if (son + 1 < arrLen && arr[son] < arr[son + 1]) //比较左孩子和右孩子，如果右孩子大于左孩子，将son加1，从而下一步拿右孩子与父亲比较		{
   			son++;		}		if (arr[dad] < arr[son])		{
   			SWAP(arr[dad], arr[son]);			dad = son;			son = 2 * dad + 1;		}		else		{
   			break;		}	}}void arr_Heap(int* arr){
   	int i;	//将数组调整为大根堆	for (i = N / 2 - 1; i >= 0; i--) //从数组中最后一个dad节点进行调整	{
   		adjust_Max_Heap(arr, i, N);	}	SWAP(arr[0], arr[N - 1]);//交换顶部与最后一个元素	for (i = N - 1; i > 1; i--)	{
   		adjust_Max_Heap(arr, 0, i); //将剩余9个元素再次调整为大根堆，不断交换根部元素与数组尾部元素，然后调整的堆元素个数减一		SWAP(arr[0], arr[i - 1]);//交换顶部元素与堆中最后一个元素，已经在尾部排好的不算堆中元素	}}/*以下的代码为对堆排的函数进行接口封装，与快排的API相对应：void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );*///每个参数的意义与qsort是一致的void heapSort(void* arr, size_t num, size_t size, int(*compare)(const void* a, const void* b)){
   	int i;	for (i = num / 2 - 1; i >= 0; i--) {
   		//heapMax的形参分别是数组首地址，开始需要判断节点的起始地址，数组的长度，节点的数组下标，单个元素大小，比较函数compare		heapMax(arr, (char*)arr + i * size, num, i, size, compare);	}	swap((char*)arr, (char*)arr + (num - 1) * size, size);	for (i = num - 1; i > 1; i--) {
   		heapMax(arr, arr, i, 0, size, compare);		swap((char*)arr, (char*)arr + (i - 1) * size, size);	}}//因为我们不知道每个元素的大小，因此交换时只能每个字节的移动，交换两个元素的内存void swap(char* a, char* b, int len) {
   	char temp;	while (len--) {
   		temp = *a;		*a++ = *b;  //将b的值取出赋值给a,然后a的地址加1		*b++ = temp;	}}//dadStartAddr是要调整的父节点的起始地址，len是数组长度//code_Num是父节点在数组中的下标值,size是每个元素的大小void heapMax(void* arr, void* dadStartAddr, int len, int code_Num, int size, int(*compare)(const void* a, const void* b)){
   	char* dad = (char*)dadStartAddr;	char* son = (char*)arr + (code_Num * 2 + 1) * size;	code_Num = code_Num * 2 + 1;	while (son <= (char*)arr + (len - 1) * size)	{
   		if (son + size <= (char*)arr + (len - 1) * size && compare(son, son + size) < 0)		{
   			son = son + size;			code_Num++;		}		if (compare(dad, son) < 0)		{
   			swap(dad, son, size);			dad = son;			son = (char*)arr + (code_Num * 2 + 1) * size;			code_Num = code_Num * 2 + 1;		}		else		{
   			break;		}	}}

#include "sort.h"int compare(const void* a, const void* b){
   	return *(int*)a - *(int*)b;}int main(){
   	int i = 0;	int* arr = (int*)malloc(N * sizeof(int));	time_t start, end;	srand(time(NULL));	for (i = 0; i < N; i++)	{
   		arr[i] = rand() % M;	}	//arrPrint(arr);	/*arr_bubble(arr);	arrPrint(arr);	arr_select(arr);  	arrPrint(arr);	arr_Insert(arr);	arrPrint(arr);*/	/*Binary_Insert_sort(arr); 	arrPrint(arr);*/	/*shell_sort(arr);	arrPrint(arr);	arr_quick(arr,0,N-1);	arrPrint(arr);*/	//printf("rand success\n");	start = time(NULL);	//qsort(arr, N, sizeof(int), compare);//实现排序	arr_Heap(arr);	//heapSort(arr, N, sizeof(int), compare);	end = time(NULL);	//arrPrint(arr);	printf("use time=%d\n", end - start);//打印排序使用时间	system("pause");	return 0;}

转载地址：http://vxxmb.baihongyu.com/