[数据结构与算法]算法总结：内排序

内排序比较

• 算法复杂度与初始状态无关的有：选择排序、堆排序、归并排序、基数排序
• 元素总比较次数与初始状态无关的有：选择排序、基数排序
• 元素移动次数与初始状态无关的有：归并排序、基数排序

插入排序

算法

void insertSort(vector<int> &arr) {
    for (int i = 1; i < arr.size(); ++i) {
        int temp = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            --j;
        }

        arr[j + 1] = temp;
    }
}

分析

• 空间效率：$O(1)$
• 时间效率：$O(n^2)$
  • 最好情况：元素正序排列，不需要执行内循环，共比较元素$n?1$次，移动元素$0$次
  • 最坏情况：元素逆序排列，第$i\in [1,n?1]$趟外循环中比较元素$i$次，移动元素$i$次，共比较元素${\sum }_{i=1}^{n?1}i=\frac{n(n?1)}{2}$次，移动元素${\sum }_{i=1}^{n?1}i=\frac{n(n?1)}{2}$次
• 稳定性：稳定
• 适用性：顺序存储和链式存储的线性表。
• 特点：
  • 固定跑$n?1$趟
  • 时间效率与比较次数直接相关
  • 适用于规模小，元素有序或随机分布

变体：折半插入排序

• 仅减少了比较次数，时间复杂度仍为$O(n^2)$
• 元素的排列不再影响比较次数

int upperBound(vector<int> &arr, int l, int r, int target) {
    while (l < r) {
        int m = l + (r - l) / 2;

        if (arr[m] > target) {
            r = m;
        }
        else {
            l = m + 1;
        }
    }    

    return l;
}

void insertSort(vector<int> &arr) {
    for (int i = 1; i < arr.size(); ++i) {
        int temp = arr[i];
        //折半查找第一个大于temp元素的位置
        int t = upperBound(arr, 0, i, temp);
        for (int j = i; j > t; --j) arr[j] = arr[j - 1];
        arr[t] = temp;
    }
}

希尔排序

算法

void shellSort(vector<int> &arr) {
    int n = arr.size();
    
    //以k为增量进行分组，每组分别进行插入排序
    for (int k = n / 2; k; k = k / 2) {
        for (int i = k; i < n; ++i) {
            int temp = arr[i];
            int j = i - k;

            while (j >= 0 && arr[j] > temp) {
                arr[j + k] = arr[j];
                j -= k;
            }

            arr[j + k] = temp;
        }
    }
}

分析

• 空间效率：$O(1)$
• 时间效率：$O(n^{\frac{3}{2}})$，优化原理：若待排序的序列时基本有序时，可以减少比较次数，由此减小时间复杂度
• 稳定性：不稳定
• 适用性：仅顺序存储的线性表，不能在链表上进行

冒泡排序

算法

void BubbleSort(vector<int> &arr) {
    int n = arr.size();
    
    // 共n-1趟排序，每趟将第n - i大的元素沉底
    for (int i = 0; i < n - 1; ++i) {
        bool flag = true;

        for (int j = 1; j < n - i; ++j) {
            if (arr[j - 1] > arr[j]) {
             	swap(arr[j - 1], arr[j]);
                flag = false;
            }
        }

        // 一趟排序无交换发生，则元素已经有序，提前跳出
        if (flag) break;
    }
}

分析

• 空间效率：$O(1)$
• 时间效率：$O(n^2)$
  • 最好情况：元素正序排列，第$1$趟外循环中发现没有元素交换就会跳出，共比较元素$n?1$次，交换元素$0$次
  • 最坏情况：元素逆序排列，需要$n?1$趟外循环，第$i\in [1,n?1]$趟外循环中比较元素$n?i$次，交换元素$n?i$次，共比较元素${\sum }_{i=1}^{n?1}n?i=\frac{n(n?1)}{2}$次，交换元素${\sum }_{i=1}^{n?1}n?i=\frac{n(n?1)}{2}$次
• 稳定性：稳定
• 适用性：顺序存储和链式存储的线性表
• 特点：
  • 排序趟数$\in [1,n?1]$，与元素的排列有关
  • 适用于规模小，元素基本有序。一般情况效率最差
  • 每趟排序后都会将一个较大元素放在最终位置上

