排序算法:插入排序和快速排序

分治思想

在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
分治法-维基百科,自由的百科全书

简单的来说,分治法将原问题划分成若干个规模较小而结构与原问题一致的子问题,递归的解决这些自问题,然后再合并其结果,由此来得到原问题的解。

分治模式在每一层递归上都有三个步骤
-分解:将原问题分解为一系列的子问题
-解决:递归的解各子问题,若子问题足够小,则直接有解
-合并:将子问题的结果合并成原问题的解

分治的关键点

-原问题可以一直分解为形式相同的子问题,当子问题规模较小时,可自然求解。
-子问题的解通过合并可以得到原问题的解。
-子问题的分解及合并较为简单,否则分解和合并所花的时间可能超过暴力解法,得不偿失。

分治的两个目的:

1.解决问题
2.提高性能

插入排序算法

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到 O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
插入排序-维基百科,自由的百科全书


图片由Swfung8 - <span class="int-own-work" lang="zh-cn">自己的作品</span>,CC BY-SA 3.0链接

由于插入排序较为简单,所以我们这里只简单的介绍一下。

插入排序的算法实现

从第一个元素开始,该元素可以认为已经被排序
取出下一个元素,在已经排序的元素序列中从后向前扫描
如果该元素(已排序)大于新元素,将该元素移到下一位置
重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找插入排序。
插入排序-维基百科,自由的百科全书

插入排序的代码实现:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void f(vector<int>& nums, int p)
{
    if (p == 0) return;
     f(nums, p - 1);
    int index = p - 1;
    int x = nums[p];
    while (x>nums[index])    
    {
        nums[index+ 1] = nums[index];
        index--;
    }
    nums[index+1]=x;
    
}
int main()
{
    int in[] = { 45,12,13,445,233 };
    vector<int>nums(in, in + 5);
    nums.push_back(0);
    f(nums,5);
    for (int i = 0; i < nums.size(); i++)
    {
        cout << nums[i] << " ";
    }
    return 0;
}

快速排序算法

前面我们讲了分治思想,现在我们讲一讲分治思想的应用,以快速排序为例。

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序 n个项目要 O(nlog n)次比较。在最坏状况下则需要 O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。


图片由en RolandH,CC BY-SA 3.0

快排的划分算法

快排的划分算法之一边单向扫描法

用两个指针讲数组划分为三个区间,从左到右,扫描指针往右走,讲主元和指针指向的元素进行比较,如果小于主元,则扫描指针右移,如果大于主元,则和未知区间末指针指向的元素进行交换,然后未知区间末指针前移,然后比较交换过来的元素,如果还是大于,则执行相同步骤。
最后将主元移动到扫描指针后。

主元的概念

用来划分数组的元素,主元的选择会影响到快排的时间复杂度,在本文中,我们选择数组第一个元素作为主元

扫描指针(scan_pos)

左边是确认小于等于主元的

未知区间末指针

扫描指针和位置区间末指针的中间是未知,未知区间末指针的右边区间为确认大于主元的元素

边界的思考

如果最后一个扫描元素大于主元,未知区间末指针左移,扫描指针大于未知区间末指针
如果最后一个扫描的元素小于主元,扫描指针右移,扫描指针大于未知区间末指针
所以,主元应插入扫描指针前(通过将主元和末指针指向的元素交换实现)。

一遍单向扫描法的代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct print
{
    void operator()(int n)//定义用于打印的一元谓词
    {
        cout << n << " ";
    }
};

int hf(vector<int>& nums,int start, int end)//快排的划分算法:一遍单向扫描法
{
    int P = nums[start];//定义主元
    int sp = start + 1;//定义扫描指针
    int ep = end;//定义未知区间末指针
    while (sp<= ep)//当扫描指针小于等于末指针的时候就执行
    {
        if (nums[sp] <= P)sp++;//如果扫描指针指向的元素小于主元,则扫描指针前移
        else//如果扫描指针指向的元素大于主元,则交换扫描指针和末指针指向的值,扫描指针前移。
        {
            int temp = nums[sp];//交换
            nums[sp] = nums[ep];
            nums[ep] = temp;

            ep--;//前移
        }
    }
    nums[start] = nums[ep];//将主元插入到扫描指针前(通过交换末指针和主元的值实现),因为扫描指针之和的数皆大于主元
    nums[ep] = P;
    return ep;//返回主元所在的下标
    

}
void quicksort(vector<int>& nums, int start, int end)
{
    if (start <end)//递归出口
    {
        int P = hf(nums, start, end);//划分
        quicksort(nums, start, P - 1);//对主元左边的数进行排序
        quicksort(nums, P +1, end);//对主元右边的数进行排序
    }
}
int main()
{
    vector<int>in{ 1,34,34,34,534,6,567,567,68,7,5,35,24,23 };//创建数组,注意这种初始化方式仅在C++11之后实现
    quicksort(in, 0, in.size() - 1);
    for_each(in.begin(), in.end(), print());//使用算法库函数调用一元谓词打印一元数组内容
    return 0;
}

