2024-10-02

329. 矩阵中的最长递增路径 - 力扣（LeetCode）
见上篇 2024-09-30 - 简书 (jianshu.com)
面试题 04.06. 后继者 - 力扣（LeetCode）
见上篇 2024-09-30 - 简书 (jianshu.com)
912. 排序数组 - 力扣（LeetCode）
排序一：冒泡排序==稳定==n^2==1

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return bubbleSort(nums);
    }

private:
    vector<int> bubbleSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            bool flag = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]); // 稳定
                    flag = true;
                }
            }
            if (flag == false) break;
        }
        return nums;
    }
};

排序二：选择排序==不稳定==n^2==1

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return selectSort(nums);
    }

private:
    vector<int> selectSort(vector<int> &nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i) {
            int minIndex = i;
            for (int j = i + 1; j < n; ++j) 
                if (nums[j] < nums[minIndex])
                    minIndex = j;
            swap(nums[i], nums[minIndex]); // 不稳定
        }
        return nums;
    }
};

排序三：插入排序==稳定==n^2==1

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return insertSort(nums);
    }

private:
    vector<int> insertSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1; i < n; i++)
            for (int j = i; j > 0; j--)
                if (nums[j - 1] > nums[j]) // 稳定
                    swap(nums[j - 1], nums[j]);
                else break; // !!!
        return nums;
    }
};

排序四：希尔排序==不稳定==nlogn和n^2之间==1

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return shellSort(nums);
    }

private:
    vector<int> shellSort(vector<int>& nums) {
        int n = nums.size();
        for (int gap = n / 2; gap > 0; gap /= 2)
            for (int i = gap; i < n; i++)
                for (int j = i; j - gap >= 0; j -= gap)
                    if (nums[j - gap] > nums[j])
                        swap(nums[j - gap], nums[j]); // 不稳定
                    else break; // !!!
        return nums;
    }
};

排序五：归并排序==稳定==nlogn==n

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        mergeSort(nums, left, right);
        return nums;
    }

private:
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    void merge(vector<int>& nums, int left, int mid, int right) {
        // nums[left...mid] nums[mid+1...right]
        int size = right - left + 1;
        vector<int> temp(size);
        int i = left, j = mid + 1, k = 0;
        for (; k < size; k++)
            if (j > right || (i <= mid && nums[i] <= nums[j])) // 稳定
                temp[k] = nums[i++];
            else
                temp[k] = nums[j++];
        for (k = 0; k < size; k++)
            nums[left + k] = temp[k];
    }
};

排序六：堆排序-不稳定-nlogn-1
法一：优先队列

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }

private:
    void heapSort(vector<int>& nums) {
        int n = nums.size();
        priority_queue<int> q;
        for (int i = 0; i < n; i++) q.push(-nums[i]);
        for (int i = 0; i < n; i++) {
            nums[i] = -q.top();
            q.pop();
        }
    }
};

法二：自实现二叉堆

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }

private:
    void heapSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapifyDown(nums, i, n);
        for (int i = n - 1; i >= 0; i--) {
            swap(nums[0], nums[i]); // 不稳定
            heapifyDown(nums, 0, i);
        }
    }

    void heapifyDown(vector<int>& nums, int index, int size) {
        int left = index * 2 + 1, right = index * 2 + 2;
        int max = index;
        if (left < size && nums[left] > nums[max])
            max = left;
        if (right < size && nums[right] > nums[max])
            max = right;
        if (max != index) {
            swap(nums[max], nums[index]);
            heapifyDown(nums, max, size);
        }
    }
};

排序七：快速排序==不稳定==nlogn==logn

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot); // A
        quickSort(nums, pivot + 1, right);
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = left + rand() % (right - left + 1);
        int pivotVal = nums[pivot];
        while (left <= right) {
            while (nums[left] < pivotVal) left++; // 此处代入pivotVal一起排序，所以为<，A处同理
            while (nums[right] > pivotVal) right--;
            if (left < right) {
                swap(nums[left], nums[right]);
                left++; right--;
            }
            else break;
        }
        return right;
    }
};

排序八：计数排序==稳定==(n+k)==(k)
k=maxNum-minNum+1

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int minVal = INT_MAX, maxVal = INT_MIN;
        for (int num : nums) {
            minVal = min(minVal, num);
            maxVal = max(maxVal, num);
        }
        vector<int> temp(maxVal - minVal + 1);
        for (int num : nums) temp[num - minVal]++;
        int k = 0;
        for (int i = 0; i < temp.size(); i++)
            while (temp[i] > 0) {
                nums[k++] = minVal + i;
                temp[i]--;
            }
        return nums;
    }
};

2024-10-02

推荐阅读更多精彩内容