leetcode刷题笔记（二） 排序篇

0. 理论

这一部分给出常见算法的模板及其性质（复杂度，稳定性 etc.).

0.1 快速排序

快排的思想是divide and conquer, 通过一个Pivot元素将数组划分为两半，其中前一半小于pivot，后一半大于Pivot。然后在每个子数组中再执行相同步骤直到子数组不可再划分。

最坏时间复杂度：O(n^2), 最好/平均时间复杂度：O(NlogN) 稳定性：不稳定

给一个模板

void quick_sort(vector<int> &nums, int l, int r) {
    if (l + 1 >= r) {
    	return;
    }
    int first = l, last = r - 1, key = nums[first];
    while (first < last){
        while(first < last && nums[last] >= key) 
        {
            --last;
    	}
        nums[first] = nums[last];
        while (first < last && nums[first] <= key) 
        {
        	++first;
        }
    	nums[last] = nums[first];
    }
    nums[first] = key;
    quick_sort(nums, l, first);
    quick_sort(nums, first + 1, r);
}

quick_sort(nums,0,nums.size()) ;//调用方法

0.2 归并排序

归并排序的思想也是divide and conquer, 通过不断地将有序的子数组合并为更大的有序数组从而得到结果。

最坏/最佳复杂度：O(NlogN) 稳定性：稳定

注意一般来说我们写的都不是in place merge sort, 即一般都会传给函数一个额外的空间用于作数组合并，但也有in place的版本，在此不作赘述。

给一个模板

void merge_sort(vector<int> &nums, int l, int r, vector<int> &temp) {
    if (l + 1 >= r) {
    	return;
    }
    // divide
    int m = l + (r - l) / 2;
    merge_sort(nums, l, m, temp);
    merge_sort(nums, m, r, temp);
    // conquer
    int p = l, q = m, i = l;
    while (p < m || q < r) 
    {
        if (q >= r || (p < m && nums[p] <= nums[q])) 
        {
        	temp[i++] = nums[p++];
    	} 
    	else 
    	{
    		temp[i++] = nums[q++];
    	}
    }
    for (i = l; i < r; ++i) {
    	nums[i] = temp[i];
    }
}

merge_sort(nums,0,nums.size(),temp);// 调用方法

0.3 插入排序

插入排序很简单，但时间久了忘记了，写一下吧。

插入排序的思想是使得有序的数组长度逐渐扩大，假设我们起初认为只有第一个元素是有序的，那么遍历到第二个元素时，检查第二个元素和第一个元素的大小关系，若第二个元素更大则将其插到第一个元素的前面，这样，我们就得到长度为2的有序序列了，以此类推，不断地将第n个元素插入到长度为n-1地有序数组中, 直到n=len(nums)。

最坏/平均时间复杂度: O(N^2) 最好时间复杂度: O(N) 稳定性: 稳定