排序算法

一、排序算法总结

排序算法题目

• 排序算法
  • 快速排序
  • 堆排序
  • 归并排序
• 应用
  • 最小K个数（TopK问题）
  • 215.数组中的第K个最大元素
  • 把数组排成最小的数
  • 排序链表
  • 查找数组中出现次数超过一半的数（快排 or 投票法）
  • 数组中的逆序对

1.1 排序的分类

1.内排序：数据全部存放在内存中进行排序的过程。

（1）插入类：直接插入排序、希尔排序。
（2）交换类：冒泡排序、快速排序。
（3）选择类：简单选择排序、堆排序。
（4）归并类：归并排序方法。
（5）分配类：基数排序。

2.外排序：数据量太大，以致内存一次不能容纳下全部数据，在排序过程中需要对外存进行访问的排序过程。

1.2 算法复杂度

1.3 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

二、排序算法题目

快速排序

思路：
 1.选择轴点元素（pivot）
    - 通常是第一个元素
 2.使用pivot将序列分割成两个子序列
    - 将小于pivot的元素放在pivot的左侧
    - 将大于pivot的元素放在pivot的右侧
    - 等于pivot的元素在哪边都可以
 3.对pivot左右序列进行1、2操作。
    - 直到不能再分割，即子序列只剩下一个元素。

int partition(vector<int>& arr, int l, int r){
    int key = arr[l];
    while (l < r) {
        while (l < r && arr[r] >= key) r--;
        arr[l] = arr[r];
        
        while (l<r && arr[l] <= key) l++;
        arr[r] = arr[l];
    }
    arr[l] = key;
    return l;
}

void qSort(vector<int>& arr, int low, int high){
    if (low >= high) return;
    
    int idx = partition(arr, low, high);
    qSort(arr, low, idx-1);
    qSort(arr, idx+1, high);
}

void quickSort(vector<int>& arr){
    qSort(arr, 0, arr.size()-1);
}

堆排序

堆调整子函数：将左右节点较大的调整到父节点；如果发生调整，递归继续调整。
堆排序：
1.首先建初堆：从第一个非叶子节点到根节点依次进行堆调整。
2.堆排序：将根节点依次和最后一个节点交换，并对0到idx-1进行堆调整；直到没有节点可以交换。

void headAdjust(vector<int>& arr, int start, int end){
    int left = 2 * start + 1;
    int right = 2 * start + 2;
    int maxIdx = start;
    
    if (left<=end && arr[left] > arr[maxIdx]) maxIdx = left;
    if (right<=end && arr[right] > arr[maxIdx]) maxIdx = right;
    
    if (maxIdx != start) {
        swap(arr[start], arr[maxIdx]);
        headAdjust(arr, maxIdx, end);
    }
}

void headSort(vector<int>& arr){
    // 建初堆
    for (int i = arr.size()/2-1; i>=0; i--) {
        headAdjust(arr, i, arr.size()-1);
    }
    // 堆排序
    for (int i = arr.size()-1; i>0; i--) {
        swap(arr[0], arr[i]);
        headAdjust(arr, 0, i-1);
    }
}

归并排序

分而治之：

1.分：

• 计算索引mid，将数组分为两部分；
• 递归分左边和右边，直到数组元素在low、high区间的元素为1。

2.治：创建一个临时数组，存放mid两边排序的结果；最后再放回到原数组中。

