排序算法

发表于 2023-01-18 分类于算法

选择排序、冒泡排序、堆排序、快速排序、归并排序、桶排序

1 排序算法

$时间复杂度 O (n l o g n) ：归并排序、堆排序、快速排序$

稳定排序，是指在排序算法中，相同值的两个元素，在输入数组中先出现的数在输出数组中也先出现。像冒泡排序，插入排序，基数排序，归并排序等都是稳定排序。

原地(原址、就地)排序是指：基本上不需要额外辅助的的空间，允许少量额外的辅助变量进行的排序。就是在原来的排序数组中比较和交换的排序。像选择排序，插入排序，希尔排序，快速排序，堆排序等都会有一项比较且交换操作(swap(i,j))的逻辑在其中，因此他们都是属于原地(原址、就地)排序，而合并排序，计数排序，基数排序等不是原地排序。

根据一个数组对另一个数组排序

506. 相对名次 - 力扣（Leetcode）

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int n=score.size();
        vector<int> rank(n);
        for(int i=0;i<n;i++)
            rank[i]=i;
        sort(rank.begin(),rank.end(),[](int a,int b){
            return score[a]>score[b];
        });

        vector<string> ans(n);
        for(int i=0;i<n;i++){
            // 排名为i+1的运动员下标位置
            int pos=rank[i];
            if(i==0){
                ans[pos]="Gold Medal";
            }else if(i==1){
                ans[pos]="Silver Medal";
            }else if(i==2){
                ans[pos]="Bronze Medal";
            }else{
                ans[pos]=to_string(i+1);
            }
        }
        return ans;
    }
};

1.1 选择排序

#include <iostream>
using namespace std;
int main()
{
    int data[5] = {5, 3, 1, 4, 2};
    int length = sizeof(data) / sizeof(data[0]);
    for (int i = 0; i < length - 1; i++)
    {
        int k = i;//记录最小值索引
        for (int j = i + 1; j < length; j++)
            if (data[k] > data[j])
                k = j;
        int temp = data[i];
        data[i] = data[k];
        data[k] = temp;
    }

    for (int i = 0; i < length; i++)
        cout << data[i] << ' ';
}

1.2 冒泡排序

#include <iostream>
using namespace std;
void show_data(int data[], int len)
{
    for (int i = 0; i < len - 1; i++)
        cout << data[i] << " ";
    cout << data[len - 1] << endl;
}
/*
    冒泡排序，正序，大数向上冒出
*/
void bubble_sort1(int data[], int len)
{
    cout << len << endl;
    for (int i = 0; i < len - 1; ++i)
    {
        for (int j = 1; j < len - i; ++j)
        {
            if (data[j - 1] > data[j])
            {
                int t = data[j - 1];
                data[j - 1] = data[j];
                data[j] = t;
            }
        }
    }
    show_data(data, len);
}
/*
    冒泡排序，正序，小数向下冒出
*/
void bubble_sort2(int data[], int len)
{
    cout << len << endl;
    for (int i = 0; i < len - 1; ++i)
    {
        for (int j = len - 1; j > i; --j)
        {
            if (data[j] < data[j - 1])
            {
                int t = data[j];
                data[j] = data[j - 1];
                data[j - 1] = t;
            }
        }
    }
    show_data(data, len);
}
int main()
{
    int data1[10] = {1, 4, 2, 5, 3, 10, 8, 7, 9, 6};
    bubble_sort1(data1, sizeof(data1) / sizeof(int));
    int data2[10] = {1, 4, 2, 5, 3, 10, 8, 7, 9, 6};
    bubble_sort2(data2, sizeof(data2) / sizeof(int));
    return 0;
}

1.3 堆排序（优先队列，堆，heap）

拜托，面试别再问我TopK了！！！ (qq.com)

在大根堆中，父节点的值比每一个子节点的值都要大；在小根堆中，父节点的值比每一个子节点都要小。下面的堆以大根堆为例。

优先队列(priority queue)可以在O(1)的时间内获取最大值，在O(logn)时间内取出最大值或者插入任意值。优先队列通常用堆(heap)实现，堆是一颗完全二叉树，其每个节点的值总是大于等于子节点的值。

上浮：如果一个节点比父节点大，需要交换这两个节点；交换后可能仍比新的父节点大，需要继续向上比较和交换下沉：子节点比父节点大，父节点向下交换；交换后仍需向下继续比较和交换

进行堆排序时，不断将堆顶元素与堆底元素交换，进行下沉操作插入元素时，把元素放在最后，进行上浮操作。

