八种常见顺序存储的算法

目录

1、线性枚举

1）问题描述

2）动图演示

3）示例说明

4）算法描述

5）源码详解

2、前缀和差分

1）问题描述

2）动图演示

3）样例分析

4）算法描述

5）源码详解

3、双指针

1）问题描述

2）动图演示

3）样例说明

4）算法描述

5）源码详解

4、二分枚举

1）问题描述?编辑

2）动图演示

3）样例说明

4）算法描述

5）源码详解

5、三分枚举

6、插入排序

1）问题描述

2）动图演示

3）样例说明

4）算法描述

5）源码详解

7、选择排序

1）问题描述

2）动图演示

3）样例说明

4）算法描述

5）源码详解

8、冒泡排序

1）问题描述

2）动图演示

3）样例说明

4）算法描述

5）源码详解

---

1、线性枚举

1）问题描述

2）动图演示

3）示例说明

??蓝色的数据代表的是数组数据，红色的数据代表当前枚举到的数据，这样就可以遍历所有的数据进行逻辑处理了。

4）算法描述

??遍历数组，进行条件判断，条件满足则执行逻辑。这里的条件就是?枚举到的数?是否小于?当前最小值，执行逻辑为 将?当前枚举到的数?赋值给?当前最小值；

5）源码详解

int findMin(int* nums, int numsSize){
    int i, min = 100000;
    for(i = 0; i < numsSize; ++i) {     // (1)
        if(nums[i] < min) {             // (2)
            min = nums[i];
        }
    }
    return min;                         // (3)
}

• (1) 遍历数组中所有的数；
• (2)?如果?当前枚举到的数?比记录的变量min小，则将它赋值给min；否则，不做任何处理；
• (3)?最后，min中存储的就是整个数组的最小值。

2、前缀和差分

1）问题描述

2）动图演示

3）样例分析

??如上图所示，只需要记录一个前缀和，然后就可以通过一次减法将区间的值计算出来。时间复杂度 O(1)。这种就是差分的思想。

原理：

sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l + 1] ...... a[r];

sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];

sum[r] - sum[l - 1] = a[l] + a[l + 1] + ......+ a[r];

4）算法描述

??第一个枚举，利用一个数组sum，存储前?i?个元素的和。
??第二个枚举，读入?m?组数据 l,r，对每组数据，通过?O(1)?获取答案，即sum[r] - sum[l - 1]?。

5）源码详解

int sum[maxn];
int* prefixSum(int* nums, int numsSize, int m, int *l, int *r){
    int i;
    int *ret;
    for(i = 0; i < numsSize; ++i) {
        sum[i] = nums[i];
        if(i) 
            sum[i] += sum[i-1];                 // (1) 
    }
    ret = (int *) malloc( m * sizeof(int) );    // (2) 
    for(i = 0; i < m; ++i) {
    	int leftsum = l[i] == 0 ? 0 : sum[l[i]-1]; // (3) 
    	int rightsum = sum[r[i]];
    	ret[i] = rightsum - leftsum;            // (4) 
    }
    return ret;
}

• (1) 计算前缀和；
• (2)?需要返回的数组；
• (3)?这里是为了防止数组下标越界；
• (4) 核心 O(1)?的差分计算；

3、双指针

1）问题描述

2）动图演示

3）样例说明

??维护两个指针?i?和?j，区间 [i,j]?内的子串，应该时刻保持其中所有字符不重复，一旦发现重复字符，就需要自增?i（即执行 i = i + 1）；否则，执行 j = j + 1，直到 j?不能再增加为止。
??过程中，记录合法情况下 j ? i + 1?的最大值。

4）算法描述

??如上文所述，这种利用问题特性，通过两个指针，不断调整区间，从而求出问题最优解的算法就叫 “尺取法”，由于利用的是两个指针，所以又叫 “双指针” 算法。
??这里 “尺” 的含义，主要还是因为这类问题，最终要求解的都是连续的序列（子串），就好比一把尺子一样，故而得名。

