iOS面试系列之常见算法

墨蓝 2022-05-21 06:22 128阅读 0赞

20180702 时隔一年半 再次坐在又爱又恨的Xcode前

1，冒泡算法

有2种思路，第一种，score\[j\] 和 score\[j+1\] 比较 如果 前者比后者小，把前者和后者调换顺序，两两调换后一轮下来 最小的会被排到最后去。每一轮j都从0开始，当i轮排序，就有最后面的i个数字因为他是最小的，所以后面的每轮都不用理他了，也就是 score.length-1-i  往后的数不用管了，如上，第一轮有4个数字 i为0 ，那么score.length-1-i  为3，也就是下标是3以后的可以不用管，3往后没有数字，所以第一轮所有的数字都要参加比较，第二轮I=1  score.length-1-i  为2 也就是说 下标2后面的 下标为3的数字不用比了，因为两两比较厚，67会到 score\[3\],实现代码如下：

for(int i =0;i < score.length - 1;i++)  
        \{  
            for(int j = 0;j <  score.length - 1-i;j++)// j开始等于0，  
            \{  
                if(score\[j\] < score\[j+1\])  
                \{  
                    int temp = score\[j\];  
                    score\[j\] = score\[j+1\];  
                    score\[j+1\] = temp;  
                \}  
            \}  
        \}  
  
第二种思路，用88 和 75 比较，在和69 比较 在和 67 比较，发现88是最大的，吧他排到第一位(index=0的位置)，然后i=1,也就是第二轮，就不用看下标为0的88了因为他是老大，然后接着比较。；

for(int i =0;i < score.length - 1;i++)  
        \{  
            for(int j = (score.length - 2);j >= i;j--)  
            \{  
                if(score\[j\] < score\[j+1\])  
                \{  
                    int temp = score\[j\];  
                    score\[j\] = score\[j+1\];  
                    score\[j+1\] = temp;  
                \}  
            \}  
        \}

2，选择排序

选择法：

假定a\[0\]为最值，先将10个数中最小的数与a\[0\]对换，（只有这俩对换，其余位置不变！！！）再将a\[1\]~a\[9\]中最小的数与a\[1\]对换......每比较一轮，找出未经排序的最小的数。以5个数为例子说明：

a\[0\]  a\[1\]  a\[2\]  a\[3\]  a\[4\]

2      5      0       8       3

\[0\]      5     \[2\]      8       3   将5个数中最小的与a\[0\]对换

0       \[2\]    \[5\]      8       3   将余下的4个数中最小的与a\[1\]对换

0        2     \[3\]      8      \[5\]   将余下的3个数中最小的与a\[2\]对换

0        2      3      \[5\]     \[8\]   将余下的2个数中最小的与a\[3\]对换

完成排序

选择排序法的复杂度：O(n\*n)

冒泡排序法：

临近数字两两依次比较，按从小到大或从大到小顺序交换，一趟过去之后，最大或最小的数字被交换到了最后一位。再从头开始比较，直到倒数第二位。

以5个数为例子说明：

a\[0\]  a\[1\]  a\[2\]  a\[3\]  a\[4\]

2      5      0        8       3

第一趟：第一次两两比较：   2      0      5        8       3

第一次两两比较：   2      0      5        3     \[ 8 \]

第二趟：                         0      2      3     \[  5       8 \]

第三趟：                         0      2   \[  3        5       8 \]

第四趟：                         0   \[  2      3        5       8 \]

完成排序。

冒泡排序法的复杂度：O(n\*n)。

选择的思想在于每次只有最值和第i个数对换，其余都保持原位不变！！！所以子函数里面，for循环里面的小for循环，只是把j赋给k，继续小for循环 ，不交换a\[j\]和a\[k\]的值。到外面的大for循环再交换a\[j\]和a\[k\]的值，这样就实现了选择排序。

void sort(int a\[\],int n)  
\{  
    int i, j, index;  
    for(i = 0; i < n - 1; i++) \{  
        index = i;  
        for(j = i + 1; j < n; j++) \{  
            if(a\[index\] > a\[j\]) \{  
                index = j;  
            \}  
        \}  
        if(index != i) \{  
            int temp = a\[i\];  
            a\[i\] = a\[index\];  
            a\[index\] = temp;  
        \}  
    \}  
\}  
   
int main(int argc, const char \* argv\[\]) \{  
    int numArr\[10\] = \{86, 37, 56, 29, 92, 73, 15, 63, 30, 8\};  
    sort(numArr, 10);  
    for (int i = 0; i < 10; i++) \{  
        printf("%d, ", numArr\[i\]);  
    \}  
    printf("\\n");  
    return 0;  
\}  
  
3，快速排序

\#include <bits/stdc++.h>  
using namespace std;  
void P(int a\[\],int n)  
\{  
    for(int i=0; i<n; i++)  
        cout<<a\[i\]<<" ";  
    cout<<endl;  
\}  
void quick\_sort(int s\[\], int l, int r)  
\{  
    if (l < r)  
    \{  
        //Swap(s\[l\], s\[(l + r) / 2\]); //将中间的这个数和第一个数交换 参见注1  
        int i = l, j = r, x = s\[l\];  
        while (i < j)  
        \{  
            while(i < j && s\[j\] >= x) // 从右向左找第一个小于x的数  
                j--;  
            if(i < j)  
                s\[i++\] = s\[j\];  
   
            while(i < j && s\[i\] < x) // 从左向右找第一个大于等于x的数  
                i++;  
            if(i < j)  
                s\[j--\] = s\[i\];  
        \}  
        s\[i\] = x;  
        quick\_sort(s, l, i - 1); // 递归调用  
        quick\_sort(s, i + 1, r);  
    \}  
\}  
int main()  
\{  
    //int a\[\]= \{72,6,57,88,60,42,83,73,48,85\};  
    int a\[\]= \{10,9,8,7,6,5,4,3,2,1\};  
    P(a,10);  
    quick\_sort(a,0,9);//注意最后一个参数是n-1!!!!!  
    P(a,10);  
    return 0;  
\}

4，