---
title: 計算機概論 - 作業 4 演算法之條條大路通羅馬
---

# 作業 4 演算法之條條大路通羅馬

> 作者 : 李信緯
> 學號 : D1211450
> e-mail : [e-mail]
> [name=naiye130]
> [time=Sat, Oct 28, 2023 8:52 PM]

## 搜尋
### 使用題目
:::success
### 278. First Bad Version
https://leetcode.com/problems/first-bad-version/
:::

### 二分搜尋

class Solution {
public:
    int firstBadVersion(int n) {
        int s = 0;
        int e = n;
        int bad;
        while(s<=e){            
            int mid = s + (e-s)/2;           
            if(isBadVersion(mid)){
                bad = mid;
                e = mid-1;
            }
            else
                s = mid+1;          
        }
        return bad;
    }
};


### 指數搜尋 (galloping search)

class Solution {
public:
    int firstBadVersion(int n) {
        if(isBadVersion(n)&&!isBadVersion(n-1)) return n;
        long i=1;
		// exponetial search
        while(i<n && !isBadVersion(i)){
            i =i*2;
        }
		// binary search 
        long low =i/2 , high=min(i,(long)n),mid;
        int ans;
        while(low<=high){
            int mid=low+(high-low)/2;
            if(isBadVersion(mid)==true){
                ans=mid;
                high=mid-1;
            }
            else
                low=mid+1;
        }
        return ans;
    }
};


## 排序
### 使用題目
:::success
### 912. Sort an Array
https://leetcode.com/problems/sort-an-array/
:::
### 堆積排序 (Heapsort)

class Solution {
public:
    void maxHeapify(vector<int>& nums, int n, int i){
        int largest = i;
        int left = (2 * i) + 1, right = (2 * i) + 2;
        if(left < n && nums[left] > nums[largest])
            largest = left;
        if(right < n && nums[right] > nums[largest])
            largest = right;
        if(largest != i){
            swap(nums[largest], nums[i]);
            maxHeapify(nums, n, largest);
        }
    }

    void heapSort(vector<int>& nums, int n){
        for(int i = n/2-1; i >= 0; i--)
            maxHeapify(nums, n, i);
        for(int i = n-1; i >= 0; i--){
            swap(nums[0], nums[i]);
            maxHeapify(nums, i, 0);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums, nums.size());
        return nums;
    }
};


### 合併排序 (Merge sort)

class Solution {
public:
    void merge(int low, int mid, int high, vector<int> &nums) {
        if (low >= high) return;
        int l = low, r = mid + 1, k = 0, size = high - low + 1;
        vector<int> sorted(size, 0);
        while (l <= mid and r <= high)
            sorted[k++] = nums[l] < nums[r] ? nums[l++] : nums[r++];
        while (l <= mid) 
            sorted[k++] = nums[l++];
        while (r <= high) 
            sorted[k++] = nums[r++];
        for (k = 0; k < size; k++)
            nums[k + low] = sorted[k];
    }

    void mergeSort(vector<int>& nums, int start, int end){
        if(start < end){
            int mid = start + (end - start) / 2;
            mergeSort(nums, start, mid);
            mergeSort(nums, mid + 1, end);
            merge(start, mid, end, nums);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }
};


### 優先佇列 (Priority Queue)

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i : nums)
            pq.push(i);
        for(int i=0;i<nums.size();i++){
            nums[i] = pq.top();
            pq.pop();
        }
        return nums;
    }
};


### 計數排序法 (Counting Sort)

	// bubbleSort(nums);
	void bubbleSort(vector<int>& nums){
        for(int i = nums.size() - 1; i >= 0; i--)
            for(int j = 0; j < i; j++)
                if(nums[j] > nums[j + 1]) 
                    swap(nums[j], nums[j + 1]);
    }


###### tags: `報告` `計算機概論`

{%hackmd @naiye130/__style %}