算法描述如下：
??1）初始化 i = 0, j = i ? 1，代表一开始 “尺子” 的长度为 0；
??2）增加 “尺子” 的长度，即 j = j + 1；
??3）判断当前这把 “尺子” [i,j]?是否满足题目给出的条件：
????3.a）如果不满足，则减小 “尺子” 长度，即 i = i + 1，回到 3）；
????3.b）如果满足，记录最优解，回到 2）；

• 上面这段文字描述的比较官方，其实这个算法的核心，只有一句话：

  满足条件时，j++；不满足条件时，i++；

• 如图所示，当区间?[i,j]?满足条件时，用蓝色表示，此时?j?自增；反之闪红，此时?i?自增。
  

5）源码详解

int getmaxlen(int n, char *str, int& l, int& r) {
    int ans = 0, i = 0, j = -1, len;   // 1)
    memset(h, 0, sizeof(h));           // 2)
    while (j++ < n - 1) {              // 3)
        ++h[ str[j] ];                 // 4)
        while (h[ str[j] ] > 1) {      // 5)
            --h[ str[i] ];
            ++i;
        }
        len = j - i + 1;              
        if(len > ans)                  // 6)
            ans = len, l = i, r = j;
    }
    return ans;
}

• 1）初始化?i = 0, j = -1，代表 s[i:j]?为一个空串，从空串开始枚举；
• 2）需要维护一个哈希表，哈希表记录的是当前枚举的区间 s[i:j]?中每个字符的个数；
• 3）只推进子串的右端点；
• 4）在哈希表中记录字符的个数；
• 5）当?h[ str[j] ] > 1满足时，代表出现了重复字符str[j]，这时候左端点?i?推进，直到没有重复字符为止；
• 6）记录当前最优解的长度?j - i + 1，更新；
• 这个算法执行完毕，我们就可以得到最长不重复子串的长度为 ans，并且?i?和?j?这两个指针分别只自增?n?次，两者自增相互独立，是一个相加而非相乘的关系，所以这个算法的时间复杂度为 O(n)?。

4、二分枚举

1）问题描述

2）动图演示

3）样例说明

??需要找值为?5?的这个元素。
??黄色箭头代表都是左区间端点 l，红色箭头代表右区间端点?r。蓝色的数据为数组数据，绿色的数字代表的是数组下标，初始化 l = 0，r = 7，由于数组有序，则可以直接折半，令 mid =(l+r)/2=3，则?55?一定落入区间 [0,3]，这时候令 r = 3，继续执行，直到 l > r?结束迭代。
??最后，当?mid = 2?时，找到数据 5。

4）算法描述

??a）令初始情况下，数组下标从 0 开始，且数组长度为?n，则定义一个区间，它的左端点是? ? ? l =?0，右端点是 r = n?1；
??b）生成一个区间中点 mid = (l+r)/2，并且判断 mid?对应的数组元素和给定的目标值的大小关系，主要有三种：
????b.1）目标值 等于 数组元素，直接返回 mid；
????b.2）目标值 大于 数组元素，则代表目标值应该出现在区间?[mid+1,r]，迭代左区间端点：l=mid+1；
????b.3）目标值 小于 数组元素，则代表目标值应该出现在区间?[l,mid?1]，迭代右区间端点：r=mid?1；
??c）如果这时候 l>r，则说明没有找到目标值，返回??1；否则，回到 b）继续迭代。

5）源码详解

int search(int *nums, int numsSize, int target) {
    int l = 0, r = numsSize - 1;         // (1)
    while(l <= r) {                      // (2)
        int mid = (l + r) >> 1;          // (3)
        if(nums[mid] == target) {   
            return mid;                  // (4)
        }else if(target > nums[mid]) {
            l = mid + 1;                 // (5)
        }else if(target < nums[mid]) {
            r = mid - 1;                 // (6)
        }
    }
    return -1;                           // (7)
}

