排序算法--快速排序的两种遍历方法(C#)

快速排序简称快排，快速排序的平均时间复杂度为O(nlogn)，空间复杂度O(logn)，比起时间复杂度O(n^2)如冒泡排序，省了非常多的运行时间，故称快速排序。

快速排序的思路是分治法。
单边和双边循环法 仅仅是找到每次递归的确定基准值的方式不一样

单边循环法： 一个指针代表边界索引，从头开始，将小于基准值的放入左边，并更新指针

//单边和双边循环 仅仅是找到每次递归的基准值的方式不一样
private int Partition(int[] arr, int start, int end)
{
	//分段基准值，大于此值的往右放，小于的往左放。
	int pivot = arr[start];

	//记录小于基准值的边界索引。
	int mark = start;

	//每找到一个小于基准值的数据，边界加1，并交换小值与边界当前值，让小值落入边界内。
	for(int i = start + 1; i <= end; i++)
	{
		if(arr[i] < pivot)
		{
			mark++;
			int temp = arr[i];
			arr[i] = arr[mark];
			arr[mark] = temp;
		}
	}

	//将基准值与边界值交换位置，使基准值落入边界处
	arr[start] = arr[mark];
	arr[mark] = pivot;

	//返回边界索引
	return mark;
}
private void QuickSort(int[] arr, int start, int end)
{
	//走到一起说明这一段排好了
	if( start >= end)
		return;

	//找出基准位置
	int pivotIndex = Partition(arr, start, end);
	//排左边
	QuickSort(arr, start, pivotIndex - 1);
	//排右边
	QuickSort(arr, pivotIndex + 1, end);
}
private void Main()
{
	int[] nums = new int[10]{5,6,1,4,7,8,0,11,54,2};
	QuickSort(nums, 0, nums.Length -1);
}

双边循环法： 两个指针，从两头开始找需要交换位置的值进行交换

//单边和双边循环 仅仅是找到每次递归的基准值的方式不一样
private int Partition(int[] arr, int start, int end)
{
	//以首位作为基准（也可以随机一个做为基准）
	int pivot = arr[start];

	//因为要使用start，所以换个值去走循环
	int left = start;
	int right = end;

	//双边只要没走到一起就继续
	while(left != right)
	{
		//右指针先走，直到找到小于基准值的位置停下
		while(left < right && arr[right] > pivot)
			right--;

		//左指针再走，直到找到大于基准值的位置停下
		while(left < right && arr[left] <= pivot)
			left++;

		//如果没碰头，那么交换两个指针指向的内容，使大的落入右边，小的落入左边。
		if(left < right)
		{
			int temp = arr[right];
			arr[right] = arr[left];
			arr[left] = temp;
		}
	}

	//交换开始的基准 和 上面循环走完后找到的边界位置，使基准值落入边界位
	arr[start] = arr[left];
	arr[left] = pivot;

	//返回边界索引
	return left;
}
private void QuickSort(int[] arr, int start, int end)
{
	//走到一起说明这一段排好了
	if( start >= end)
		return;

	//找出基准位置
	int pivotIndex = Partition(arr, start, end);
	//排左边
	QuickSort(arr, start, pivotIndex - 1);
	//排右边
	QuickSort(arr, pivotIndex + 1, end);
}
private void Main()
{
	int[] nums = new int[10]{5,6,1,4,7,8,0,11,54,2};
	QuickSort(nums, 0, nums.Length -1);
}