快速排序_算法思想

大家好，欢迎来到IT知识分享网。

1.先从数列中取出一个数作为基准数

2.将比这个数大的数全放到他的右边，小于或等于他的数全部放在他的左边

3.再对左右区间重复第二步，直到各区间只有一个数

int quickSortPartition(int arr[], int start, int end)
{
	int i = start;
	int j = end;
	
	//默认第一个元素为哨兵
	int sentry = arr[i];
	
	while(i < j)
	{
		//从右往左找第一个小于哨兵的元素
		while(i < j && arr[j] >= sentry)
		{
			j--;
		}
		
		//找到了 
		if(i < j)
		{
			arr[i] = arr[j];
			i++;
		}
		
		//从左往右找第一个大于哨兵的元素
		while(i <j && arr[i] <= sentry)
		{
			i++;
		}
		
		//找到了 
		if(i < j)
		{
			arr[j] = arr[i];
			j--;
		}
	}
	
	//把哨兵放到i == j的位置上
	arr[i] = sentry;
	
	return i;
}

void quickSort(int arr[], int start, int end)
{
	if (start < end)
	{
		//找出分界点 
		int index = quickSortPartition(arr, start, end);
		quickSort(arr, start, index - 1); //对分界点左边进行排序 
		quickSort(arr, index + 1, end);   //对分界点右边进行排序
	}
}

void quickSortEntry(int arr[], int count)
{
	quickSortEntry(arr, 0, count - 1);
}