选择排序&&霍尔快排_c语言_快速排序霍尔分区法

默认以升序举例

01：选择排序

void Selectsort(int* m, int size)
{
	for (int i = 0; i < size; i++)
	{
		int min = i;
		for (int j = i; j < size - i; j++)
		{
			if (m[min] > m[j])  min = j;
		}
		swap(&m[min], &m[i]);
	}
}

简单介绍一下思路：在每次进行循环时 min用来找最小的那个值的下标，找到之后和最开始的i值互换，这样每次都能找到其中最小的值,找n次之后数组有序；

时间复杂度n^2，不适合数据量大的排序；

简单的优化

void Selectsort(int* m, int size)
{
	for (int i = 0; i < size/2; i++)
	{
		int min = i;
		int max = i;
		for (int j = i; j < size - i; j++)
		{
			if (m[min] > m[j])  min = j;
			if (m[max] < m[j])  max = j;
		}
		if (min == max)
			return;
		swap(&m[min], &m[i]);//把最小的值给到开始处
		if (max == i) //此时m[min]的值为最大的
		{
			if (min == size - i-1)//代表原始数据中最大的在左边，最小的在右边,
				continue;
			swap(&m[size-i-1], &m[min]);
			continue;
		}
		swap(&m[max], &m[size - i-1]);
	}
}

思路：弄两个下标min和max，每次循环找到最大的和最小的两个值，放到两边；        

时间复杂度仍为n^2；

02：优化思路

        1：当数组长度过长时，每次循环都要花费大量时间，可以适当对数组进行简单的排序后进行拆分；

        2：进行了太多无意义的比较，想办法让每次循环进行更多有效的值替换；

03：快速排序

       ​历史背景​        快速排序算法_百度百科 (baidu.com)

      简单的介绍一下，1960年科学家霍尔提出了一种新的排序方式，因为时间复杂度为n*log(n)，俗称快排。之后的挖坑法和双指针法是以一种排序思路，不同的实现方式来实现的。相较而言挖坑和双指针较容易理解。

霍尔快排

void QuiteSort1(int*m,int begin,int end)
{
	//如果开始小于结束的话代表遍历完了直接退出
	if (begin >= end)  return;
	//找一个不是最小也不是最大的值，如果是极值的话会让排序效率变低
	int middle = midd(m, begin, end);
	swap(&m[begin], &m[middle]);
	//
	int left = begin, right = end;
	while (left < right)
	{
		//找小
		while (left < right && m[right] >= m[begin])
			right--;
		//找大
		while (left <right && m[left] <= m[begin])
			left++;
		//以m[begin]为基准，把小的放左边，把大的放右边
		if (left != right)
			swap(&m[left], &m[right]);
		else
			swap(&m[begin],& m[left]);
	}
	QuiteSort1(m, begin, left-1);
	QuiteSort1(m, left+1, end);
}

挖坑快排

void QuiteSort2(int* m, int begin, int end)
{
	//遍历完的直接退出
	if (begin >= end) return;
	//找不是极值的
	int middle = midd(m, begin, end);
	swap(&m[begin], &m[middle]);
	//
	int hole = begin, key = m[begin];
	int left = begin, right = end;
	while (left < right)
	{
		//找小
		while (right>left && m[right]>=key)
			right--;
		//把小的值放左边
		m[hole] = m[right];
		hole = right;
		//找大
		while (left < right && m[left] <= key)
			left++;
		//把大的值放右边
		m[hole] = m[left];
		hole = left;
	}
	m[hole] = key;
	QuiteSort2(m, begin, hole - 1);
	QuiteSort2(m, hole + 1, end);
}

相较霍尔的思路而言，这种方法的思路为：把开头位置的值存起来,此时把最左边的位置当坑，从右边开始找小，把小放到左边的坑，把右边找小找到的位置当坑，从左边找大，填到坑里，此时坑到左边，再去右边找小，填左坑，坑到右边，以此循环。

双指针快排

void QuiteSort3(int* m, int begin, int end)
{
	if (begin >= end)  return;
 
	int middle = midd(m, begin, end);
	swap(&m[begin], &m[middle]);
	
	int left = begin, right = left + 1;
	while (right <= end)
	{
		if (m[right] < m[begin] && ++left != right)
			swap(&m[right], &m[left]);
		right++;
	}
	swap(&m[left], &m[begin]);
 
	QuiteSort3(m, begin, left - 1);
	QuiteSort3(m, left+1, end);
}

04：非递归式快排

        非递归式快排需要按一定顺序操作数组，栈就很适合用来存储中间的信息

        做法：先把初始的数据入栈，从栈中取数据，执行一次快排，把新数据入栈，直到栈为空时跳出循环。

感谢观看！！！