快速排序

算法

//Hoare法（左右指针法），以快排创始人Hoare命名，是快排最初的实现版本
void quickSort(vector<int> &arr, int l, int r) {
    if (l >= r) return;
	
	//选择arr[l]作为分界元素
    int i = l, j = r;
    while (i < j) {
    	//从右往左找比arr[l]小的元素
        while (i < j && arr[j] >= arr[l]) --j;
        //从左往右找比arr[l]大的元素
        while (i < j && arr[i] <= arr[l]) ++i;
        swap(arr[i], arr[j]);
    }
    
    //由于先从右往左找，后从左往右找，i和j相遇时，arr[i]比arr[l]小
    swap(arr[l], arr[i]);
    quickSort(arr, l, i - 1);
    quickSort(arr, i + 1, r);
}

//挖坑法
void quickSort(vector<int> &arr, int l, int r) {
    if (l >= r) return;
        
    //选择arr[l]作为分界元素，把元素挖出来形成一个坑
    int key = arr[l];
    int i = l, j = r;
    while (i < j) {
    	//从右往左找比key小的元素
        while (i < j && arr[j] >= key) --j;
        //用arr[j]来填arr[i]的坑
        arr[i] = arr[j];
        //从左往右找比key大的元素
        while (i < j && arr[i] <= key) ++i;
        //用arr[i]来填arr[j]的坑
        arr[j] = arr[i];
    }
    
    //最后剩下的坑由key来填
    arr[i] = key;
    quickSort(arr, l, i - 1);
    quickSort(arr, i + 1, r);
}

分析

• 空间效率：$O({\log }_{2}n)$，递归需要栈空间
• 时间效率：$O(n{\log }_{2}n)$，与划分是否对称有关
  • 最好情况：每次划分都最平衡，$O(n{\log }_{2}n)$
  • 最坏情况：元素已经有序排列，每次划分中有一个区域元素个数为$0$，退化成冒泡排序，$O(n^2)$
• 稳定性：不稳定
• 适用性：仅顺序存储的线性表，不能在链表上进行
• 特点：
  • 元素移动间隔较大，比较次数较少，速度较快
  • 适用于规模大，元素随机分布
  • 每趟排序后都会将基准元素放在最终位置上
• 提高效率的策略：
  • 优化基准元素的选取策略，使得划分更加平衡，如三数取中法，随机法等
  • 子问题规模较小时使用插入排序

题目

LeetCode215. 数组中的第K个最大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int l = 0, r = n - 1;

        while (true) {
            int i = l, j = r;

            while (i < j) {
                while (i < j && nums[j] >= nums[l]) --j;
                while (i < j && nums[i] <= nums[l]) ++i;
                swap(nums[i], nums[j]);
            }            
            swap(nums[i], nums[l]);

            if (i < n - k) {
                l = i + 1;
            }
            else if (i > n - k) {
                r = i - 1;
            }
            else {
                return nums[i];
            }
        }

        return -1;
    }
};

选择排序

算法

void selectionSort(vector<int> &arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; ++i) {
        int minValIdx = i;

        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minValIdx]) {
                minValIdx = j;
            }
        }

        swap(arr[i], arr[minValIdx]);
    }
}

分析

• 空间效率：$O(1)$
• 时间效率：$O(n^2)$，总是需要比较${\sum }_{i=1}^{n?1}n?i=\frac{n(n?1)}{2}$次
• 稳定性：不稳定
• 适用性：顺序存储和链式存储的线性表
• 特点：
  • 固定跑$n?1$趟
  • 元素的排列与比较次数无关
  • 适用于规模小

堆排序

算法

// 自己实现大顶堆
class Heap {
private:
    vector<int> arr;
public:
    void insert(int num) {
        //将新元素插入到堆的末端
        int i = arr.size();
        arr.emplace_back(num);
        
        //新元素不断与其父元素比较，如果新元素比父元素大，则两者互换
        while (i) {
            int parent = (i - 1) / 2;
            if (arr[i] <= arr[parent]) break;
            swap(arr[i], arr[parent]);
            i = parent;
        }
    }

