Algorithms: Sort

2 minute read

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

融合数组的重复部分。1. 对数组进行排序。 2. 依次判断结果数组中最后一个间隔的重叠情况。

vector<Interval> merge(vector<Interval>& intervals) {
    std::sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
    
    vector<Interval> res;
    if (intervals.empty()) return res;
    res.push_back(intervals[0]);
    for (int i = 1; i < intervals.size(); ++i) {
        Interval cur = intervals[i];
        Interval last = res.back();
        if (cur.start <= last.end) {
            res[res.size() - 1].end = max(cur.end, last.end);
        } else {
            res.push_back(cur);
        }
    }
    return res;
}

147. Insertion Sort List

  • 对链表使用插入排序。使用指针preHead指向拍好序的链表,head指向未排序的链表,指针pt是拍好序的链表的游标,当head->val 小于等于 pt->next->val时,pt向前移动。pt在 pt -> next == NULL时,插在末尾;在另一种结束情况,代表head节点插入到小于 pt -> next -> val的pt和pt->next之间。
  • 时间复杂度:$O(n^2)$
ListNode* insertionSortList(ListNode* head) {
     ListNode preHead = ListNode(INT_MIN);
     while (head) {
         ListNode *pt = &preHead;
         while (pt -> next &&  pt -> next ->val <= head->val) {
             pt = pt -> next;
         }
         
         ListNode *next = head -> next;
         head -> next = pt -> next;
         pt -> next = head;
         head = next;
     }
     return preHead.next;
}

148. Sort List

  • 解析: 时间复杂度$O(n\log n)$,空间复杂度$O(1)$, 实现链表排序(归并、快排)
  • 边界:链表为空或链表只有1个节点
  • 思路:对一段列表划分成两段,分别对这两段进行排序,再对排好序的链表进行合并。 实际上,使用递归实现的归并排序空间复杂度为$O(\log n)$,递归工作栈大小应该为$O(\log n)$

归并方法

  • merge函数,常用的两个排好序的链表融合,别忘了cur 往下走。
  • 递归的结束条件:链表为空或链表长度为1,代表了最底层的返回值。
  • 使用快慢指针对链表进行划分。
  • 分别对两段调用递归排序,并合并。
  • 时间复杂度:$O(n\log n)$
// 归并,使用分治思想,这个实现一定要熟悉
ListNode* mergeLists(ListNode *left, ListNode *right) {
    ListNode preHead = ListNode(INT_MIN);
    ListNode *cur = &preHead;
    while (left && right) {
        if (left->val < right->val) {
            cur -> next = left;
            left = left -> next;
        } else {
            cur -> next = right;
            right = right -> next;
        }
        cur = cur -> next;
    }

    cur -> next = left?left:right;
    return preHead.next;
}

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode preHead = ListNode(INT_MIN);
    preHead.next = head;
    ListNode *preMid = &preHead, *mid = head;
    while (head && head -> next) {
        preMid = mid;
        mid = mid -> next;
        head = head -> next -> next;
    }

    preMid -> next = NULL;

    return mergeLists(sortList(preHead.next),sortList(mid));
}

快排(此处给的是基于数组的,链表实现比较复杂)

  • 思路:partition:对给定数组取基准元素,比它大的放它右边,比它小的放它左边。然后再将数组按返回的基准元素的位置进行划分,递归进行。
  • 移动元素技巧性比较强
  • 时间复杂度:$O(n\log n)$
int partition(int a[], int low, int high)  
{  
    int privotKey = a[low];                             //基准元素  
    while(low < high){                                   //从表的两端交替地向中间扫描  
        while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端  
        swap(&a[low], &a[high]);  
        while(low < high  && a[low] <= privotKey ) ++low;  
        swap(&a[low], &a[high]);  
    }  
    print(a,10);  
    return low;  
}  
  
  
void quickSort(int a[], int low, int high){  
    if(low < high){  
        int privotLoc = partition(a,  low,  high);  //将表一分为二  
        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
    }  
}