一起学习交流~

排序-04-快速排序,快排的两种实现

算法 laomuji 12个月前 (10-09) 398次浏览 已收录 0个评论

一、什么是快速排序

首先来看百度百科介绍

快速排序(Quicksort)是对冒泡排序算法的一种改进。

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

快速排序的平均时间复杂度也是O(nlog2n)。该排序方法被认为是目前最好的一种内部排序方法。

二、快排原理及实现

原理:

快速排序 使用分治的思想
比我小的放在左边,比我大的放在右边
然后再将左边的当作一个整体,右边的当作一个整体,比我小的放左边,比我大的放右边
再递归调用左边和右边,直到只剩下一个为止

直接讲可能不太好理解,先放一个比较容易理解的快排代码

//使用容器的方法,便于理解,但速度比不用容器稍微慢一些,但是仍然比冒泡等排序快很多
vector<int> quickSort(vector<int>nums)
{
    if (nums.size() <= 1)return nums;
    int num = nums[0];//假设最左边的数字为基准值
    vector<int>leftVector;//左边数组
    vector<int>midVector;//与基准值相等数组
    vector<int>rightVector;//右边数组
    //循环将数字添加到对应的数组里
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] < num) leftVector.push_back(nums[i]);
        else if (nums[i] > num) rightVector.push_back(nums[i]);
        else midVector.push_back(nums[i]);
    }

    //将左右两边的两个整体递归
    leftVector = quickSort(leftVector);
    rightVector = quickSort(rightVector);
    //将左 中 右 数组合并
    leftVector.insert(leftVector.end(), midVector.begin(), midVector.end());
    leftVector.insert(leftVector.end(), rightVector.begin(), rightVector.end());
    return leftVector;
}

vector数组可以当作java里的ArrayList之类的理解.

将小于,等于,大于基准值(分界值)分别放在三个数组中,

然后对小于,大于基准值的数组进行递归

每次调用都分为三个数组,直到只剩一个数字为止

不停的将三个数组进行合并然后返回,就实现了排序

通过对上面的理解,接下来写正常的快排

//循环+递归的方法
void quickSort(int nums[], int low, int high)
{
	//low 和 high 用户限定数组的开始和结束部分,nums[low]-nums[high]为一个整体
	if (low >= high)return;
	int left = low;//左边下标
	int right = high;//右边下标
	int key = nums[low];//基准值,假设为最左边的
	//在left和right的范围内进行寻找
	//先从左边或右边开始找
	while (left <= right)
	{
		while (left <high && nums[left] < key)left++;
	
		while (right > low && nums[right] > key)right--;
		if (left > right) break;

		swap(nums[left++], nums[right--]);
	}

	quickSort(nums, low, left - 1);//左边部分再次排序
	quickSort(nums, left, high);//右边部分再次排序
}
int main()
{
    int nums[] = { 5,6,2,4,3,1,7,8,9,10 };
    quickSort(nums, 0, 10 - 1);
}

把利用数组容器改为直接对原始数组操作,通过low和high来划分数组区域

喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论