Leetcode刷题记录——排序

• 通过递归不断地将数组分为两半，直至分割后数组的左右边界相等，即数组中只有一个元素。进而将左右两半部分排序后合并，return后重复此操作，直至排序完成。

class Solution {
public:
    vector sortArray(vector& nums) {
        mergesort(nums,0,nums.size()-1);
        return nums;
    }
    void merge(vector& nums,int l1,int r1,int l2,int r2)
    {
        int i=l1,j=l2,n=r1-l1+1+r2-l2+1,k=0;
        vectortemp(n);
        while(i<=r1&&j<=r2)
        {
            if(nums[i]
            nums[l1+i]=temp[i];
        }
    }
    void mergesort(vector& nums,int left,int right)
    {
        if(left==right) return;
        int mid=left+(right-left)/2;
        mergesort(nums,left,mid);
        mergesort(nums,mid+1,right);
        merge(nums,left,mid,mid+1,right);
    }
};

排序时将两半部分中的最小元素依次放入中间数组中，完成排序后替换原数组

• 只是把数组换成了链表，思路相同，将K个链表排序问题转化为合并两个有序链表。

class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        if(lists.size()==0) return nullptr;
        return mergelists(lists,0,lists.size()-1);
    }
    ListNode* merge(ListNode* l1,ListNode* l2)
    {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->valval)
        {
            l1->next=merge(l1->next,l2);
            return l1;
        }
        else
        {
            l2->next=merge(l1,l2->next);
            return l2;
        }
    }
    ListNode* mergelists(vector& lists,int left,int right)
    {
        if(left==right) return lists[left];
        int mid=left+(right-left)/2;
        ListNode* l1=mergelists(lists,left,mid);
        ListNode* l2=mergelists(lists,mid+1,right);
        return merge(l1,l2);
    }
};

• 在数组中指定一个基准，先从右向左搜索，元素比基准值大则继续向左搜索，比基准值小则将该元素放到左边；然后从左向右搜索，元素比基准值小则继续向右搜索，比基准值大则将该元素放到右边；重复以上操作直至左右指针相遇，则该位置为基准位置，将基准值赋给当前位置。接着对基准左右两部分继续进行上述操作，完成快速排序。

class Solution {
public:
    vector sortArray(vector& nums) {
        quick_sort(nums,0,nums.size()-1);
        return nums;
    }
    void quick_sort(vector& nums,int left,int right)
    {
        if(left>=right) return;
        int i=left,j=right;
        int pivot=rand()%(right-left+1)+left;
        swap(nums[left],nums[pivot]);
        pivot=nums[left];
        while(left
            while(left=pivot) right--;
            nums[left]=nums[right];
            while(left 
基准值随机在数组中选择以降低时间复杂度
 
数组中的第K个最大元素： 
在快速排序时判断所要查找的元素在基准的左侧还是右侧，只对该侧递归排序即可。
 
 
class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        int left=0,right=nums.size()-1;
        quick_sort(nums,left,right,k);
        return nums[right-k+1];
    }
    void quick_sort(vector& nums,int left,int right,int k)
    {
        if(left>=right) return;
        int i=left,j=right;
        int pivot=rand()%(right-left+1)+left;
        swap(nums[left],nums[pivot]);
        pivot=nums[left];
        while(left
            while(left=pivot) right--;
            nums[left]=nums[right];
            while(leftnums.size()-k) quick_sort(nums,i,left-1,k);
        else if(left 
若基准位置大于第K大元素的位置，则该元素在基准的左边，递归排序左边数组即可；基准位置小于第K大元素的位置同理可得只递归排序右边数组即可；若基准位置等于第K大元素的位置，则基准值即为所需元素，直接返回。