排序_快速排序-Aet

Bingliaolong 2020-05-08 10:55 Aet | 隐藏边栏 | 抢沙发 | 24 0

文章评分 5 次，平均分 5.0 ：

简述

快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。

快速排序是从冒泡排序演变而来的。

快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

为什么快速排序比较快？
因为它使用了分治法
【分治法：】将一个规模为N的问题，分成K个规模较小的子问题。这些子问题相互独立且与原问题性质相同。求出子问题的解，合并得到原问题的解。

复杂度


名称	最好	平均	最差	空间	稳定性
快速排序	nlog(n)	nlog(n)	n²	log(n)	否

双边循环理解

递归实现，寻找一个基准，将整个集合按基准分成两半去处理
1. 快速排序是一种典型的分治算法
2. 基本思想是将一个大的问题分解成若干个小问题分别解决，然后将它们的结果合并起来
3. 可以理解为：通过递归的方式去达到分治的目的
在每一次递归调用中，会确定好一个基准，这个基准其实也代表着有一个元素被放置到正确的位置了

单边循环理解

同样是递归实现，同样需要找一个基准，将整个集合按基准分成两半去处理
一开始用arr[start]这个元素作为pivot，并且用start的下标值作为mark的初始值
1. 于是，需要处理的元素，就需要从start+1开始
大循环中，从start+1的位置开始和所有元素挨个比较，任务就是找出比一开始记录的pivot（也就是arr[start]）小的所有元素
1. 在循环中每找到一个比pivot小的元素，就把mark向右移动一次，用移动后的位置和找到和元素的位置，进行值交换
2. 这样，当循环结束，所有比pivot小的元素都挨个被存放在start的后面了
3. 直到找不到比pivot更小的元素时，结束循环
循环结束后，序列中所有比pivot小的元素都位于start的右边，此时start存放的是pivot，而mark记录的是最后一个找到的比pivot小的元素
1. 于是，将mark位置的元素和pivot进行值交换，mark位置左边的所有元素都是比它小的
这样，mark这个下标就是我们找到的基准，可以以mark为界限，把所有元素分成两半

实现

递归实现

双边循环法

选定一个基准元素，并指定两个指针left right，分别指向数列最左和最右的两个元素。

void QuickSort(int array[],int startIndex,int endIndex)

{

//递归结束条件

if(startIndex >= endIndex)

return;

//得到基准元素

int pivotIndex = partition(array,startIndex,endIndex);

//根据基准元素，分成两部分进行递归排序

QuickSort(array,startIndex,pivotIndex - 1);

QuickSort(array,pivotIndex + 1,endIndex);

}

int partition(int array[],int startIndex,int endIndex)

