您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

iOS 面試常見的三種基礎演算法:二分搜尋、氣泡排序、選擇排序

編輯:iOS 開發綜合

面試與日常開發中,這三個演算法出現的頻率最高。下面把實作與複雜度一起整理清楚。

二分搜尋法(Binary Search)

前提條件是資料必須已排序。每次比對中間元素後砍掉一半搜尋範圍,因此平均時間複雜度為 O(log₂n)。

int halfFunction(int a[], int length, int number)
{
    int start = 0;
    int end = length - 1;
    int index = 0;

    while (start <= end)
    {
        index = start + (end - start) / 2;

        if (a[index] == number)
        {
            return index;
        }
        else if (a[index] < number)
        {
            start = index + 1;
        }
        else
        {
            end = index - 1;
        }
    }

    return -1; // 找不到時回傳 -1
}

兩個細節值得注意:中間值用 start + (end - start) / 2 而非 (start + end) / 2,可以避免整數溢位;迴圈條件用 start <= end,並在找不到時回傳 -1,語意比回傳最後一次的中間值清楚得多。

氣泡排序(Bubble Sort)

平均時間複雜度:O(n²)
空間複雜度:O(1),只用於元素交換
穩定性:穩定

void bubbleFunction(int a[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

內層迴圈的 length - 1 - i 是關鍵:每一輪跑完,結尾都會多一個已排好的元素,不需要再比較。「穩定」的意思是數值相同的元素,排序後相對順序不會改變。

選擇排序(Selection Sort)

平均時間複雜度:O(n²)
空間複雜度:O(1)
穩定性:不穩定

void selectFunction(int a[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < length; j++)
        {
            if (a[j] < a[minIndex])
            {
                minIndex = j;
            }
        }

        if (minIndex != i)
        {
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

為什麼說它「不穩定」?以序列 [5, 5, 3] 為例,第一輪直接把索引 0 的 5 和索引 2 的 3 交換,原本在前面的那個 5 就被挪到後面去了,相同元素的相對順序因此被打亂。

另外提醒:標準的選擇排序應該是「每輪找最小值、跑完內層迴圈後只交換一次」。如果像某些範例那樣在內層迴圈裡每次都交換,雖然結果仍然正確,但交換次數會暴增,失去選擇排序本身的意義。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved