博客

• 排序算法之 冒泡排序及性能优化（时间复杂度+空间复杂度分析）
• 排序算法之 简单选择排序及时间复杂度分析
• 排序算法之 直接插入排序及时间复杂度分析
• 排序算法之 希尔排序及时间复杂度分析

快速排序

科普： 快速排序算法最早由图领奖获得者Tony Hoare设计出来的，是上世界最伟大的计算机科学家之一。更牛的是，快速排序算法被列为20世界十大算法之一。
基本思想：挖坑法+分治法

• 从序列中选择一个基准数pivot [可以选择序列中的第一个数为pivot]
• 将序列中所有数依次遍历，同时比基准数pivot大的放在其右侧，比基准数小的放在其左侧
• 分别对左右子序列重复以上两步操作

分享一个b站视频，通俗易懂：https://www.bilibili.com/video/BV1at411T75o

算法实现

void QuickSort(int array[], int L, int R)
{
	if(L>R) return;
	int left = L,right = R;
	int pivot = array[left];
	while(left<=right)
	{
		//从右开始向左寻找第一个小于pivot的值
		while(left<right && array[right]>=pivot)
			right--;
		if(left<right)
			array[left] = array[right];
		//从左开始向右寻找第一个大于pivot的值
		while(left<right && array[left]<=pivot)
			left--;
		if(left<right)
			array[right] = array[left];
		if(left >= right)
			array[left] = pivot;
	}
	QuickSort(array, L, right-1);
	QuickSort(array, right+1, R);
}

时间复杂度

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。