【数据结构】排序详解

void InsertSort(int* arr, int n);

void InserSort(int* arr, int n)
{

	for (int i = 0;i < n - 1;i++)
	{
		int end = i;
		int tmp = arr[end + 1];//将end+1的数据保存
		while (end >= 0)//每一次插入的结束条件
		{
			if (arr[end] > tmp)//end位置的数据大于end+1
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//跳出循环说明end越界 最后还要将tmp的数据放到end+1的位置上！！！
		//end+1就是0下标处
		arr[end + 1] = tmp;
	}
}

//希尔排序
void ShellSort(int* arr, int n)
{
	//给定一个长度差
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//for循环控制的是多个组的情况
		for (int i = 0;i < n - gap;i++)
		{
			int end = i;
			//与同组的数据 比较然后交换
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					//将arr[end]往后放 将arr[end+gap]往前放
					arr[end+gap] = arr[end];
					//每交换一次end就要减gap 去排序end之后的数据
					end -= gap;
				}
				else
				{
					break;
				}
			}
			//跳出循环此时 arr[end+gap]处的数据为空将tmp给arr[end+gap]
			arr[end + gap] = tmp;
		}
	}
}

//直接选择排序
void selectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		//i=begin+1 就是从第二个数据开始比较 
		//因为mini和maxi默认为第一个元素
		for (int i = begin + 1;i <= end;i++)
		{
			//比较的是数组中数据的大小 更新的是下标
			if (arr[i] > arr[maxi])
			{
				//更新最大值 注意是更新下标
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				//更新最小值 注意是更新下标
				mini = i;
			}
		}
		//跳出循环此时mini与maxi已经更新完了 
		//交换
		if (begin == maxi)//特殊情况
		{
			maxi = mini;
		}
		Swap(&arr[mini],&arr[begin]);
		Swap(&arr[maxi],&arr[end] );
		//交换完了begin往后走 end往前走 缩小范围
		begin++;
		end--;
	}
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	//最后一个函数栈帧所执行的内容 
	//left都大于right了所以就没法找了直接return
	if (left >= right)
	{
		return;
	}
	//分两步
	//第一步找基准值
	int keyi = _QuickSort1(arr,left,right);
	//int keyi = _QuickSort2(arr, left, right);

	//找到基准值后 第二步 递归！
	//left keyi right
	//左序列[left,keyi-1]     右序列[keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

//hoare版本找基准值
int _QuickSort1(int* arr, int left, int right)
{
	int keyi = left;
	//left从基准值第二个数开始找起
	++left;
	while (left <= right)//这个是大前提
	{
		//lerft找大于基准值 所以小于基准值就加加
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		//right找小于基准值 所以大于基准值就减减
		while (left<=right && arr[right]>arr[keyi])
		{
			right--;
		}
		//到这说明left与right都找到了 交换！
		//交换的前提是left<right 
		if (left <= right)
		{
			//交换后left往后走 right往前走 所以left++ right--
			Swap(&arr[left++], &arr[right--]);
		}
	}
	//跳出循环说明left>right 此时将基准值处的数据与right处的数据交换
	Swap(&arr[keyi], &arr[right]);

	//最后返回基准值 right处的数据
	return right;
}

//lomuto版本找基准值
int _QuickSort2(int* arr, int left, int right)
{
	int key = left;
	int prev = left, cur = prev + 1;
	while (cur <= right)
	{
		//cur要找小于基准值的数据 如果大于就继续往后走
		if (arr[cur] < arr[key] &&cur!=++prev)
		{
			Swap(&arr[prev], &arr[cur]);;
		}
		//交换完cur往后走++ 没找到cur也++
		cur++;
	}
	//走到这cur已经越界 那么就要让key位置的数据与prev处的数据交换
	Swap(&arr[key], &arr[prev]);
	//返回的是prev处基准值的下标
	return prev;

}

void swap(int*x,int*y)
{
	int tmp=*x;
	*y=*x;
	*x=tmp;
}