    int pop() {
        if (arr.empty()) return INT_MIN;

        //堆顶元素与堆末元素互换，删除堆末元素
        int n = arr.size();
        int res = arr[0];
        arr[0] = arr[n - 1];
        arr.pop_back();
        //对堆顶元素进行向下调整，恢复堆的性质
        heapify(arr, 0, n);

        return res;
    }

    //对某一元素进行向下调整，使其恢复堆的性质，需确保该元素的左右子树已经是堆
    static void heapify(vector<int> &arr, int index, int len) {
        int lchild = 2 * index + 1;

        //该元素不断与其左右孩子中最大的进行比较，若左右孩子中最大值大于该元素则两者互换并继续向下比较，反之则停止
        while (lchild < len) {
            int largest = lchild + 1 < len && arr[lchild + 1] > arr[lchild] ? lchild + 1 : lchild;
            if (arr[largest] > arr[index]) {
                swap(arr[largest], arr[index]);
                index = largest;
                lchild = 2 * index + 1;
            }
            else {
                break;
            }
        }
    }
};

void heapSort(vector<int> &arr) {
    //法一：原地建堆，然后排序
    //将数组看成是完全二叉树的顺序存储，此时叶节点都具备堆的性质，这些叶节点的父节点只需进行一次调整操作就可以变成堆
    //于是将非叶子节点自底向上地进行调整便可以将整个完全二叉树变成堆，完全二叉树中n/2-1是最后一个非叶子节点
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; --i) {
        Heap::heapify(arr, i, n);
    }
    //进行n-1趟排序，每次将堆顶与堆末交换，然后将堆末元素移除出堆，最后对堆顶进行向下调整
    for (int i = 1; i < n; ++i) {
        swap(arr[0], arr[n - i]);
        Heap::heapify(arr, 0, n - i);
    }

    //法二：将元素依次插入到堆中，然后不断从堆中拿出堆顶元素
    // Heap heap;
    // for (int i : arr) heap.insert(i);
    // for (int i = arr.size() - 1; i >= 0; --i) arr[i] = heap.pop();
    
    //法三：用自带的优先队列实现
    // priority_queue<int, vector<int>, greater<int>> q;
    // for (int i : arr) q.emplace(i);
    // for (int i = 0; i < arr.size(); ++i) {
    //     arr[i] = q.top();
    //     q.pop();
    // }
}

分析

• 空间效率：$O(1)$
• 时间效率：$O(n{\log }_{2}n)$
• 稳定性：不稳定
• 适用性：仅顺序存储的线性表，不能在链表上进行
• 特点：
  • 固定跑$n?1$趟
  • 相比于快速排序，无论什么情况，时间复杂度都是$O(n{\log }_{2}n)$
  • 适用于规模大，元素可能出现有序分布

归并排序

算法

void process(vector<int> &arr, int l, int r, vector<int> &temp) {
    if (r - l <= 1) return;

    int m = l + (r - l) / 2;
    process(arr, l, m, temp);
    process(arr, m, r, temp);

    int i = l, j = m, k = l;
    while (i < m && j < r) temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    while (i < m) temp[k++] = arr[i++];
    while (j < r) temp[k++] = arr[j++];
    while (k-- > l) arr[k] = temp[k];
}

void mergeSort(vector<int> &arr) {
    int r = arr.size();
    vector<int> temp(r);
    process(arr, 0, r, temp);
}

分析

• 空间效率：$O(n)$，合并两个有序数组时需要额外辅助空间
• 时间效率：$O(n{\log }_{2}n)$，共需$?{\log }_{2}n?$趟归并，每趟时间复杂度为$O(n)$
• 稳定性：稳定
• 适用性：顺序存储和链式存储的线性表
• 特点：无论什么情况，时间复杂度都是$O(n{\log }_{2}n)$

题目

合集：https://leetcode-cn.com/tag/merge-sort/problemset/

LeetCode剑指Offer 51. 数组中的逆序对