插入元素，上浮操作
//小根堆
//将元素插入堆最后面，元素大小i=n（下标从1开始）
InsertHeap(A,i){
 	while(i>1){
        //与父节点比较大小
        if(A[i/2]<A[i])
            break;
        swap(A[i/2],A[i]);
        i=i/2;
	}   
}

插入建堆（边插入元素边调整堆）
InsBuildHeap(){
    for(int i=1;i<=n;i++){
        A[i]=x;
        InsertHeap(A,i);
    }
}

调整堆，下沉操作
//i为堆顶，k为堆底
HeapRectify(A,i,k){
    if(2*i+1<=k){
        m=min(A[2i],A[2i+1])	//m为两者小的下标
        if(A[i]>A[m]){
            swap(A[i],A[m])
            i=m;
        }
    }
    if(2*i=k&&A[i]>A[k]){
        swap(A[i],A[k]);
    }
}

调整完绿色节点后，6上升，2下降，同时需要继续向下调整

下标从0开始，i孩子节点为，$2i+1,2i+2 $，父节点为$ \frac{i-1}{2} $下标从 1 开始， i 孩子节点为，$ 2i,2i+1 $，父节点为$ \frac{i}{2}$

算法-堆.png

1.3.1 大根堆（筛选建堆）

//筛选建堆，从最后一个非叶子节点开始
void builtHeap(vector<int>& nums){
    int n=nums.size()-1;	//n为最后一个元素下标
    for(int i=(n-1)/2;i>=0;i--)
        Heapify(nums,i,n-1);
}

// 利用删除的调整过程建堆，时间复杂度O(n)
// 调整堆，从i开始调整，下沉，
void Heapify(vector<int>& nums,int i,int heapSize){
    //到达叶子节点
 	while(2*i+1<=heapSize){
        int largest=2*i+1;
        //存在右节点且右节点更大
        if(2*i+2<=heapSize&&nums[2*i+2]>nums[largest]){
            largest=2*i+2;
        }

        //需要进行交换
        if(nums[largest]>nums[i]){
            swap(nums[i],nums[largest]);
            i=largest;
        }else{
            break;
        }
 	}
}

//利用插入建堆，不断插入元素，然后上浮调整，时间复杂度：O(nlogn)
void InsertHeap(vector<int>& nums){
	int i=nums.size()-1;   //新插入元素位置
	while(i>0){
		if(nums[(i-1)/2]>=nums[i])
			break;
		swap(nums[(i-1)/2],nums[i]);
		i=(i-1)/2;
	}
}

int findKthLargest(vector<int>& nums, int k) {
    // 建立大根堆，不断弹出堆顶元素
    // 通过筛选建堆
    int n=nums.size();
    builtHeap(nums);
    for(int i=1;i<k;i++){
        //最大节点与底部交换
        swap(nums[0],nums[n-i]);
        Heapify(nums,0,n-1-i);
    }
    return nums[0];

}

1.4 快速排序

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

    void quickSort(vector<int>& nums,int left,int right){
        if(left>=right){
            return;
        }

        int l=left,r=right;
        // 随机从[left,right]中选择一个主元
        int t=rand()%(right-left+1)+left;
        swap(nums[t],nums[left]);
        int pivot=nums[left];


        while(l<r){
            while(l<r&&nums[r]>=pivot)
                r--;
           	nums[l]=nums[r];
            while(l<r&&nums[l]<=pivot)
                l++;
            nums[r]=nums[l];
        }
        nums[l]=pivot;
        quickSort(nums,left,l-1);
        quickSort(nums,l+1,right);
    }
};

1.5 归并排序

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

    void merge_sort(vector<int> &nums, int left, int right, vector<int> &tmp) {
        if (left >= right)
            return;
        int m = left + (right - left) / 2;
        // cout << left << " " << right << endl;
        merge_sort(nums, left, m, tmp);
        merge_sort(nums, m + 1, right, tmp);

        int p = left, q = m + 1, i = left;
        while (p <= m || q <= right) {
            if (q > right || (p <= m && nums[p] <= nums[q])) {
                tmp[i++] = nums[p++];
            } else {
                tmp[i++] = nums[q++];
            }
        }

        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i];
        }
    }
};

1.6 桶排序

1.7 插入排序(insertion sort)

适用于元素基本有序的情况

1.8 题单

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

方法一：堆排序