void merge(vector<int>& arr, int low, int mid, int high){
    vector<int> temp(high - low + 1,0);

    int i = low,j = mid+1, k = 0;
    while (i<=mid && j<=high) {
        if (arr[i] < arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i<=mid) temp[k++] = arr[i++];
    while (j<=high) temp[k++] = arr[j++];

    // 放到原数组里面
    for (int i=low, j=0; i<=high; i++, j++) {
        arr[i] = temp[j];
    }
}

void mSort(vector<int>& arr, int low, int high){
    if (low == high) return ;
    
    int mid = (low + high) / 2;
    mSort(arr, low, mid);
    mSort(arr, mid+1, high);
    
    merge(arr, low, mid, high);
}

void mergeSort(vector<int>& arr){
    mSort(arr, 0, arr.size()-1);
}

数组中的第K个最大元素

思路：使用快排中partation逐渐逼近

int partation(vector<int>& nums, int low, int high){
    int pivot = nums[low];
    
    while (low < high) {
        while (low < high && nums[high]>=pivot) high--;
        nums[low] = nums[high];
        while (low < high && nums[low]<=pivot) low++;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}

int findKthLargest(vector<int>& nums, int k) {
    int low = 0, high = nums.size()-1;
    int idx = partation(nums, low, high);
    int keyIdx = nums.size() - k;
    while (idx != keyIdx) {
        if (idx > keyIdx) {
            idx = partation(nums, low, idx-1);
        }else if(idx < keyIdx){
            idx = partation(nums, idx+1, high);
        }
    }
    return nums[idx];
}

最小K个数

思路：堆排序

先用前k个数建立大根堆；
然后遍历k以后的数与堆顶比较，如果比堆顶小则替换堆顶，然后调整堆。

void heapAdjust(vector<int>& arr, int start, int end){
    int maxIdx = start;
    int l = 2 * maxIdx + 1;
    int r = 2 * maxIdx + 2;
    
    if (l <= end && arr[l]>arr[maxIdx]) maxIdx = l;
    if (r <= end && arr[r]>arr[maxIdx]) maxIdx = r;
    
    if (maxIdx != start) {
        swap(arr[start], arr[maxIdx]);
        heapAdjust(arr, maxIdx, end);
    }
}
void buildHeap(vector<int>& arr, int k){
    for (int i= k/2-1; i>=0; i--) 
        heapAdjust(arr, i, k-1);
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
    if (k == 0) return vector<int>();
    
    vector<int> res(k, 0);
    for (int i=0; i<k; i++)
        res[i] = arr[i];
    buildHeap(res, k);
    for (int i=k; i<arr.size(); i++) {
        if (arr[i] < res[0]) {
            res[0] = arr[i];
            heapAdjust(res, 0, k-1);
        }
    }
    return res;
}

排序链表

方法1： 归并排序

1.分：

• 通过快慢指针找到mid指针，断开连接，将链表分为两部分；
• 递归分左边和右边，直到表内元素只有1个。

2.治：合并两个链表。

Node* merge(Node* head1, Node* head2){
    Node* dummy = new Node(-1);
    Node* cur = dummy;
    while (head1 && head2) {
        if (head1->val < head2->val) {
            cur->next = head1;
            cur = cur->next;
            head1 = head1->next;
        }else{
            cur->next = head2;
            cur = cur->next;
            head2 = head2->next;
        }
    }
    if (head1) cur->next = head1;
    if (head2) cur->next = head2;
    return dummy->next;
}

Node* sortList(Node* head){
    if (!head || !head->next) return head;
    
    Node* slow = head;
    Node* fast = head->next;
    
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node* head2 = slow->next;
    slow->next = NULL;
    
    Node* p1 = sortList(head);
    Node* p2 = sortList(head2);
    return merge(p1, p2);
}

方法2：快速排序

partition子函数：从head到tail遍历链表，创建两个临时链表，存放比pivot小的节点和比pivot大的节点。然后将两个临时链表和pivot连接到原链表起来。
先从右向左找到比key小的数，放到左边；再从左往右找到比key大的数，放到右边；直到索引l>=r，把key放到索引指向的位置.

快排：...递归对索引两边排序；直到low>=high。

Node* partation(Node* head, Node* tail){
    Node* pivot = head->next; // 枢轴
    
    // 保存比privot小的节点
    Node* leftHead = new Node(-1);
    Node* lh = leftHead;
    // 保存比pivot大的节点
    Node* rightHead = new Node(-1);
    Node* rh = rightHead;
    
    for (Node* p = pivot->next; p!=tail; p = p->next) {
        if (p->val < pivot->val) {
            lh->next = p;
            lh = lh->next;
        }else{
            rh->next = p;
            rh = rh->next;
        }
    }
    
    // 连接前后
    // 顺序！注意lh和leftHead rh和rightHead的相对顺序！
    lh->next = pivot;
    rh->next = tail;
    head->next = leftHead->next;
    pivot->next = rightHead->next;
    
    return pivot;
}

void qSort(Node* head, Node* tail){
    if (head->next == tail || head->next->next == tail)
        return;
    
    Node* pivot = partation(head, tail);
    qSort(head, pivot);
    qSort(pivot, tail);
}

Node* sortList(Node* head){
    if(!head || !head->next) return head;
    
    // 添加头节点！
    Node* newHead = new Node(-1);
    newHead->next = head;
    qSort(newHead, NULL);
    return newHead->next;
}

数组中的逆序对

int count = 0;
void merge(int*arr, int left, int mid, int right){
    int *temp = (int *)malloc((right-left+1) * sizeof(int)); // 临时区

    int i=left, j=mid+1, k=0;
    while (i<=mid && j<=right) {
        if (arr[i] <= arr[j]){
            temp[k++] = arr[i++];
        }
        else{
            temp[k++] = arr[j++];
            count += mid - i + 1; // 增加一行代码
        }
    }
    while (i<=mid) temp[k++] = arr[i++];
    while (j<=right) temp[k++] = arr[j++];

    //将临时区域中排序后的元素，整合到原数组中
    for (int i=0; i<k; i++) {
        arr[left+i] = temp[i];
    }
    free(temp);
}


void mergeSort(int* arr, int start, int end){
    // 递归结束条件
    if (start >= end) return;

    int mid = (start + end) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid+1, end);

    merge(arr, start, mid, end);
}

int reversePairs(int* nums, int numsSize){
    mergeSort(nums, 0, numsSize-1);
    return count;
}

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

思路：先把字符串数组排序一下，然后拼接到一起。

这个排序使用的匿名函数值得学习。

string minNumber(vector<int>& nums) {
    vector<string>strs;
    string ans;
    for(int i = 0; i < nums.size(); i ++){
        strs.push_back(to_string(nums[i]));
    }
    auto cmp = [](string s1, string s2){
        return s1+s2 < s2+s1;
    };
    sort(strs.begin(), strs.end(), cmp);
    for(int i = 0; i < strs.size(); i ++)
        ans += strs[i];
    return ans;
}

出现次数超过一半的数

方法1：快排
找出作为为中间的元素，即为出现次数超过一半的数。

int partition(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 majorityElement(vector<int>& nums) {
    int low = 0, high = nums.size()-1;
    int middle = nums.size() / 2;
    int idx = partition(nums, low, high);
    while (idx != middle) {
        if (idx > middle) {
            high = idx - 1;
        }else{
            low = idx + 1 ;
        }
        idx = partition(nums, low, high);
    }

    return nums[idx];
}

方法2：投票法
用两个变量记录当前标记元素和它出现的次数。

• 如果出现新的元素，它的次数减1；
• 如果次数为0，更换当前标记元素；
  因为出现次数超过一半的数，所以遍历到最后可以得到要求的元素。

int majorityElement(vector<int>& nums) {
    int value = nums[0];
    int count = 1;
    for (int i=1; i<nums.size(); i++) {
        if (nums[i] == value) {
            count++;
        }else{
            count--;
            if (count==0) {
                value = nums[i];
                count = 1;
            }
        }
    }
    return value;
}