C语言实现快排（荷兰国旗问题）

问题一：

• 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
  

  
  

  要求额外空间复杂度0(1)，时间复杂度O(N)

解法一：

关于这个问题，左程云（左神）的解法是创建两个标志（可以是指针），第一个标志指向左侧的移动范围用L表示，第二个标志指向数组的元素用i表示。

从左到右依次遍历数组

当数组中的数小于目标数字时，并且交换L位和i位的数字，L和i都左移

当数组中的数不小于目标数字时，i左移，L不移动

当i元素越界后结束判断表示已经分边 *** 作完成

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
void ExChange(int* arr, int x, int y)
{
	int temp = 0;
	temp = *(arr + x);
	*(arr + x) = *(arr + y);
	*(arr + y) = temp;
}

/*arr: 数组
 *cpm: 需比较的数字
 *size: 数组大小
 */

void Fun(int* arr, int cpm, int size)
{
	int L = 0;
	int i = 0;
	while (i < size)
	{
		if (arr[i] < cpm)                //目标数字小于num
		{
			ExChange(arr, L++, i++);     //交换L位置和i位置的数字，并将他们右移
		}
		else                             //目标数字不小于num
		{
			i++;
		}
	}
}

int main()
{
	int arr[] = { 1, 5, 2, 3, 1, 4, 2, 3 };
	int num = 4;
	Fun(arr, num, sizeof(arr) / sizeof(arr[0]));

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

解法二：

可以使用左右两个指针依次向中间收缩的方式遍历数组，分别用left和right表示

当left位数字小于num，则left左移

当left位数字不小于num，则判断right位数字是否大于num

                若right大于等于num，则right左移

                若right小于num，则将此时left位和right位交换

当left和right重合表示分边 *** 作完成。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 

void ExChange(int* x, int* y)
{
	int temp = 0;
	temp = *x;
	*x = *y;
	*y = temp;
}

void SeparateSort(int *arr, int num, int size)
{
	int* left = arr;
	int* right = arr + size - 1;
	while (right > left)
	{
		if (*left < num)                //left位的数字小于num
			left++;                     //left右移
		else                            //left位数字不小于num
		{
			if (*right >= num)          //right位的数字大于等于num
				right--;                //right位左移
			else                        //当left位数字不小于num且right位数字小于num才执行
				ExChange(left,right);
		}
	}
}

int main()
{
	int arr[] = {1,5,2,3,1,4,2,3};
	int sz = sizeof(arr) / sizeof(arr[0]);
	int num = 3;
	SeparateSort(arr, num, sz);

	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;

}

问题二：荷兰国旗

•  给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
  

  
  

  要求额外空间复杂度0(1)，时间复杂度0(N)。
  

  
  

解题思路：

左程云（左神）的解法是创建三个标志，其中两个标志分别表示左边界和右边界(left和right)，一个标志表示遍历数组的位置标志(i)

左边界内存放比num小的元素，右边界内存放比num大的元素，中间存放未遍历和判断的元素和与num相等的元素。

 以 i 为指针遍历数组（使用下标也可以）

当 i 位置元素小于num时，将 left 位和 i 位置的元素相互交换，并且 left 位和 i 位都向右移一位

当 i 位置元素等于num时，将i++，即向右移一位

当 i 位置元素大于num时，将 right 位和 i 位置的元素相互交换，并且只将right 位向左移一位

（right与i位置交换 i 不移位，在下一次进入时判断的就是原本right位置的，被交换到 i 位的元素）

在 i 移动越过 right时表示排列完毕

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 

//荷兰国旗问题
void ExChange(int* x, int* y)
{
	int temp = 0;
	temp = *x;
	*x = *y;
	*y = temp;
}

void SeparateSort(int *arr, int num, int size)
{
	int* left = arr;
	int* right = arr + size - 1;
	int* i = arr;
	while (i <= right)
	{
		if (*i < num)                //小于时交换left和i
		{
			ExChange(left++, i++);
		}
		else if (*i == num)          //等于时跳过当前元素
			i++;
		else                         //大于num时与right位交换
		{
			ExChange(right--, i);
		}
	}
}

int main()
{
	int arr[] = { 1, 5, 2, 3, 1, 4, 2, 3, 2,3,1,2,4,5,3,2 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int num = 3;
	SeparateSort(arr, num, sz);

	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;

}

问题三：

• 试着写出一个排序算法，使时间复杂度小于O(N^2)，额外空间复杂度O(1)。
  

  
  

基于现在所学的知识，我所知的时间复杂度小于O(N^2)的算法只有归并排序，但是归并排序额外空间复杂度为O(1)，不符合要求，所以这里不选用这种做法。

将荷兰国旗问题进行深度修改，即可找到新的题解。

解题思路：

排序思路与上个问题基本相同，主要有几个不同点：

1、需要创建一个能容纳两个元素的堆空间，作为暂时存放该次 *** 作中左边界终点和右边界起点。

2、进行递归 *** 作，分别对左侧和右侧进行分边 *** 作，直到 right < left 为止

3、需要随机数来随机取出区间内的一个数来作为num分界点的值，将它和边界上最后一个数字交换，以便在子函数中取用。

这里使用时间戳来实现。

为什么一定要随机数呢？因为当该方法固定取出尾部数字作为分界点值，那么当数组为递增的有序数组时，时间复杂度为O(N^2)，所以取用随机值可以避免这种情况。

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
#include 
#include  

//快排3.0
void ExChange(int* arr, int x, int y)
{
	int temp = 0;
	temp = *(arr + x);
	*(arr + x) = *(arr + y);
	*(arr + y) = temp;
}

int *Fun(int* arr, int left, int right)
{
	int* pf = (int*)malloc(sizeof(int) * 2);    //创建存储空间分别存储
	memset(pf, 0, sizeof(int) * 2);
	int cpm = arr[right];                //将本次排序的终点元素取出作为比较num
	int i = left;
	while (i <= right)
	{
		if (arr[i] < cpm)
		{
			ExChange(arr, left++, i++);
		}
		else if (arr[i] == cpm)
			i++;
		else
		{
			ExChange(arr, right--, i);
		}
	}

	*(pf + 1) = i--;        //存右边元素起点
	while (arr[i] == cpm)
		i--;
	*pf = i;                //存左边元素终点
	return pf;
}
void SeparateSort(int *arr, int left, int right)
{
	int *pf = NULL;
	if (left >= right)
	{
		return;
	}
	ExChange(arr, left + rand() % (right - left), right);	//随机取数与最后以一个交换
	
	pf = Fun(arr, left, right);								//排序
	SeparateSort(arr, left, *pf);							//左排序
	SeparateSort(arr, *(pf + 1), right);					//右排序

	free(pf);
	pf = NULL;
}

int main()
{
	srand((unsigned)time(NULL));

	int arr[] = { 1, 5, 2, 3, 1, 4, 2, 3, 2, 3, 1, 2, 4, 5, 3, 2 };

	SeparateSort(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1);

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;

}

 注：参考链接：一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV13g41157hK?p=3&spm_id_from=pageDriver