class Solution {
  public:
    int findKthLargest(vector<int> &nums, int k) {
        if (nums.size() < k) {
            return -1;
        }

        int n = nums.size() - 1;
        // 筛选建堆
        for (int i = (n - 1) / 2; i >= 0; i--) {
            HeapRecify(nums, i, n);
        }

        // 执行k-1次删除操作
        for (int i = 1; i <= k - 1; i++) {
            swap(nums[0], nums[n]);
            n--;
            HeapRecify(nums, 0, n);
        }
        return nums[0];
    }
    /**
     * 筛选调整堆，i为堆顶，n为堆底
     */
    void HeapRecify(vector<int> &nums, int i, int n) {
        // 存在左右孩子
        while (2 * i + 2 <= n) {
            int m;
            if (nums[2 * i + 1] > nums[2 * i + 2]) {
                m = 2 * i + 1;
            } else {
                m = 2 * i + 2;
            }
            // 堆顶小，向下调整
            if (nums[i] < nums[m]) {
                swap(nums[i], nums[m]);
                i = m;
            }else{
                break;
            }
        }
        if (2 * i + 1 == n && nums[i] < nums[n]) {
            swap(nums[i], nums[n]);
        }
    }
};

方法二：快速选择

快速排序算法思想的应用，快速排序每次可以确定一个元组的位置

$T (n) = 2 * T (n / 2) + (n - 1)$

$T (n) = n + T (n / 2)$

#include <iostream>
#include <vector>
using namespace std;
/*
    找出数组中第K大的数，从0开始
*/
int quickSelection(vector<int> &nums, int l, int r) {
    int key = nums[l];
    while (l < r) {
        while (l < r && nums[r] >= key) {
            --r;
        }
        nums[l] = nums[r];
        while (l < r && nums[l] <= key) {
            l++;
        }
        nums[r] = nums[l];
    }
    nums[l] = key;
    return l;
}
int findKthLargest(vector<int> &nums, int k) {
    int l = 0, r = nums.size() - 1;
    int target = nums.size() - k;
    while (l < r) {
        int mid = quickSelection(nums, l, r);
        // cout << "l" << l << " mid" << mid << " r" << r << endl;
        if (mid == target)
            return nums[mid];
        if (mid > target)
            r = mid - 1;
        else {
            l = mid + 1;
        }
    }
    return nums[l];
}

int main() {
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    cout << findKthLargest(nums, 2);
    return 0;
}

1.8.2 23. 合并 K 个升序链表（堆）

写priority_queue的比较函数

struct Comp{
    bool operator()(ListNode* a,ListNode* b){
        return a->val>b->val;
    }
};
class Solution {
  public:
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        typedef pair<int, ListNode *> pii;
        priority_queue<ListNode*,vector<ListNode*>,Comp> pq; // 小根堆
        for (ListNode *list : lists) {
            if(list!=nullptr)
                pq.push(list);
        }

        ListNode *root = new ListNode(-1), *cur = root;
        while (!pq.empty()) {
            auto p= pq.top();
            pq.pop();
            cur->next = new ListNode(p->val);
            cur = cur->next;
            if (p->next != nullptr)
                pq.push(p->next);
        }
        return root->next;
    }
};

1.8.3 218. 天际线问题（堆）

类似于单调栈，移除无用元素

class Solution {
  public:
    vector<vector<int>> getSkyline(vector<vector<int>> &buildings) {
        int n = buildings.size();
        typedef pair<int, int> pii;
        // 高度，右侧边界
        priority_queue<pii, vector<pii>, less<>> maxHeap;

        vector<vector<int>> ans;
        int i = 0;
        int cur_x, cur_h = 0;
        while (i < n || !maxHeap.empty()) {
            if (maxHeap.empty() ||
                (i < n && buildings[i][0] <= -maxHeap.top().second)) {
                cur_x = buildings[i][0];
                while (i < n && buildings[i][0] <= cur_x) {
                    maxHeap.push({buildings[i][2], -buildings[i][1]});
                    i++;
                }

                // 插入节点导致高度变高
                if (maxHeap.top().first > cur_h) {
                    cur_h = maxHeap.top().first;
                    ans.push_back({cur_x, cur_h});
                }
                // maxHeap.push({buildings[i][2], -buildings[i][1]});
                // i++;
            } else {
                cur_x = -maxHeap.top().second;
                maxHeap.pop();

                // 把所有<=cur_x的全部弹出
                while (!maxHeap.empty() && -maxHeap.top().second <= cur_x)
                    maxHeap.pop();

                if (maxHeap.empty()) {
                    ans.push_back({cur_x, 0});
                    cur_h = 0;
                } else if (maxHeap.top().first < cur_h) {
                    cur_h = maxHeap.top().first;
                    ans.push_back({cur_x, cur_h});
                }
            }
        }
        return ans;
    }
};