class Solution {
private:
    int mergeSort(vector<int> &nums, int l, int r, vector<int> &temp) {
        if (r - l <= 1) return 0;

        int m = l + (r - l) / 2;
        int res = mergeSort(nums, l, m, temp) + mergeSort(nums, m, r, temp);
        
        int i = l, j = m, k = l;
        while (i < m && j < r) {
            if (nums[i] > nums[j]) {
                res += r - j;
                temp[k++] = nums[i++];
            } 
            else {
                temp[k++] = nums[j++];
            }
        }

        while (i < m) temp[k++] = nums[i++];
        while (j < r) temp[k++] = nums[j++];
        while (k-- > l) nums[k] = temp[k];

        return res;
    }
public:
    int reversePairs(vector<int>& nums) {
        int r = nums.size();
        vector<int> temp(r);
        return mergeSort(nums, 0, r, temp);
    }
};

基数排序（桶排序）

算法

void RadixSort(vector<int> &arr) {
    int n = arr.size();
    vector<queue<int>> buckets(n);

    //先获得元素中最大元素有几位，确定排序趟数k
    int k = 0;
    for (int num : arr) {
        int cnt = 0;

        while (num) {
            num /= 10;
            ++cnt;
        }

        k = max(k, cnt);
    }

    //第i趟对第i位数进行排序
    for (int i = 0; i < k; ++i) {
        int base = pow(10, i);
        //将元素分配到桶中
        for (int num : arr) {
            buckets[num / base % 10].push(num);
        }

        int j = 0;
        //将桶中的元素按顺序收集回数组
        for (queue<int> &bucket : buckets) {
            while (!bucket.empty()) {
                arr[j++] = bucket.front();
                bucket.pop();
            }
        }
    }
}

分析

设元素个数为$n$，最大元素位数为$d$，每位有$r$种取值（基数）

• 空间效率：$O(n+r)$
• 时间效率：$O(d(n+r))$，共进行$d$趟外循环，每趟中需要对$n$个元素进行分配，对$r$个桶进行收集
• 稳定性：稳定
• 适用性：顺序存储和链式存储的线性表，元素为自然数
• 特点：
  • 无论什么情况，时间复杂度都是$O(d(n+r))$
  • 适用于规模大，位数小

自定义排序题目

LeetCode937. 重新排列日志文件
法一：手写排序

class Solution {
private:
    bool isSmaller(const string &a, const string &b) {
        bool flag1 = isdigit(a.back());
        bool flag2 = isdigit(b.back());

        if (!flag1 && flag2) return true;

        if (!flag1 && !flag2) {
            int idx1 = a.find(' '), idx2 = b.find(' ');
            string perfix1 = a.substr(0, idx1), suffix1 = a.substr(idx1 + 1);    
            string perfix2 = b.substr(0, idx2), suffix2 = b.substr(idx2 + 1);     

            if (suffix1 == suffix2 && perfix1 < perfix2 || suffix1 < suffix2) return true;
        }

        return false;
    }
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        int n = logs.size();

        for (int i = 1; i < n; ++i) {
            string temp = logs[i];
            int j = i;

            while (j > 0 && isSmaller(temp, logs[j - 1])) {
                logs[j] = logs[j - 1];
                --j;
            }

            logs[j] = temp;
        }

        return logs;
    }
};

法二：使用api

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(logs.begin(), logs.end(), [&](const string & a, const string & b) {
            bool flag1 = isdigit(a.back());
            bool flag2 = isdigit(b.back());

            if (!flag1 && flag2) return true;

            if (!flag1 && !flag2) {
                int idx1 = a.find(' '), idx2 = b.find(' ');
                string perfix1 = a.substr(0, idx1), suffix1 = a.substr(idx1 + 1);    
                string perfix2 = b.substr(0, idx2), suffix2 = b.substr(idx2 + 1);     

                if (suffix1 == suffix2 && perfix1 < perfix2 || suffix1 < suffix2) return true;
            }

            return false;
        });

        return logs;
    }
};

剑指 Offer 45. 把数组排成最小的数

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        for (int num : nums) strs.push_back(to_string(num));

        sort(strs.begin(), strs.end(), [&](const string &a, const string &b) {
            return a + b < b + a;
        });

        string res;
        for (const string &s : strs) res += s;
        
        return res;
    }
};