运行结果

快速排序的划分算法之双向扫描法

头尾指针往中间扫描,从左找大于主元的元素,从右找小于等于主元的元素,然后二者交换,继续扫描,直到左侧无大元素,右侧无小元素。

边界的思考

无论如何,左右指针最后都会交错,且右指针在左,左指针在右,主元应放在左指针前,即和一边单向扫描法相同。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct print
{
    void operator()(int n)//定义用于打印的一元谓词
    {
        cout << n << " ";
    }
};
void swap(vector<int>& nums, int p1, int p2)
{
    int temp = nums[p1];
    nums[p1] = nums[p2];
    nums[p2] = temp;
}

int hf1(vector<int>& nums,int start, int end)//快排的划分算法:一遍单向扫描法
{
    int P = nums[start];//定义主元
    int sp = start + 1;//定义扫描指针
    int ep = end;//定义未知区间末指针
    while (sp<= ep)//当扫描指针小于等于末指针的时候就执行
    {
        if (nums[sp] <= P)sp++;//如果扫描指针指向的元素小于主元,则扫描指针前移
        else//如果扫描指针指向的元素大于主元,则交换扫描指针和末指针指向的值,扫描指针前移。
        {
            swap(nums, sp, ep);

            ep--;//前移
        }
    }
    swap(nums, ep, start);//将主元插入到扫描指针前(通过交换末指针和主元的值实现),因为扫描指针之和的数皆大于主元
    return ep;//返回主元所在的下标
    

}
int hf2(vector<int>& nums, int start, int end)//快排的划分算法:双向扫描法
{
    int P = nums[start];//定义主元
    int zp = start + 1;//定义左指针
    int yp = end;//定义右指针
    while (zp<=yp)
    {
        while (zp <= yp&&nums[zp] <= P)zp++;//zp <= yp这个条件一定要在左边,不然从c++从左往右顺序判定条件会造成数组越界
        while (zp <= yp&&nums[yp] > P)yp--;
        if(zp<yp)swap(nums,zp, yp);
    }
    swap(nums,yp, start);//将主元插入到左指针前(通过交换右指针和主元的值实现),因为右指针之后的数皆小于,等于主元
    return yp;
    
}
void quicksort(vector<int>& nums, int start, int end)
{
    if (start <end)//递归出口
    {
        int P = hf2(nums, start, end);//划分
        quicksort(nums, start, P - 1);//对主元左边的数进行排序
        quicksort(nums, P +1, end);//对主元右边的数进行排序
    }
}
int main()
{
    vector<int>in{ 1,34,34,34,534,6,567,567,68,7,5,35,24,23 };//创建数组,注意这种初始化方式仅在C++11之后实现
    quicksort(in, 0, in.size() - 1);
    for_each(in.begin(), in.end(), print());//使用算法库函数调用一元谓词打印一元数组内容
    return 0;
}

快排在工程实践中的优化

为什么要优化?

因为如果主元选取不恰当,那么快排的时间复杂度会从O(nlogn)退化为O(n^2),比如:

12345665776
主元搜索指针未知区间尾指针

由于数组中没有比主元还小的元素,所以搜索指针会和其他每一个元素交换。。。。
所以,我们期望选择的主元,应该是尽量居中的。
递归式:2T(n/2)+O(n);

三点中值法

从左中右选三个点,选择中间值作为主元

int  P;
if(nums[sp]>nums[mid]&&nums[sp]<nums[ep])P=sp;
if(nums[ep]>nums[mid]&&nums[ep]<nums[sp])P=ep;
else P=mid;

虽然三点中值法较为简单,且易于理解,但是其实其时间复杂度的大小是个运气问题,在某些情况下(例如三个点全部为最糟糕情况的下),并不能确保快排的时间复杂度为O(nlogn)。

绝对中值法

绝对中值法的思路是将原数组每五个分组,然后取最中间的元素,末尾不满五个也取最中间的,形成一个新数组,然后对这个数组进行插入排序,取最中间的元素作为主元。
虽然绝对中值法能够确保快排的时间复杂度为O(nlogn)但由于代码较为复杂,且不可能使用三点中值法的时候每次都是最坏情况,所以我们一般常用三点中值法。

在待排序列表较短时,使用插入排序

插入排序的时间复杂度为:O(n^2)
快速排序的时间复杂度为:O(nlogn)
乍一看,快排是要快于插入排序的,但是,我在之前我写的评估算法的那篇文章中关于函数的渐近增长的概念中提到存在一个点,使得该点之后的所有F(n)大于另一函数,那么关键就是这个点,这告诉了我们时间复杂度低的算法并非在任何情况下都优于时间复杂度高的算法。
而快排和插排也是如此
插入排序:T(n)=n(n-1)/2
快速排序:T(n)=n(lgn+1)
然后解不等式:n(n-1)/2< n(lgn+1)
估算大概为8
那么也就是说,在数组元素个数小于等于8时,插排是快于快排的。

Last modification:May 29th, 2019 at 04:00 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment