建设品牌型网站,怎么制作网站视频教程,好用建站模板,网站备案 年审排序算法 —— 快速排序介绍
基本概念
快速排序#xff08;Quicksort#xff09;是一种排序算法#xff0c;最早由东尼霍尔提出。在平均状况下#xff0c;排序 n 个项目要 Ο(n log n) 次比较。在最坏状况下则需要 Ο(n2) 次比较#xff0c;但这种状况并不常见。事实上Quicksort是一种排序算法最早由东尼·霍尔提出。在平均状况下排序 n 个项目要 Ο(n log n) 次比较。在最坏状况下则需要 Ο(n2) 次比较但这种状况并不常见。事实上快速排序通常明显比其他 Ο(n log n) 算法更快因为它的内部循环inner loop可以在大部分的架构上被优化掉。
算法描述
快速排序使用分治法Divide and conquer策略来把一个串行list分为两个子串行sub-lists。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看快速排序应该算是在冒泡排序基础上做的改进。
快速排序的名字起的是简单粗暴因为一听到这个名字你就知道它是怎么排序的。它的大概思路就是找到一个基准点一般是数组中间的数然后将数组分为两个部分一部分比这个基准点小一部分比这个基准点大然后递归对这两部分排序即可。
算法步骤
选择一个基准元素将列表分割成两个子序列。对每个子序列重复步骤1直到列表只有一个元素为止。合并排序。返回排序后列表。结束。
算法伪代码
function quickSort(arr[], low, high)if (low high){// pi is partitioning index, arr[p] is now at right placepi partition(arr, low, high)// Separately sort elements before partition and after partitionquickSort(arr, low, pi - 1)quickSort(arr, pi 1, high)}优缺点
优点
通常明显比其他 Ο(n log n) 算法更快。内循环较小快速排序通常内循环较少。是一种分治算法。是递归的。是原地的。不需要额外的存储。
缺点
快速排序的最差时间复杂度是 Ο(n²)。快速排序是不稳定的。快速排序的空间复杂度是 Ο(log n)。快速排序的递归深度是 Ο(log n)。快速排序的运行时间取决于分区的方式。
常见应用场景
快速排序被广泛应用于各种应用中例如对大型数据集进行排序、实现高效的排序算法、优化算法性能等。它也用于各种数据结构如数组、链表和集合以高效地搜索和操作数据。快速排序也用于各种排序算法中例如堆排序和归并排序作为数据分区的子例程。快速排序也用于图遍历的各种算法中如深度优先搜索和广度优先搜索以高效地访问图中的所有节点。
时间复杂度
最好情况 : O(n log n)平均情况 : O(n log n)最坏情况 : O(n^2)
为什么时间复杂度是O(n log n)?
快速排序算法的时间复杂度为O(n log n)这是因为它对n个元素排序时具有线性时间复杂度而将数组划分为更小的子数组时具有对数时间复杂度。
如何避免最坏情况下的时间复杂度?
为了避免最坏情况下的时间复杂度可以使用随机版本的快速排序它随机选择基准值元素而不是使用第一个或最后一个元素。这确保了最坏的情况不会频繁发生。
空间复杂度
O(log n)
为什么空间复杂度是O(log n)?
快速排序算法的空间复杂度是O(log n)因为它使用栈来管理递归。在最坏的情况下递归树的深度可能为O(n)但由于该算法是对输入向量进行原地排序因此平均空间复杂度为O(log n)。
在每次递归调用中算法都会将输入向量划分为两个大小大致相等的子向量。然后使用相同的算法对这些子向量进行排序但输入向量更小。这个过程会一直持续直到达到基线条件(即输入向量只有一个元素)。
实现
快速排序背后的思想是什么?
快速排序是一种分而治之的排序算法它的工作原理是从数组中选择一个基准值元素并根据其他元素是否小于基准值将它们划分为两个子数组。然后对子数组进行递归排序。这可以就地完成只需要少量的额外内存来执行排序。
快速排序具有良好的平均性能但当输入数组已经排好序或逆序时其最差性能为O(n^2)。因此对于需要考虑最坏情况性能的排序算法例如针对系统库的排序算法就不使用这个参数。
非递归版本的代码
template typename T
int partition(vectorT arr, int low, int high)
{T pivot arr[high];int i low - 1;for (int j low; j high - 1; j){if (arr[j] pivot){i;swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return i 1;
}// This is a recursive quicksort code.
template typename T
void quickSort(vectorT arr, int low, int high)
{if (low high){int pivotIndex partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex 1, high);}
}现在我想解释一下上面的代码:
partition函数用于找到基准元素的正确位置。它接受一个数组、下标和大标作为参数。它返回基准值元素被放置到正确位置后的索引。基准值被选为数组的最后一个元素。然后该函数遍历数组将小于或等于基准值的元素替换到数组的左侧。最后将基准值放在正确的位置并返回基准值的下标。
No Recursive version of the code
template typename T
int partitionNew(vectorT arr, int low, int high)
{T pivot arr[low];int i low 1;int j high;while (i j){while (i j arr[i] pivot){i;}while (i j arr[j] pivot){j--;}if (i j){swap(arr[i], arr[j]);}}swap(arr[low], arr[j]);return j;
}template typename T
void quickSortNew(vectorT arr)
{stackpairint, int stk;stk.push(make_pair(0, arr.size() - 1));while (!stk.empty()){int low stk.top().first;int high stk.top().second;stk.pop();if (low high){continue;}int pivot partitionNew(arr, low, high);stk.push(make_pair(pivot 1, high));stk.push(make_pair(low, pivot - 1));}
}这段代码使用栈来管理递归实现了快速排序算法。partitionNew函数是快速排序算法中使用的划分函数的修改版本。它接受一个元素向量和两个下标low和high作为输入并返回对向量进行分区后主元素的下标。
quickSortNew函数是使用快速排序算法对输入向量进行排序的主要函数。它接受一个指向元素向量的引用作为输入并对向量进行原地排序。该函数使用栈来管理递归并调用partitionNew函数对向量进行分区并获得基准值索引。然后它将接下来要排序的子向量的下标压入栈中直到栈为空。
完整的代码
#include iostream
#include vector
#include algorithm
#include ctime
#include cstdlib
#include stack
#include cassert#pragma warning(push)
#pragma warning(disable : 4267)using namespace std;template typename T
int partition(vectorT arr, int low, int high)
{T pivot arr[high];int i low - 1;for (int j low; j high - 1; j){if (arr[j] pivot){i;swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return i 1;
}template typename T
int partitionNew(vectorT arr, int low, int high)
{T pivot arr[low];int i low 1;int j high;while (i j){while (i j arr[i] pivot){i;}while (i j arr[j] pivot){j--;}if (i j){swap(arr[i], arr[j]);}}swap(arr[low], arr[j]);return j;
}// This is a recursive quicksort code.
template typename T
void quickSort(vectorT arr, int low, int high)
{if (low high){int pivotIndex partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex 1, high);}
}template typename T
void quickSortNew(vectorT arr)
{stackpairint, int stk;stk.push(make_pair(0, arr.size() - 1));while (!stk.empty()){int low stk.top().first;int high stk.top().second;stk.pop();if (low high){continue;}int pivot partitionNew(arr, low, high);stk.push(make_pair(pivot 1, high));stk.push(make_pair(low, pivot - 1));}
}class Person
{
public:Person(string name, int age, int score){this-name name;this-age age;this-socre score;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Override the operator! for other function to use.bool operator!(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre ! other.socre ||this-age ! other.age ||this-name ! other.name;}// Override the operator for other fnction to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Now there are some get parameters function for this calss:const string getName() const { return this-name; }int getAge() const { return this-age; }int getScore() const { return this-socre; }private:string name;int age;int socre;
};// This is a unit test function for Person class.
void testPerson()
{Person person1(Alice, 20, 90);Person person2(Bob, 21, 80);Person person3(Charlie, 22, 85);// Test operatorassert(person1 person2);assert(!(person1 person3));// Test operatorassert(person2 person1);assert(!(person3 person1));// Test operatorassert(person1 person1);assert(!(person1 person2));// Test operator!assert(person1 ! person2);assert(!(person1 ! person1));
}void basicTypesQuickSortCase()
{// The int type test case:vectorint intArr {10, 7, 8, 9, 1, 5};quickSortint(intArr, 0, intArr.size() - 1);cout Sorted int array: ;for (int i 0; i intArr.size(); i){cout intArr[i] ;}cout endl;// The float type test case:vectordouble floatArr {10.5, 7.2, 8.1, 9.6, 1.8, 5.3};quickSortdouble(floatArr, 0, floatArr.size() - 1);cout Sorted float array: ;for (int i 0; i floatArr.size(); i){cout floatArr[i] ;}cout endl;// The string type test case:vectorstring stringArr {apple, banana, cherry, orange, grape, kiwi};quickSortstring(stringArr, 0, stringArr.size() - 1);cout Sorted string array: ;for (int i 0; i stringArr.size(); i){cout stringArr[i] ;}cout endl;
}void basicTypesQuickSortNewCase()
{// The int type test case:vectorint intArr {10, 7, 8, 9, 1, 5};quickSortNewint(intArr);cout Sorted int array: ;for (size_t i 0; i intArr.size(); i){cout intArr[i] ;}cout endl;// The float type test case:vectordouble floatArr {10.5, 7.2, 8.1, 9.6, 1.8, 5.3};quickSortNewdouble(floatArr);cout Sorted float array: ;for (size_t i 0; i floatArr.size(); i){cout floatArr[i] ;}cout endl;// The string type test case:vectorstring stringArr {apple, banana, cherry, orange, grape, kiwi};quickSortNewstring(stringArr);cout Sorted string array: ;for (size_t i 0; i stringArr.size(); i){cout stringArr[i] ;}cout endl;
}void personQuickSortCase()
{// Now I want to write some Person classs quick sort examples in here:vectorPerson personArr {Person(John, 25, 88), Person(Alice, 30, 77), Person(Bob, 20, 66)};quickSortNewPerson(personArr);cout Sorted Person array: ;const auto personSize personArr.size();for (size_t i 0; i personSize; i){const auto person personArr[i];cout person.getName() person.getAge() person.getScore() endl;}cout endl;// Now I want to write some Person classs quick sort examples in here:vectorPerson personArrNew {Person(Tom, 35, 77), Person(Panda, 22, 88), Person(Alex, 50, 99)};const auto personSizeNew personArrNew.size();quickSortPerson(personArrNew, 0, personSizeNew - 1);cout Sorted Person array: endl;for (size_t i 0; i personSizeNew; i){const auto person personArrNew[i];cout person.getName() person.getAge() person.getScore() endl;}cout endl;
}int main()
{// Test Person classtestPerson();// Test basic types quick sortbasicTypesQuickSortCase();basicTypesQuickSortNewCase();personQuickSortCase();return 0;
}#pragma warning(pop)
class Person:def __init__(self, name, age, score):self.name nameself.age ageself.score scoredef __gt__(self, other):return self.score other.scoredef __lt__(self, other):return self.score other.scoredef __eq__(self, other):return self.score other.score and self.age other.age and self.name other.namedef __ne__(self, other):return self.score ! other.score or self.age ! other.age or self.name ! other.namedef __le__(self, other):return self.score other.score and self.age other.age and self.name other.namedef __ge__(self, other):return self.score other.score and self.age other.age and self.name other.namedef get_name(self):return self.namedef get_age(self):return self.agedef get_score(self):return self.scoredef partition(arr, low, high):pivot arr[high]i low - 1for j in range(low, high):if arr[j] pivot:i 1arr[i], arr[j] arr[j], arr[i]arr[i 1], arr[high] arr[high], arr[i 1]return i 1def quick_sort(arr, low, high):if low high:pivot_index partition(arr, low, high)quick_sort(arr, low, pivot_index - 1)quick_sort(arr, pivot_index 1, high)def test_person():person1 Person(Alice, 20, 90)person2 Person(Bob, 21, 80)person3 Person(Charlie, 22, 85)assert person1 person2assert not (person1 person3)assert person2 person1assert not (person3 person1)assert person1 person1assert not (person1 person2)assert person1 ! person2assert not (person1 ! person1)def basic_types_quick_sort_case():int_arr [10, 7, 8, 9, 1, 5]quick_sort(int_arr, 0, len(int_arr) - 1)print(Sorted int array:, int_arr)float_arr [10.5, 7.2, 8.1, 9.6, 1.8, 5.3]quick_sort(float_arr, 0, len(float_arr) - 1)print(Sorted float array:, float_arr)string_arr [apple, banana, cherry, orange, grape, kiwi]quick_sort(string_arr, 0, len(string_arr) - 1)print(Sorted string array:, string_arr)def person_quick_sort_case():person_arr [Person(John, 25, 88), Person(Alice, 30, 77), Person(Bob, 20, 66)]quick_sort(person_arr, 0, len(person_arr) - 1)print(Sorted Person array:)for person in person_arr:print(person.get_name(), person.get_age(), person.get_score())if __name__ __main__:# test_person()basic_types_quick_sort_case()person_quick_sort_case()
上面的代码是快速排序算法对基本数据类型和用户定义数据类型的完整实现。它包括针对每种数据类型的测试用例以及如何在自定义数据类型上使用快速排序算法的演示。
总结
在本文中我们梳理了快速排序算法它的时间复杂度以及如何用c实现它。我们还学习了如何在基本数据类型和用户定义数据类型上使用快速排序算法。
扩展阅读
随机快速排序算法(Randomized Quick Sort)
随机快速排序是使用随机基准值的快速排序算法的一种变体。其基本思想是随机从数组中选择一个基准值并根据其他元素是否小于基准值将其划分为两个子数组。然后对子数组进行递归排序。
使用随机基准值的主要好处是避免了对已经排序或倒序的输入数组的最差情况性能。通过随机选择基准值得到糟糕基准值(将数组划分为两个大小不等的子数组)的机会减少了从而提高了算法的平均性能。
随机快速排序通常用于未知输入数据是否已排序或逆序的情况良好的平均性能比最差情况下的性能更重要。它对于大型数据集的排序特别有用因为即使在最坏的情况下预期的性能也非常好。
下面是随机快速排序的一个简单实现:
import randomdef randomized_partition(arr, low, high):pivot_index random.randint(low, high)arr[pivot_index], arr[high] arr[high], arr[pivot_index]return partition(arr, low, high)def randomized_quick_sort(arr, low, high):if low high:pivot_index randomized_partition(arr, low, high)randomized_quick_sort(arr, low, pivot_index - 1)randomized_quick_sort(arr, pivot_index 1, high)下面是随机快速排序算法的c代码:
#include iostream
#include vector
#include randomstd::random_device rd;
std::mt19937 gen(rd());int randomized_partition(std::vectorint arr, int low, int high) {int pivot_index std::uniform_int_distribution(low, high)(gen);std::swap(arr[pivot_index], arr[high]);return partition(arr, low, high);
}void randomized_quick_sort(std::vectorint arr, int low, int high) {if (low high) {int pivot_index randomized_partition(arr, low, high);randomized_quick_sort(arr, low, pivot_index - 1);randomized_quick_sort(arr, pivot_index 1, high);}
}int main() {std::vectorint arr {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};randomized_quick_sort(arr, 0, arr.size() - 1);for (int num : arr) {std::cout num ;}return 0;
}这段代码使用了c 11的随机数生成功能来随机选择一个主元素。randomized_partition函数是快速排序算法中使用的分区函数的修改版本。它接受一个元素向量的引用和两个索引low和high作为输入并返回对向量进行分区后主元素的索引。
randomized_quick_sort函数是使用随机快速排序算法对输入向量进行排序的主要函数。它接受一个元素向量的引用和两个索引low和high作为输入并对向量进行原地排序。该函数使用randomized_partition函数对向量进行分区并获得基准值索引。然后递归调用自己对子向量进行排序直到栈为空。
三中位数快排(Median of Three Quick Sort)
三中位数快排算法(Median of Three fast Sort algorithm)是快速排序算法的一种变体它随机选择三个元素中的中间元素作为基准值。这种方法旨在提高快速排序算法在处理有很多重复元素的数组或已经排序过的数组时的性能。
三中位数快排算法的中位数工作原理如下:
从数组中随机选择三个元素。对这三个元素进行排序找到中位数。在快速排序算法中使用中位数元素作为基准值。
这种方法背后的主要思想是使用中位数元素作为基准值可以减少遇到最坏情况的可能性即分区过程导致子数组不平衡。这反过来又提高了快速排序算法的整体性能。
下面是三次快速排序中位数算法的简单Python实现:
import randomdef median_of_three_quick_sort(arr):if len(arr) 1:return arr# Choose three random elementsidx1, idx2, idx3 random.sample(range(len(arr)), 3)elem1, elem2, elem3 arr[idx1], arr[idx2], arr[idx3]# Sort the three elementsif elem1 elem2:elem1, elem2 elem2, elem1if elem2 elem3:elem2, elem3 elem3, elem2if elem1 elem2:elem1, elem2 elem2, elem1# Use the median element as the pivotpivot elem2less [x for x in arr if x pivot]greater [x for x in arr if x pivot]# Recursively sort the less and greater arraysreturn median_of_three_quick_sort(less) [pivot] median_of_three_quick_sort(greater)请注意三中位数快排算法的中位数比标准快速排序算法的性能提升取决于特定的用例和输入数据的性质。在某些情况下标准的快速排序算法仍然可能优于三种快速排序算法中的中位数。
下面是快速排序算法的中位数的c实现:
#include iostream
#include vector
#include algorithm
#include cstdlibusing namespace std;// Swap two elements in the vector
void swap(vectorint arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}// Median of Three function to find the median of three elements
int median_of_three(vectorint arr, int low, int high) {int mid low (high - low) / 2;if (arr[mid] arr[low]) {swap(arr, low, mid);}if (arr[high] arr[low]) {swap(arr, low, high);}if (arr[high] arr[mid]) {swap(arr, mid, high);}swap(arr, mid, high - 1);return arr[high - 1];
}// Quick Sort function
void quick_sort(vectorint arr, int low, int high) {if (low high) {return;}int pivot median_of_three(arr, low, high);int i low;int j high - 1;while (i j) {while (arr[i] pivot) {i;}while (arr[j] pivot) {j--;}if (i j) {swap(arr, i, j);i;j--;}}quick_sort(arr, low, i - 1);quick_sort(arr, j 1, high);
}int main() {vectorint arr {3, 6, 8, 10, 1, 2, 1};quick_sort(arr, 0, arr.size() - 1);for (int i 0; i arr.size(); i) {cout arr[i] ;}return 0;
}这段代码定义了一个median_of_three函数用于查找数组中三个元素的中位数并将其用作基准值。然后quick_sort函数被修改为使用这种三选中值基准值选择。main函数演示了一个示例数组的排序。
个人格言 追寻与内心共鸣的生活未来会逐渐揭晓答案。
Pursue the life that resonates with your heart, and the future will gradually reveal the answer.