//三路划分
void QuickSort(int*arr,int left,int right)
{
	
	if(left>right)
	{
		return;
	}
	int begin=left;
	int end=right;
	
	
	//随机选key
	int randi=left+(rand()%right-left+1);
	swap(&arr[randi],&arr[left]);
	
	int cur=begin+1;
	int key=arr[left];
	while(left<=right)
	{
		//小于基准值与left交换left++ cur++
		if(arr[cur]<key)
		{
			swap(&arr[cur],&arr[left]);
			cur++;
			left++;
		}
		//大于基准值与right交换 right--
		else if(arr[cur]>key)
		{
			swap(&arr[cur],&arr[right]);
			right--;
		}
		//等于基准值cur++
		else
		{
			cur++;
		}
	}
	//跳出循环 cur大于right说明中间已经全为基准值了，再递归左右子区间排序
	//左区间[begin,left-1]
	QuickSort(arr,begin,left-1);
	//右区间[right+1,end]
	QuickSort(arr,right+1,end);
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	//最后一个函数栈帧所执行的内容 
	//left都大于right了所以就没法找了直接return
	if (left >= right)
	{
		return;
	}
	//分两步
	//第一步找基准值
	//int keyi = _QuickSort1(arr,left,right);
	int keyi = _QuickSort2(arr, left, right);

	//找到基准值后 第二步 递归！
	//left keyi right
	//左序列[left,keyi-1]     右序列[keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

//非递归版本的快速排序——栈
void QuicSortNoR(int* arr, int left, int right)
{
	//定义栈
	ST st;
	StackInit(&st);
	//将给定的左右下标入栈
	StackPush(&st, left);
	StackPush(&st, right);
	//只要栈不为空就循环取栈顶 更新区间
	while (!StackEmpty(&st))
	{
		//取栈顶
		int end = StackTop(&st);//先取的是右边的范围 
		StackPop(&st);
		int begin = StackTop(&st);//后取的是左边的范围
		StackPop(&st);

		//取完栈顶有了范围后根据begin与end使用lomuto找基准值
		int keyi = begin;
		int prev = begin, cur = prev + 1;
		while (cur <= end)
		{
			//cur要找小于基准值的数据 如果大于就继续往后走
			if (arr[cur] < arr[keyi] && cur != ++prev)
			{
				Swap(&arr[prev], &arr[cur]);
			}
			//交换完cur往后走++ 没找到cur也++
			cur++;
		}
		//走到这cur已经越界 那么就要让key位置的数据与prev处的数据交换
		Swap(&arr[keyi], &arr[prev]);
		//交换后下标也要变化
		keyi = prev;
		//begin keyi end
		//左序列：[begin,keyi-1]  右序列：[keyi+1,end];
		//找到基准值后 就要划分左右区间 直到left大于right的区间不会入栈就会跳出循环、
		//所以入栈的条件是当left<right的时候入栈
		if (keyi + 1 < end)//右区间
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, end);
		}
		if (begin < keyi - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, keyi-1);
		}
	}
	StackDestroy(&st);
}

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				Swap(&arr[i - 1], &arr[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

//归并排序
void MergeSort(int* arr, int n)
{
	//开辟一个临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	//递归分解 合并数组
	_MergeSort(arr, 0, n - 1, tmp);
	//最后释放空间
	free(tmp);
	tmp = NULL;
}

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	//首先是递归
	if (left == right)
	{
		return;
	}
	//定义mid将数组二分
	int mid = (left + right) / 2;
	//有了左右区间继续二分递归
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//走到这说明最小的右区间已经返回了‘
	//合并 定义begin和end防止left与right改变
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		//比较begin1与begin2 谁小放谁
		if (arr[begin1] > arr[begin2])
		{
			tmp[index++] = arr[begin2++];
		}
		else
		{
			tmp[index++] = arr[begin1++];
		}
	}
	//到这要么begin1越界 要么begin2越界
		
	//begin1没越界导入begin1
	while (begin1<=end1)
	{
		tmp[index++] = arr[begin1++];
	}
	//begin2没越界导入begin2
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}
	//最后将临时数组的数据导入到原数组中
	//[left,right]
	for (int i = left;i <= right;i++)
	{
		arr[i] = tmp[i];
	}
}

//归并排序的非递归
void MergeSortNor(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	int gap = 1;
	while (gap <= n)
	{
		//分区间
		for (int i = 0;i <n ;i*=2*gap)
		{
			int begin1 = i, end1 = i + gap-1;
			int begin2 = i + gap, end2 = i + gap - 1 + gap;
			int index = i;//tmp数组的下标
			//特殊处理如果左右不能完全二分 则begin2 或end2否可能越界
			if (begin2 > n)
			{
				//进入下一次的分组
				break;
			}
			if (end2 > n)
			{
				//此时一个数据有一个不同的区间
				end2 = n - 1;
			}
			//分好区间就要合并 两个有序序列进行合并
			while (begin1 < end1 && begin2 < end2)
			{
				//这里不用去比较end1与end2 因为begin1和begin2会++ 走到相应的end上
				//再去进行比较
				if (arr[begin1] > arr[begin2])
				{
					tmp[index++] = arr[begin2++];
				}
				else
				{
					tmp[index++] = arr[begin1++];
				}
			}
			//跳出循环 两种情况
			while (begin1 < end1)
			{
				//左右不均分有多余的继续插入到后面
				tmp[index++] = arr[begin1++];
			}
			while (begin2 < end2)
			{
				tmp[index++] = arr[begin2++];
			}
			//最后再将临时数组中的数据导入到原数组中
			//end2为左边子数组最后一个边界 因此可以确定数据个数 
			memcpy(arr + i, tmp + i,sizeof(end2-i+1));
		}
		gap *= 2;
	}
}

//计数排序
void CountSort(int* arr, int n)
{
	//找最大最小值确定count数组大小
	int max = arr[0], min = arr[0];
	for (int i = 0;i < n;i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	//到这已经找到了最大最小值 
	int range = max - min + 1;
	//根据range开辟count数组
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//到这开辟成功 数据换下标
	//对count数组初始化 使用memset
	memset(count, 0, sizeof(int) * range);
	//循环count 使用差值法
	for (int i = 0;i < n;i++)
	{
		count[arr[i] - min]++;
	}
	

	//将count数组中的数据导入到原数组中
	int index = 0;
	for (int i = 0;i < range;i++)
	{
		
		while (count[i]--)
		{
			//能进入循环说明count的改下标处存的数据是不为0的
			//使用while循环，递减该下标的值即次数
			arr[index++] = i + min;
		}
	}
}

/ 测试排序的性能对⽐
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int)*N);
	int* a2 = (int*)malloc(sizeof(int)*N);
	int* a3 = (int*)malloc(sizeof(int)*N);
	int* a4 = (int*)malloc(sizeof(int)*N);
	int* a5 = (int*)malloc(sizeof(int)*N);
	int* a6 = (int*)malloc(sizeof(int)*N);
	int* a7 = (int*)malloc(sizeof(int)*N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	} 
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort(a5, 0, N-1);
	int end5 = clock();
	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();
	int begin7 = clock();
	BubbleSort(a7, N);
	int end7 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}