[数据结构与算法]10种排序算法中常用的其中8种

//显示函数
void show_sort_result(const char* name,int* arr,size_t len)
{
	printf("%10s:",name);
	for(int i=0; i<len; i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}

//冒泡排序
void bubble_sort(int* arr,size_t len)
{
	bool flag = true;					//用于体现冒泡的数据敏感性
	for(int i=len-1; i>0 && flag; i--)
	{
		flag = false;
		for(int j=0; j<i; j++)
		{
			if(arr[j] > arr[j+1])
			{
				swap(arr[j],arr[j+1]);
				flag = true;
			}
		}
	}
	//show_sort_result(__func__,arr,len);
}

//选择排序
void select_sort(int* arr,size_t len)
{
	for(int i=0; i<len-1; i++)			//选择排序循环次数固定，相比较于冒泡，每轮交换次数只有一次
	{									//节省了用户态和内核态交换消耗的时间
		int min = i;
		for(int j=i+1; j<len; j++)
		{
			if(arr[j] < arr[min])
				min = j;
		}
		if(min != i)
			swap(arr[min],arr[i]);
	}
	show_sort_result(__func__,arr,len);
}

//插入排序
void insert_sort(int* arr,size_t len)
{
	for(int i=1,j; i<len; i++)
	{
		int tmp = arr[i];
		for(j=i-1; j>=0 && tmp<arr[j]; j--)
		{
			arr[j+1] = arr[j];
		}
		arr[j+1] = tmp;
	}
	show_sort_result(__func__,arr,len);
}

//希尔排序
void shell_sort(int* arr,size_t len)
{
	for(int k=len/2; k>0; k/=2)				//在插入的基础上加入了k，k使数据在前几轮的插入基本有序
	{
		for(int i=k,j; i<len; i++)
		{
			int tmp = arr[i];
			for(j=i-k; j>=0 && tmp<arr[j]; j-=k)
			{
				arr[j+k] = arr[j];
			}
			arr[j+k] = tmp;
		}
	}
	show_sort_result(__func__,arr,len);
}

//创建堆
void create_heap(int* arr,size_t len,int root)
{
	while(root*2 <= len)
	{
		int max = root*2;
		if(max+1<len && arr[max-1] < arr[max])
			max++;
		if(arr[root-1] > arr[max-1])
			return;
		swap(arr[root-1],arr[max-1]);
		root = max;
	}
}

//堆排序
void heap_sort(int* arr,size_t len)
{
	for(int i=len/2; i>0; i--)
		create_heap(arr,len,i);
	
	for(int i=len-1; i>0; i--)
	{
		swap(arr[0],arr[i]);
		create_heap(arr,i,1);
	}
	show_sort_result(__func__,arr,len);
}

//快速排序
void _quick_sort(int* arr,int left,int right)
{
	//版本1
	/*
	if(left >= right)
		return;
	int len = right-left+1;
	int pv = arr[left] , tmp[len] , l=0 , r=len-1;
	for(int i=left+1; i<=right; i++)
	{
		if(arr[i] < pv)
			tmp[l++] = arr[i];
		else
			tmp[r--] = arr[i];
	}
	tmp[l] = pv;
	memcpy(arr+left,tmp,len*sizeof(arr[0]));
	_quick_sort(arr,left,left+l-1);
	_quick_sort(arr,left+l+1,right);
	*/
	//版本2
	if(left >= right)
		return;

	int pi = left , pv = arr[left];
	for(int l=left,r=right; l<r;)
	{
		while(l<r && pv<=arr[r]) r--;
		if(l<r)
		{
			arr[pi]=arr[r];
			pi = r;
		}
		while(l<r && arr[l] < pv) l++;
		if(l<r)
		{
			arr[pi] = arr[l];
			pi = l;
		}
	}

	arr[pi] = pv;
	_quick_sort(arr,left,pi-1);
	_quick_sort(arr,pi+1,right);
}

void quick_sort(int* arr,size_t len)
{
	_quick_sort(arr,0,len-1);
	//show_sort_result(__func__,arr,len);
}

//归并排序
void merge_sort(int* arr,size_t len)
{
	int *dest = malloc(sizeof(arr[0])*len), *src = arr;
	for(int k=1; k<len; k*=2)
	{
		for(int i=0,j; i<len; i+=k*2)
		{
			int s1 = j= i , e1 = min(i+k,len);
			int s2 = e1 , e2 = min(i+k*2,len);
			while(s1 < e1 && s2 < e2)
			{
				dest[j++] = src[s1]<src[s2] ? src[s1++] : src[s2++];
			}
			while(s1 < e1)
				dest[j++] = src[s1++];
			while(s2 < e2)
				dest[j++] = src[s2++];
		}
		swap(dest,src);
	}
	if(src != arr)
	{
		memcpy(arr,src,sizeof(arr[0])*len);
		dest = src;
	}
	free(dest);
	//show_sort_result(__func__,arr,len);
	
}

//基数排序
void count_sort(int* arr,int len)
{
	int max = arr[0] , min = arr[0];
	for(int i=1; i<len; i++)
	{
		if(max < arr[i])
			max = arr[i];
		if(min > arr[i])
			min = arr[i];
	}
	int* count = calloc(sizeof(count[0]),max-min+1);
	for(int i=0; i<len; i++)
	{
		count[arr[i]-min]++;
	}
	for(int i=0,k=0; i<=max-min; i++)
	{
		for(int j=0; j<count[i]; j++)
		{
			arr[k++] = i+min;
		}
	}
	free(count);
	show_sort_result(__func__,arr,len);
}