• (1)?初始化区间左右端点；
• (2)?一直迭代左右区间的端点，直到?左端点 大于 右端点?结束；
• (3)?>> 1等价于除 2，也就是这里mid代表的是l和r的中点；
• (4)?nums[mid] == target表示正好找到了这个数，则直接返回下标mid；
• (5)?target > nums[mid]表示target这个数在区间?[���+1,�][mid+1,r]?中，所以才有左区间赋值如下：l = mid + 1;
• (6)?target < nums[mid]表示target这个数在区间?[�,���?1][l,mid?1]?中，所以才有右区间赋值如下：r = mid - 1;
• (7)?这一步呼应了?(2)，表示这不到给定的数，直接返回?-1；

5、三分枚举

??三分枚举?类似?二分枚举?的思想，也是将区间一下子砍掉一块基本完全不可能的块，从而减小算法的时间复杂度。只不过?二分枚举?解决的是 单调性 问题。而?三分枚举?解决的是 极值问题。

6、插入排序

1）问题描述

??给定一个?n?个元素的数组，数组下标从?0?开始，采用「 插入排序 」将数组按照?「升序」排列。

2）动图演示

3）样例说明

图示	含义
蓝色柱形	代表尚未排好序的数
绿色柱形	代表正在执行 比较 和 移动 的数
橙色柱形	代表已经排好序的数
红色柱形	代表待执行插入的数

??我们看到，首先需要将?「第二个元素」?和?「第一个元素」?进行?「比较」，如果?前者?小于等于?后者，则将?后者?进行向后?「移动」，前者?则执行插入；
??然后，进行第二轮「比较」，即?「第三个元素」?和?「第二个元素」、「第一个元素」?进行?「比较」， 直到?「前三个元素」?保持有序 。
??最后，经过一定轮次的「比较」?和?「移动」之后，一定可以保证所有元素都是?「升序」?排列的。

4）算法描述

整个算法的执行过程分以下几步：
??1）?循环迭代变量 i=1→n?1；
??2）?每次迭代，令 x=a[i]，j=i?1，循环执行比较 x?和 a[j]，如果产生 x≤a[j]?则执 行?a[j+1]=a[j]。然后执行j=j+1，继续执行?2）；否则，跳出循环，回到?1）。

5）源码详解

#include <stdio.h>

int a[1010];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void InsertSort(int n, int *a) {       // (1)
    int i, j; 
    for(i = 1; i < n; ++i) {
        int x = a[i];                  // (2)
        for(j = i-1; j >= 0; --j) {    // (3)
            if(x <= a[j]) {            // (4)
                a[j+1] = a[j];         // (5)
            }else
                break;                 // (6)
        }
        a[j+1] = x;                    // (7)
    }
} 

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        InsertSort(n, a);
        Output(n, a);
    }
    return 0;
} 

• (1)?void InsertSort(int n, int *a)为?插入排序?的实现，代表对a[]数组进行升序排序。
• (2) 此时a[i]前面的?i-1个数都认为是排好序的，令x = a[i]；
• (3) 逆序的枚举所有的已经排好序的数；
• (4) 如果枚举到的数a[j]比需要插入的数x大，则当前数往后挪一个位置；
• (5) 执行挪位置的?�(1)O(1)?操作；
• (6) 否则，跳出循环；
• (7) 将x插入到合适位置；

7、选择排序

1）问题描述

??给定一个?�n?个元素的数组，数组下标从?00?开始，采用「 选择排序 」将数组按照?「升序」排列。

2）动图演示

3）样例说明

图示	含义
蓝色柱形	代表尚未排好序的数
绿色柱形	代表正在执行 比较 的数
橙色柱形	代表已经排好序的数
红色柱形	有两种：1、记录最小元素 2、执行交换的元素

??我们发现，首先从?「第一个元素」?到?「最后一个元素」?中选择出一个?「最小的元素」，和?「第一个元素」?进行?「交换」；
??然后，从?「第二个元素」?到?「最后一个元素」?中选择出一个?「最小的元素」，和?「第二个元素」?进行?「交换」。
??最后，一定可以保证所有元素都是?「升序」?排列的。

