您的位置: 首页  >  文章  >  《算法导论》第七章——快速排序

《算法导论》第七章——快速排序

分类: 文章 • 2023-03-10 10:00:40

  虽然写这个博客主要目的是为了给我自己做一个思路记忆录，但是如果你恰好点了进来，那么先对你说一声欢迎。我并不是什么大触，只是一个菜菜的学生，如果您发现了什么错误或者您对于某些地方有更好的意见，非常欢迎您的斧正！

7.1快速排序的描述
  我看了一下书的内容，感觉并不是很，emmmm就是很看得懂吧，可能我太菜鸡了。我们在网上看到的函数一般就是直接一个quicksort，在《算法导论》里，它把这一个函数的主体部分剥离出来为另一个函数Partition(A,p,r)，我虽然并不知道为什么要把一个函数拆分成两个函数，但是如果你知道的话，你一定要告诉我！（学长说：为了一个函数的简洁！）不过我觉得，其实不管是一个函数还是两个函数，都是比较容易理解的吧。那么我也用两个函数来写啦。

我们先看一个这个Partition函数的作用原理：
①首先我们设定一个key，left光标在数组最左边，right光标在数组最右边。
②right光标从右往左 ←，找到一个数小于key，把这个数赋值给left光标所在的位置
③left光标从左往右→，找到一个数大于key，把这个数赋值给right光标所在的位置
④重复②③步骤，直到left与right光标重合，把key赋值给这两个光标重合的位置
好的我接下来要用图解了！

《算法导论》第七章——快速排序

《算法导论》第七章——快速排序

《算法导论》第七章——快速排序


这个时候一个小循环结束了，我们的left与right没有相遇，于是我们继续执行②③

《算法导论》第七章——快速排序
《算法导论》第七章——快速排序


这个时候又一个小循环结束了，我们的left与right没有相遇，于是我们继续执行②③


《算法导论》第七章——快速排序


  至此，一个大循环结束，我们发现65左边的数都小于65,右边的数都大于65，然后我们对左边的数组和右边的数组再分别进行以上步骤，也就是一个递归的过程。比如右边的数组，我们的key就变成了91，left指向91，right指向88，经过一次小循环之后，右边的数组变成了88，91，92，就排好序了，而左边的数组，key = 3，left指向3，right指向54经过一次大循环会变成：1,3,25,53,41,54，即3左边的数小于3，右边的数大于3，此时左边完成排序了，我们再对右边的数也就是25,53,41,54进行同样的过程。

7.2快速排序的性能
最坏情况划分：θ(n²)
最好情况划分：θ(nlgn)
平衡的划分：O(nlgn)
7.3快速排序的随机化版本
  我们之前设置key的时候都是直接取arr[left]，也就是数组的第一位，如果数组是一个逆序，那么这样就容易导致最坏情况的发生，于是我们随机抽取其中一位数作为随机数。抽取之后把这个数与第一个数进行交换，接下来就与Partition一模一样了。说白了，就是随机找个数把它弄到第一位。我们知道rand()%(Y-X+1)+X的值为X-Y之间的随机数，这个也就是我们的随机实现方法。
接下来是代码部分（建议复制后自己运行一下）：

快速排序.h

#pragma once
typedef int dataType;

/*打印数组*/
void PrintQuickArray(dataType arr[], int length);

/*初始化数组*/
void InitQuickArray(dataType arr[], int length);

/*快速排序递归部分*/
void QuickSort(dataType arr[], int left, int right);

/*快速排序主体部分*/
int Partition(dataType arr[], int left, int right);

/*快速排序的随机化版本*/
int RandomPartition(dataType arr[], int left, int right);

/*快速排序测试函数*/
void TestQuickSort();

快速排序.cpp

#include "快速排序.h"
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

/*打印数组*/
void PrintQuickArray(dataType arr[], int length)
{
	for (int i = 0; i < length; i++)
	{
		cout << arr[i]<<" ";
		if ((i + 1) % 15 == 0)/*如果一排超过15个数就换行*/
			cout << endl;
	}
	cout << endl; cout << endl;
}

/*初始化数组*/
void InitQuickArray(dataType arr[], int length)
{
	srand((unsigned)time(NULL));/*建立随机数种子*/
	for (int i = 0; i < length; i++)
	{   /*一句废话：虽然这里可以不要花括号，我总觉得有了比较庄重！*/
		arr[i] = rand() % 100 + 1;/*arr[i]的值：1-100之间*/
	}
}

/*快速排序递归部分*/
void QuickSort(dataType arr[], int left, int right)
{
	if (left < right)
	{
		int middle = Partition(arr, left, right);/*arr[middle]左边的数都小于它，右边的数都大于它*/
		QuickSort(arr, left, middle - 1);/*对左边的数进行快排*/
		QuickSort(arr, middle + 1, right);/*对右边的数进行快排*/
	}
}

/*快速排序主体部分*/
int Partition(dataType arr[], int left, int right)
{
	if (left >= right)/*此时两个光标重合,代表已经整理完成一个组*/
		return 0;

	/*①首先我们设定一个key*/
	int key = arr[left];
	while (left < right)
	{
		while (left<right&&arr[right]>=key)/*②right光标从右往左 ←，找到一个数小于key*/
		{
			right--;
		}
		/*把这个数赋值给left光标所在的位置*/
		arr[left] = arr[right];
		while (left < right&&arr[left] <= key)/*③left光标从左往右→，找到一个数大于key*/
		{
			left++;
		}
		/*把这个数赋值给right光标所在的位置*/
		arr[right] = arr[left];
	}
	/*④left与right光标重合，把key赋值给这两个光标重合的位置*/
	arr[left] = key;

	/*返回重合的位置的下标*/
	return left;
}

/*快速排序的随机化版本*/
int RandomPartition(dataType arr[], int left, int right)
{
	srand((unsigned)time(NULL));/*建立随机种子*/
	int random = rand() % (right - left + 1) + left;/*random就是一个随机的位置*/
	/*将arr[random]与arr[left]进行交换*/
	dataType temp = arr[left];
	arr[left] = arr[random];
	arr[random] = temp;
	return Partition(arr,left,right);
}

/*快速排序测试函数*/
void TestQuickSort()
{
	int length;
	cout << "输入你理想的数组长度:";
	cin >> length;/*输入*/
	cout << endl;
	dataType *arr = new dataType[length];/*动态建立数组*/
	InitQuickArray(arr, length);/*初始化这个数组*/
	cout << "初始化后的数组:  ";
	PrintQuickArray(arr, length);
	QuickSort(arr, 0, length - 1);/*对这个数组进行快速排序.第length个数下标为length-1*/
	cout << "快排后的数组:    ";
	PrintQuickArray(arr, length);

	/*随机快排的测试，记得把QuickSort里的Partition换成RandomPartition*/
	/*cout << endl; cout << endl;
	cout << "随机快排后的数组:";
	PrintQuickArray(arr, length);*/
	delete[] arr;/*最后要销毁这个数组*/
}

主函数

#include "快速排序.h"
#include <stdio.h>
int main()
{
	TestQuickSort();
	getchar();
	getchar();
	return 0;
}

运行结果：

快速排序：

《算法导论》第七章——快速排序


随机快速排序：

《算法导论》第七章——快速排序

参考网站以及博客：

百度百科
https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842?fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&fromid=2084344&fr=aladdin#3_6
快速排序(三种算法实现和非递归实现)
https://blog.csdn.net/qq_36528114/article/details/78667034
快速排序（nba76ers的博客）
https://www.cnblogs.com/foreverking/articles/2234225.html

相关推荐