算法系列-排序

快排

模板：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

自己写输入输出的格式：

include<bits/stdc++.h>
using namespace std;

void quick_sort(vector<int> &ans, int left, int right) {
    if(left >= right) return; //即输入已经不是l < r，直接返回
    int l = left - 1; //因为每次都是先加，再比较，所以初始化时初始化到前面一个位置
    int r = right + 1;
    int x = ans[l + r >> 1];
    while(l < r) {
        do l ++ ; while (ans[l] < x);
        do r -- ; while (ans[r] > x);
        if(l < r) swap(ans[l], ans[r]);
    }
    quick_sort(ans, left, r);
    quick_sort(ans, r + 1, right);
}

int main() {
    int N;
    vector<int> ans;
    cin >> N;
    while(N --) {
        int x;
        cin >> x;
        ans.push_back(x);
    }
    quick_sort(ans, 0, ans.size() - 1);
    for(auto x : ans) {
        cout << x << " ";
    }
    
    return 0;
    
}

核心代码模式：

class Solution {
    int partition(vector<int> &nums,int l, int r) {
        int p = nums[r]; //p是待比较的数
        int i = l - 1; //不确定第一个数比p大还是小，所以指针移到上一位
        for(int j = l;j < r ;++j) {//快慢指针，保证i自己和它左边的数一定比p小
            if(nums[j] <= p) {//从左遍历到右，如果快指针j找到了比p小的，就交给慢指针
                i = i + 1;
                swap(nums[j],nums[i]);
            }
        }
        swap(nums[i+1],nums[r]);//因为i本身也比p小，就i+1指定比p大，所以可以直接换
        return i + 1;
    }
    int rand_partition(vector<int> &nums,int l, int r) {
        int random_pos = rand() % (r - l + 1) + l;// % (r-l+1)控制随机数的范围，减是防止直接加导致数据过界
        swap(nums[random_pos],nums[r]); //将选中的随机数换到最后
        return partition(nums,l,r);
    }
    void quicksort(vector<int> &nums,int l, int r) {
        if(l < r) {
            int pos = rand_partition(nums,l,r);
            quicksort(nums,l,pos - 1);
            quicksort(nums,pos + 1,r);
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));//
        quicksort(nums,0,(int)nums.size() - 1);
        return nums;

    }
};

srand(time(NULL)); 的意思是：使用当前时间进行随机数发生器的初始化。

t是空指针（NULL），直接返回当前时间。

time() 是指返回自 Unix 纪元起的当前时间的秒数的函数，主要用来获取当前的系统时间，返回的结果是一个time_t类型。

srand函数是随机数发生器的初始化函数。原型：void srand(unsigned int seed); srand和rand()配合使用产生伪随机数序列。

归并排序

数组

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], tmp[N]; // 声明一个指定大小的数组

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; //在这里l到r是闭区间，判断条件要取等号
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}

链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val; //规定链表的值
 *     ListNode *next;//规定链表一个指针，指向下一个链表的存储空间
 *     ListNode() : val(0), next(nullptr) {}//构造函数，定义一个存储的值为0，指向NULL的新结点
 *     // ListNode *dummyNode = new ListnNode(0);是新建结点的方式
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * }; //记得结构体和类后面要跟分号
 */
class Solution {
private:
    ListNode *mergesort(ListNode *&head) { //这里记得head加上引用
        if(head == NULL || head->next == NULL) return head;

        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *pre = NULL;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            pre = slow;//慢指针的前驱
            slow = slow->next;
        }
        pre->next = NULL;//将慢指针前一个结点的next置为空，慢指针前面要断开
        ListNode *l = mergesort(head);//将左边链表分开
        ListNode *r = mergesort(slow);//将右边链表分开
        return merge(l,r);//分开后的每一个链表都会运行merge进行合并
    }
    ListNode *merge(ListNode *l, ListNode *r) {
        //合并有序链表
        //1. 新建dummy结点：左边声明指针 = 右边new一片空间出来
        //2.在左右都不为空时，谁小谁往cur后面接，注意cur接了结点之后要往后走一步
        //3.没有空的直接补到后面就好。return一点不能在里面的大括号里，要在函数域里
        ListNode *dummyNode = new ListNode(0);
        ListNode *cur = dummyNode;
        while(l != NULL && r != NULL) {
            if(l->val < r->val) {
                cur->next = l;
                l = l->next;
                cur = cur->next; //这一步容易掉，记得cur也要跟进指针
            }
            else {
                cur->next = r;
                r = r->next;
                cur = cur->next; //这一步容易掉，记得cur也要跟进指针
            }
        }
        if(l != NULL) {
            cur->next = l;
        }
        if(r != NULL) {
            cur->next = r;
        }
        return dummyNode->next;

    }
public:
    //1. 通过快慢指针找到中点，一个走两步一个走一步
    //2. 再拆开，递归1，拆到最小的L链表和R链表
    //3. 再合并，比较值合并链表
    //新建一个链表的时候可以用dummy结点
    ListNode* sortList(ListNode* head) {
        return mergesort(head);
    }
};

返回倒数第k大的数

acm 模式

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int q[N], k;

int quick_sort(int l, int r, int k)
{
    if (l == r) return q[l];
    int pos = rand() % (r - l + 1) + l;
    int i = l - 1, j = r + 1, x = q[pos];
    while (i < j)// 最后循环结束的时候i比j大，j指向的是q[pos]
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    int sl = j - l + 1; //左边一共有sl个数
    if(k <= sl) return quick_sort(l, j, k);
    return quick_sort(j + 1, r, k - sl);
    
}

int main() {
    int n;
    scanf("%d", &n);
    scanf("%d", &k);
    for(int i = 0;i < n;i++) {
        scanf("%d", &q[i]);
    }
    srand((unsigned)time(NULL));
    printf("%d", quick_sort(0, n - 1, k));
    
    
    return 0;
}

class Solution {
private:
    int quickselect(vector<int> &nums, int l, int r, int index) {
        int pos = randomPartition(nums, l, r);//这里这个函数的功能是：让返回的pos值前面都比pos小，后面的值都比pos大
        if(pos == index) {//这里相当于剪枝，
        //每一次循环都能保证pos处的值就是排序完整后这个位置上应该的值
        //如果index比pos小，就直接不管比pos大的部分了
            return nums[pos];
        }
        else if(pos < index) {
            return quickselect(nums, pos + 1, r, index);
        }
        else {
            return quickselect(nums, l, pos - 1, index);
        }

    }
    int randomPartition(vector<int> &nums, int l, int r) {
        int q = rand() % (r - l + 1) + l;
        swap(nums[q], nums[r]);//选中一个值当r，如果不随机，就直接到partition
        return partition(nums, l, r);

    }
    int partition(vector<int> &nums, int l, int r){
        int x = nums[r];
        int i = l - 1;//i指向的值永远比x小，所以每次找到了比x小的值才会i++
        for(int n = l;n < r;n++) {//因为r是x值的位置，所以不要循环到r
            if(nums[n] < x) {
                i++;
                swap(nums[i], nums[n]);
            }
        }
        swap(nums[i + 1], nums[r]);//最后记得把x值换过来
        return i + 1;//返回对比的中间值的位置，中间值左边的数都比它小，右边的值都比它大
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned)time(NULL));
        return quickselect(nums, 0, nums.size() - 1, nums.size() - k );
    }
};