C++力扣Leetcode算法4--排序算法

目录

快速排序--递归

归并排序--递归

插入排序

冒泡排序

选择排序

215 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

347. 前 K 个高频元素

---

快速排序--递归

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);
}

归并排序--递归

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];
    }
}

插入排序

void insertion_sort(vector<int> &nums, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = i; j > 0 && nums[j] < nums[j-1]; --j) {
            swap(nums[j], nums[j-1]);
        }
    }
}

冒泡排序

void bubble_sort(vector<int> &nums, int n) {
    bool swapped;
    for (int i = 1; i < n; ++i) {
        swapped = false;
        for (int j = 1; j < n - i + 1; ++j) {
            if (nums[j] < nums[j-1]) {
                swap(nums[j], nums[j-1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

选择排序

void selection_sort(vector<int> &nums, int n) {
    int mid;
    for (int i = 0; i < n - 1; ++i) {
        mid = i;
        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[mid]) {
                mid = j;
            }
        }
        swap(nums[mid], nums[i]);
    }
}

排序调用方法

void sort() {
    vector<int> nums = {1,3,5,7,2,6,4,8,9,2,8,7,6,0,3,5,9,4,1,0};
    vector<int> temp(nums.size());
    sort(nums.begin(), nums.end());
    quick_sort(nums, 0, nums.size());
    merge_sort(nums, 0, nums.size(), temp);
    insertion_sort(nums, nums.size());
    bubble_sort(nums, nums.size());
    selection_sort(nums, nums.size());
}

215 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

书中最优解

int pointers::findKthLargest(vector<int>& nums, int k)
{
	int l = 0, r = nums.size() - 1, target = nums.size() - k;
	while (l < r) {
		int mid = quickSelection(nums, l, r);
		if (mid == target) {
			return nums[mid];
		}
		if (mid < target) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	return nums[l];
}
 
// 辅函数 - 快速选择
int quickSelection(vector<int>& nums, int l, int r) {
	int i = l + 1, j = r;
	while (true) {
		while (i < r && nums[i] <= nums[l]) {
			++i;
		}
		while (l < j && nums[j] >= nums[l]) {
			--j;
		}
		if (i >= j) {
			break;
		}
		swap(nums[i], nums[j]);
	}
	swap(nums[l], nums[j]);
	return j;
}

本人写，提交超出时间限制

int pointers::findKthLargest(vector<int>& nums, int k)
{
	int len = nums.size();
	for (int i = 0; i < len; ++i) {
		for (int j = i; j >0 && nums[j]<nums[j-1]; --j) {
			swap(nums[j], nums[j - 1]);
		}
	}
 
	return nums[len-k];
}

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。

解：桶排序

书中最优解

vector<int> pointers::topKFrequent(vector<int>& nums, int k)
{
	unordered_map<int, int> counts;
	/*unordered_map容器用来存储键值对，其中键为int型，值为int型，
	可以用counts[key]++方式增加某个键的值，如果键不存在，会自动插一个新的键值对，值为0
	由于unordered_map不允许存储具有重复键的元素，因此count()函数本质上检查unordered_map中是否存在具有给定键的元素。
	*/
	int max_count = 0;
	//统计每个元素出现的次数，实现数：频率
	for (const int& num : nums) {
		max_count = max(max_count, ++counts[num]);
	}
	vector<vector<int>> buckets(max_count + 1);  //行数max_count + 1
	//将次数为i的元素放入i桶中，实现频率：数，通过键值相互交换达到value排序的目的，这种写法更符合C++
	for (const auto& p : counts) {
		buckets[p.second].push_back(p.first);
	}
	vector<int> ans;
	for (int i = max_count; i >= 0 && ans.size() < k; --i) {
		for (const int& num : buckets[i]) {
			ans.push_back(num);
			if (ans.size() == k) {
				break;
			}
		}
	}
	return ans;
	
}

学习：leetcode-347. 前K个高频元素 - ggaoda - 博客园 (cnblogs.com)