I.何为Two pointer

用两个哨兵指向两个序列，通过利用序列本身的性质减少遍历次数，来更快得解决一些归并问题

基本问题

给定一个正整数递增序列和一个正整数M，求序列中两个不同位置的a,b使得a+b==M，打印a,b。
合并两个递增正整数序列。

解决方案

若直接二重循环遍历，显然存在一些不必要的遍历步骤。

题目一

递增数组a。对于某个a[i]来说，当找到一个a[j]使得a[i]+a[j]==M时，a[i]+b[j+1]>M显然的，根本无需再往下枚举；同理a[i+1]+b[j]>M也是显然的，无需枚举。只有在a[i+1]+b[j-1]的情况下才有可能再次出现和为M的情况。

所以可用i,j两个哨兵分别指向a,b的首尾，当a[i]+b[j]<M时，i++使得a[i]+a[j]增大；当a[i]+a[j]>M时，j--使得a[i]+a[j]减小;当a[i]+a[j]==M时，i++,j--，在[i+1,j-1]区间内再次判断大小关系。

#include<stdio.h>

int main()

{

    int a[5] = {1,2,3,4,5};

    int i=0,j=4;

    while(i<=j)

    {

        if(a[i]+a[j]==6)

        {

            printf("%d %d\n", a[i],a[j]);

            i++;j--;

        }

        else if(a[i] + a[j] > 6)

            j--;

        else i++;

    }

    return 0;

}

由于i只加不减，j只减不加，最终会达到i==j，此时a已枚举完毕。

题目二

当a[i]>b[j-1]&&a[i]<=b[j]时,a[i]插在b[j]之前，而此时a[i+1]必然插在b[j-1]之后，二重循环中a[i+1]和b[0]-b[j-1]之间的比较是不必要的。

所以可创建一个空数组c存储合并后的序列，用i,j，index,分别指向a,b,c的首元素。

当a[i]<b[j]时，将a[i]插入c中，i后移，index后移，即‘c[index++] = a[i++]’

否则，将b[i]插入c中，j后移，index后移，即‘c[index++] = b[j++]’

最后，a或b中若有剩余元素，则全部添加到c中。

#include<stdio.h>

void merge(int a[], int b[], int m, int n)

{

    int i = 0, j = 0, index = 0;

    int c[100] = {0};

    while(i < m && j < n)

    {

        if(a[i] <= b[j])

             c[index++] = a[i++];

        else c[index++] = b[j++];

    }

    while(i < m) c[index++] = a[i++];

    while(j < n) c[index++] = b[j++];

    i = 0;

    while(c[i] != 0) printf("%d ", c[i++]);

}

int main()

{

    int a[5] = {1,2,3,4,5}, b[5] = {3,4,6,7,8};

    int i=0,j=4;

    merge(a,b,5,5);

    return 0;

}

II.归并排序

基本思想：有序子序列归并后构成的序列仍有序

时间复杂度

O(nlogn)

递归实现

算法分析（升序为例）

将序列A升序排序即构造递增序列

1.递归表达式：要保证A递增，只需保证A的子序列B,C递增，再将其合并

2.结束条件：当B,C只有一个元素时，可视为递增

3.回溯操作：合并递增的子序列

代码实现

#include<stdio.h>

const int maxn = 100;

/*将数组A[]的[L1,R1],[L2,R2]合并为有序序列*/

/*此时L2 = R1+1*/

void merge(int A[], int L1, int R1, int L2, int R2)

{

    int i = L1, j = L2, index = 0;

    int tmp[maxn];

    while(i <= R1 && j <= R2)

    {

        if(A[i] <= A[j])

             tmp[index++] = A[i++];

        else tmp[index++] = A[j++];

    }

    while(i <= R1) tmp[index++] = A[i++];

    while(j <= R2) tmp[index++] = A[j++];

    for(i = 0; i < index; i++)

        A[L1+i] = tmp[i];

}

void mergeSort(int a[], int left, int right)

{

    if(left<right)

    {

    int mid = (left+right)/2;

    mergeSort(a,left,mid);

    mergeSort(a,mid+1,right);

    merge(a,left,mid,mid+1,right);

    }

}

int main()

{

    int a[10] = {1,23,54,65,22,3,23,61,15,34};

    int i;

    mergeSort(a,0,9);

    for(i=0; i < 10; i++)

        printf("%d ",a[i]);

    return 0;

}

迭代实现

《算法笔记》P141

III.快速排序