4）算法描述

整个算法的执行过程分以下几步：
??1）?循环迭代变量 i=0→n?1；
??2）?每次迭代，令 min=i，j=i+1；
??3）?循环执行比较 a[j]?和 a[min]，如果产生 a[j]<a[min]?则执行 min=j。执行 j=j+1，继续执行这一步，直到 j==n；
??4）?交换 a[i]?和 a[min]，回到?1）。

5）源码详解

#include <stdio.h>

int a[1010];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void SelectionSort(int n, int *a) {  // (1)
    int i, j;
    for(i = 0; i < n - 1; ++i) {     // (2)
        int min = i;                 // (3)
        for(j = i+1; j < n; ++j) {   // (4)
            if(a[j] < a[min]) {
                min = j;             // (5)
            }
        }
        Swap(&a[i], &a[min]);        // (6) 
    }
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        SelectionSort(n, a);
        Output(n, a);
    }
    return 0;
} 

• (1)?void SelectionSort(int n, int *a)为选择排序的实现，代表对a[]数组进行升序排序。
• (2)?从首元素个元素开始进行 n?1?次跌迭代。
• (3)?首先，记录min代表当前第?i?轮迭代的最小元素的下标为?i。
• (4)?然后，迭代枚举第?i+1?个元素到 最后的元素。
• (5)?选择一个最小的元素，并且存储下标到?min中。
• (6)?将 第?i?个元素 和 最小的元素 进行交换。

8、冒泡排序

1）问题描述

??给定一个?n?个元素的数组，数组下标从?0?开始，采用「 冒泡排序 」将数组按照?「升序」排列。

2）动图演示

3）样例说明

图示	含义
蓝色柱形	代表尚未排好序的数
绿色柱形	代表正在执行比较的两个数
黄色柱形	代表已经排好序的数

??我们看到，首先需要将?「第一个元素」?和?「第二个元素」?进行?「比较」，如果?前者?大于?后者，则进行?「交换」，然后再比较?「第二个元素」?和?「第三个元素」?，以此类推，直到?「最大的那个元素」?被移动到?「最后的位置」?。
??然后，进行第二轮「比较」，直到?「次大的那个元素」?被移动到?「倒数第二的位置」?。
??最后，经过一定轮次的「比较」?和?「交换」之后，一定可以保证所有元素都是?「升序」?排列的。

4）算法描述

整个算法的执行过程分以下几步：
??1）?循环迭代变量 i=0→n?1；
??2）?每次迭代，令 j=i，循环执行比较?a[j]?和 a[j+1]，如果产生 a[j]>a[j+1]?则交换两者的值。然后执行 j=j+1，这时候对?j?进行判断，如果 j≥n?1，则回到?1），否则继续执行?2）。

5）源码详解

#include <stdio.h>

int a[1010];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void BubbleSort(int n, int *a) {             // (1)
    bool swapped;
    int last = n;
    do {
        swapped = false;                     // (2)
        for(int i = 0; i < last - 1; ++i) {  // (3)
            if(a[i] > a[i+1]) {              // (4)
                Swap(&a[i], &a[i+1]);        // (5)
                swapped = true;              // (6)
            }
        }
        --last;
    }while (swapped);
} 

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        BubbleSort(n, a);
        Output(n, a);
    }
    return 0;
} 

• (1)?void BubbleSort(int n, int *a)为冒泡排序的实现，代表对a[]数组进行升序排序。
• (2)?swapped标记本轮迭代下来，是否有元素产生了交换。
• (3)?每次冒泡的结果，会执行last的自减，所以待排序的元素会越来越少。
• (4)?如果发现两个相邻元素产生逆序，则将它们进行交换。保证右边的元素一定不比左边的小。
• (5)?swap实现了元素的交换，这里需要用&转换成地址作为传参。
• (6)?标记更新。一旦标记更新，则代表进行了交换，所以下次迭代必须继续。