排序算法总结

时间:2024-03-07 09:58:41
  • 归并排序是一个基于分治的算法。
  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
  • 原问题:把数组排序。
  • 子问题:把数组前一半、后一半分别排序,然后再合并左右两半(两个有序数组)就可以了。
    void mergeSort(vector<int>& arr, int l, int r) {
    	if (l >= r) return;
    	int mid = (l + r) >> 1;
    	mergeSort(arr, l, mid);
    	mergeSort(arr, mid + 1, r);
    	return merge(arr, l, mid, r);
    }
    void merge(vector<int>& arr, int left, int mid, int right) {
    	vector<int> tmp = vector<int>(right - left + 1); // 临时数组
    	int i = left, j = mid + 1;
    	for(int k = 0;k < tmp.size();k++) {
    		if (j > right || (i <= mid && arr[i] <= arr[j])) { // 合并两个有序数组
    			tmp[k] = arr[i++];
    		} else {
    			tmp[k] = arr[j++];
    		}
    	}
    	
    	for (int k = 0;k < tmp.size();k++) { // 拷贝回原数组
           	arr[left + k] = tmp[k];
        }
    }