基本思想：直接确定每个元素在排序后的序列中的位置

算法分析

1.将区间最左侧元素a[left]置位。即保证：a[index]左侧元素都<=a[index],a[index]右侧所有元素值都>a[index]。

2.以a[index]为界限划分序列a，重复上述操作。

将区间最左侧元素a[left]置位：Partition()

调整最左侧元素a[left]到相应位置，使得序列中<=a[left]的元素都在a左侧，>a的元素都在右侧

基本方法：two pointer

关注空穴。

在区间[left, right]中：

将tmp = a[left]，此时a[left]为空穴。
比较a[right],若a[right]>tmp，说明a[right]的相对位置正确，不必变动
反复左移right(right--)，直到找到a[right]<=tmp，此时该元素a[right]的相对位置不正确，它应该在tmp左边
令a[left] = a[right]来填补a[left]空穴，此时a[right]移动到了正确的相对位置上，且此时a[right]成为空穴
比较a[left],若a[left]<=tmp，说明a[left]的相对位置正确，不必变动
反复右移left(left++)，直到找到a[left]>tmp，此时该元素a[left]的相对位置不正确，它应该在tmp右边
令a[right] = a[left]来填补a[right]空穴，此时a[left]移动到了正确的相对位置上，且此时a[left]再次成为空穴
重复2-7操作，直到left == right,此时a[left]（或成为a[right]）左边的元素都<=tmp，右边的元素都>tmp,即a[left]就是tmp在最终序列中的位置。令 a[left] = tmp。

注：2-4与5-7相对应且不能交换顺序。

代码实现

#include<stdio.h>

int Portition(int a[], int left, int right)

{

    int tmp = a[left];

    while(left < right)

    {

        while(left < right && a[right] > tmp) right--; /*反复左移right*/

        a[left] = a[right];

        while(left < right && a[left ] <= tmp) left ++; /*反复右移left*/

        a[right] = a[left];

    }

    a[left] = tmp;  /*把tmp放置在letf\right相遇处*/

    return left;

}

快速排序的递归实现

代码

/*输入元素下标*/

void quickSort(int a[], int left, int right)

{

     /*区间长度大于1*/

    if(left < right)

    {

        /*将[Left, Right]按a[Left]一分为二*/

        int pos = Portition(a, left, right);

        quickSort(a, left, pos - 1);

        quickSort(a, pos + 1, right);

    }

}

现存问题与改进方案

问题：当序列基本有序时等价于选择排序，时间复杂度：O(n^2).
原因：A[left]为将序列较为均匀地划分
改进：随机选取A[left]

randomPortition()

在Portition()开头加两行

int P = (int)(1.0 * rand()/RAND_MAX(right-left)+left);

swap(a[left], a[P]);

总结：随机快排

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

int randomPortition(int a[], int left, int right)

{

    int P = (int)(1.0 * rand()/RAND_MAX*(right-left)+left);

    swap(a[left], a[P]);

    int tmp = a[left];

    while(left < right)

    {

        while(left < right && a[right] > tmp) right--;

        /*反复左移right*/

        a[left] = a[right];

        while(left < right && a[left ] <= tmp) left ++;

        /*反复右移left*/

        a[right] = a[left];

    }

    a[left] = tmp;  /*把tmp放置在letf\right相遇处*/

    return left;

}

void quickSort(int a[], int left, int right)

{

     /*区间长度大于1*/

    if(left < right)

    {

        /*将[Left, Right]按a[Left]一分为二*/

        int pos = randomPortition(a, left, right);

        quickSort(a, left, pos - 1);

        quickSort(a, pos + 1, right);

    }

}

测试程序

int main()

{

    int a[10] = {15,23,15,65,22,3,23,61,1,34};

    int i;

    printf("%d\n", randomPortition(a,0,9));

    for(i = 0; i < 10; i++)

        printf("%d ",a[i]);

    printf("\n");

    quickSort(a, 0, 9);

    for(i = 0; i < 10; i++)

        printf("%d ",a[i]);

    return 0;

}

巴特西

Two pointer方法

I.何为Two pointer

基本问题

解决方案

题目一

题目二

II.归并排序

时间复杂度

递归实现

算法分析（升序为例）

代码实现

迭代实现

III.快速排序

算法分析

将区间最左侧元素a[left]置位：Partition()

基本方法：two pointer

代码实现

快速排序的递归实现

代码

现存问题与改进方案

randomPortition()

总结：随机快排

测试程序

最新文章

热门文章