{

//取第一个位置的元素为基准元素【更好的方法是取随机位置的元素为基准元素】

int pivot = array[startIndex];

int left = startIndex;

int right = endIndex;

while(left != right)

{

//控制right指针比较并左移

while(left < right && array[right] > pivot)

{

right--;

}

//控制left指针比较并右移

while(left < right && array[left] <= pivot)

{

left++;

}

//交换left指针和right指针所指向的元素

if(left < right)

{

int temp = array[left];

array[left] = array[right];

array[right] = temp;

}

//基准元素和指针重合点交换

array[startIndex] = array[left];

array[left] = pivot;

return left;

}

单边循环法

选定一个基准元素，并使用一个指针mark作为区域边界，只从数组的一边对元素进行遍历和交换。

void QuickSort(int array[],int startIndex,int endIndex)

{

//递归结束条件

if(startIndex >= endIndex)

return;

//得到基准元素

int pivotIndex = partition(array,startIndex,endIndex);

//根据基准元素,分成两部分进行递归排序

QuickSort(array,startIndex,pivotIndex - 1);

QuickSort(array,pivotIndex + 1,endIndex);

}

int partition(int array[],int startIndex,int endIndex)

{

//取第一个位置的元素为基准元素【更好的方法是取随机位置的元素为基准元素】

int pivot = array[startIndex];

int mark = startIndex;

for(int i = startIndex + 1;i < endIndex; ++i)

{

if(array[i] < pivot)

{

mark++;

int temp = array[mark];

array[mark] = array[i];

array[i] = temp;

}

array[startIndex] = array[mark];

array[mark] = pivot;

return mark;

}

非递归实现

通过栈的方式进行非递归实现快速排序。

#inluce <stack>

#include <unordered_map>

using namespace std;

void QuickSort(int array[], int startIndex, int endIndex)//非递归实现

{

//用一个集合栈来代替递归的函数栈

stack<unordered_map<string, int>> quickSortStack;

//整个数列的起止下标，以哈希的方式入栈

unordered_map<string, int> rootPram;

rootPram.insert(make_pair("startIndex", startIndex));

rootPram.insert(make_pair("endIndex", endIndex));

quickSortStack.push(rootPram);

//循环结束条件：栈为空时

while (!quickSortStack.empty())

{

//栈顶元素出栈，得到起止下标

unordered_map<string, int> param = quickSortStack.top();

quickSortStack.pop();

//得到基准元素

int pivotIndex = partition2(array, param.at("startIndex"), param.at("endIndex"));

//根据基准元素分成两部分，把每一部分得起止下标入栈

if (param.at("startIndex") < pivotIndex - 1)

{

unordered_map<string, int> leftParam;

leftParam.insert(make_pair("startIndex", param.at("startIndex")));

leftParam.insert(make_pair("endIndex", pivotIndex - 1));

quickSortStack.push(leftParam);

}

if (pivotIndex + 1 < param.at("endIndex"))

{

unordered_map<string, int> rightParam;

rightParam.insert(make_pair("startIndex", pivotIndex + 1));

rightParam.insert(make_pair("endIndex", param.at("endIndex")));

quickSortStack.push(rightParam);

}

int partition(int array[],int startIndex,int endIndex)

{

//取第一个位置的元素为基准元素【更好的方法是取随机位置的元素为基准元素】

int pivot = array[startIndex];

int mark = startIndex;

for(int i = startIndex+1; i < endIndex; ++i)

{

if(array[i] < pivot)

{

mark++;

int temp = array[mark];

array[mark] = array[i];

array[i] = temp;

}

array[startIndex] = array[mark];

array[mark] = pivot;

return mark;

}

算法导论

单边循环

划分思想，假设对数组A[p...r]划分，划分主元为A[q]：

交换：首先将A[q]与A[r]交换，使得新的A[r]成为划分元素

循环：维持循环不变式： A[p...smaller_next-1]始终小于A[r]，A[smaller_next...current-1]始终大于A[r]。开始对A[current]进行判别

若A[current]<A[r] 则交换 A[current]与 A[smaller_next], current右移（进行下一个元素的判断），smaller_next右移（维持不变式）

若A[current]>=A[r], current右移（进行下一个元素的判断）

时间复杂度 O(n)

原地操作

begin : 待划分序列的起始迭代器（也可以是指向数组中某元素的指针）

end: 待划分序列的终止迭代器（也可以是指向数组中某元素的指针）

partition_iter: 指定划分元素的对应的迭代器（也可以是指向数组中某元素的指针）

compare: 一个可调用对象，可用于比较两个对象的小于比较，默认为std::less

划分之后该划分元素值在序列中对应的新迭代器（也可以是指向数组中某元素的指针）

template<typename Iterator,typename CompareType=std::less<typename std::iterator_traits<Iterator>::value_type>>

Iterator partition(const Iterator begin,const Iterator end,const Iterator partition_iter,CompareType compare=CompareType())

{

//typedef typename std::iterator_traits<Iterator>::value_type T;// 迭代器指向对象的值类型

auto size=std::distance(begin,end);

assert(size>=0);

if(size==0) return end; //空序列，返回end

// if(size<=1)

// return begin;

assert(std::distance(begin,partition_iter)>=0 &&std::distance(partition_iter,end)>0);

auto smaller_next=begin; //指向比key小的元素区间的下一个(即大于等于key元素区间的第一个），其中key为序列最后一个元素

auto current=begin; //指向当前待处理的元素

std::swap(*partition_iter,*(end-1));//交换partition元素到末尾

while(current!=end-1)

{

if(compare(*current,*(end-1)))

{

std::swap(*smaller_next,*current);

smaller_next++;

}

current++;

}

std::swap(*smaller_next,*(end-1));//交换partition元素到它的位置

return smaller_next;

}

begin : 待排序序列的起始迭代器（也可以是指向数组中某元素的指针）

begin : 待排序序列的起始迭代器（也可以是指向数组中某元素的指针）

compare: 一个可调用对象，可用于比较两个对象的小于比较，默认为std::less

最坏时间复杂度 O(n^2)，期望时间复杂度 O(nlgn)。它平均性能非常好，是实际排序应用中最好的选择

原地排序

template<typename Iterator,typename CompareType=std::less<typename std::iterator_traits<Iterator>::value_type>>

void quick_sort(const Iterator begin,const Iterator end,CompareType compare=CompareType())

{

//typedef typename std::iterator_traits<Iterator>::value_type T;// 迭代器指向对象的值类型

auto size=std::distance(begin,end);

if(size<=1)

return;

auto partitioned_iter=partition(begin,end,end-1,compare); // 以最后一个元素作为划分元素，返回其顺序统计量

quick_sort(begin,partitioned_iter,compare);

quick_sort(partitioned_iter+1,end,compare);

}

双边循环

template<typename Iterator, typename CompareType = std::less<typename std::iterator_traits<Iterator>::value_type>>

void quick_sort(const Iterator begin, const Iterator end, CompareType compare = CompareType()) {

auto size = std::distance(begin, end);

if (size <= 1)

return;

auto partitioned_iter = partition(begin, end, begin, compare);

quick_sort(begin, partitioned_iter, compare);

quick_sort(partitioned_iter + 1, end, compare);

}

template<typename Iterator, typename CompareType = std::less<typename std::iterator_traits<Iterator>::value_type>>

Iterator partition(const Iterator begin, const Iterator end, const Iterator partition_iter, CompareType compare = CompareType()) {

auto pivot = *partition_iter; // 选择第一个元素作为 pivot

auto left = begin + 1; // 从第二个元素开始

auto right = end - 1; // 从最后一个元素开始

while (true) {

// 向右移动 left，找到第一个不小于 pivot 的元素

while (left <= right && compare(*left, pivot)) {

left++;

}

// 向左移动 right，找到第一个不大于 pivot 的元素

while (left <= right && compare(pivot, *right)) {

right--;

}

// 如果 left 和 right 没有交错，则交换它们指向的元素

if (left < right) {

std::swap(*left, *right);

left++;

right--;

} else {

break;

}

// 最后将 pivot 放到其正确的位置

std::swap(*partition_iter, *(right));

// 返回 pivot 的位置

return right;

}

简述
复杂度
双边循环理解
单边循环理解
实现
递归实现
非递归实现
算法导论
单边循环
双边循环

本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！

Bingliaolong 关注：0 粉丝：0 最后编辑于：2024-08-13

Everything will be better.

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

简述

复杂度

双边循环理解

单边循环理解

实现

递归实现

双边循环法

单边循环法

非递归实现

算法导论

单边循环

双边循环

你可能也喜欢

热评文章

发表评论

标签云集