I.何为Two pointer

基本问题

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

解决方案

1. 遍历：O(n^2)
2. two pointer: O(n)【充分利用了序列的递增特性】

代码实现

#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;
}

#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)

递归实现

#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.快速排序

Partition()

1. 调整最左侧元素a到相应位置，是序列中<=a的元素都在a左侧，

a的元素都在右侧

2. 代码实现

#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);
    }
}

现存问题与改进方案

1. 问题：当序列基本有序时等价于选择排序，时间复杂度：O(n^2).
2. 原因：A[left]为将序列较为均匀地划分
3. 改进：随机选取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;
}