Day23-排序-快排&堆排&归并排序
Day23-排序-快排&堆排&归并排序
一 鸽王回来了！
由于前段时间真的有点忙，鸽了大家一个礼拜多
然后，鸽王今天回来了，明天继续更图，今天小试牛刀一下
排序算法很基础，基础还是要打扎实~
像冒泡排序这种时间复杂度为O（N²）的渣渣排序算法就不更了
快排的平均时间复杂度，堆排和归并的时间复杂度都是O（nlog（n））
所以这仨都值得一写，也是面试的高频排序题
二 快排开始搞起来！
Q：实现快速排序
冷静分析一下快排的基本思想：（以最终升序为例）
1.取数组第一个元素，为基准值；
2.建立左右指针，分别指向第一个和最后一个元素；
3.在左指针 < 右指针 下进行循环：
右指针--，直到找到比基准值小的元素，将左右指针指向的元素进行交换；
左指针++，直到找到比基准值大的元素，将左右指针指向的元素进行交换；
4.此时初始数组的第一个元素，即我们刚才定义的基准值，已在其最终位置上，那么对该数左边的部分递归快排，对该数右边的部分递归快排；
//
// Created by renyi on 2019-07-26.
//
#include <iostream>
#include <vector>
using namespace std;
void printArray(vector<int> nums){
for (int i = 0; i < nums.size(); i++) {
printf("[%d]", nums[i]);
}
printf("\n");
}
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void quickSort(vector<int> &nums, int low, int high){
if (low >= high){
return;
}
int i = low;
int j = high;
int base = nums[i];
while (i < j){
while (i < j && nums[j] >= base){
j--;
}
swap(nums[i], nums[j]);
while (i < j && nums[i] <= base){
i++;
}
swap(nums[i], nums[j]);
}
quickSort(nums, low, i-1);
quickSort(nums, i+1, high);
}
int main(){
int temp[] = {7, 9, 5, 1, 2, 8, 6, 4, 0, 3, 10};
vector<int> result;
for (int i = 0; i < 11; i++) {
result.push_back(temp[i]);
}
printArray(result);
quickSort(result, 0, result.size()-1);
printArray(result);
return 0;
}三 堆排开始搞起来！
Q：实现堆排序
冷静分析：先知道堆排序要干什么（仍然以最终升序为例）
网上找个图
堆排序的思路就是：这是初始的堆，我们现在要构造一个大顶堆。然后将大顶堆的堆顶，即当前最大的元素和最后一个元素交换，即把最大的堆顶，放到了最后面。同时将堆可操作的长度-1，即后面的堆顶，放到了倒数第二个位置。同时需要实现一个函数，完成每次交换完两个元素之后，调整堆使其继续保持为大顶堆。
这是初始的堆
利用我们自己实现的函数，将初始堆，构造为大顶堆
这是最终构造好的大顶堆
然后开始堆排序，将堆顶80与最后一个元素40进行交换，此时80就在其最终位置上了，可操作长度-1。接下来利用我们自己实现的函数，调整堆，使其继续为大顶堆，那么此时大顶堆的堆顶一定是70，将堆顶70交换到了下标为7的位置，依次类推~
//
// Created by renyi on 2019-07-26.
//
#include <iostream>
#include <vector>
using namespace std;
void printArray(vector<int> nums){
for (int i = 0; i < nums.size(); i++) {
printf("[%d]", nums[i]);
}
printf("\n");
}
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void adjustHeap(vector<int>& nums, int parNode, int high){
int newParNode = parNode;
int j = 2 * parNode + 1;//取根节点的左孩子
while (j <= high){//如果j=high，说明没有右孩子，high就是左孩子
if (j < high && nums[j] <= nums[j+1]){
j += 1;//一个根节点下如果有两个孩子，将j指向更大的那个孩子
}
if (nums[j] >= nums[newParNode]){//如果j指向的孩子大于父节点，就交换
swap(nums[j], nums[newParNode]);
newParNode = j;
j = j * 2 + 1;
} else{
break;
}
}
}
void heapSort(vector<int>& nums){
int last = nums.size() - 1;
int lastParNode = nums.size() / 2 - 1;//最后一个父节点
while (lastParNode >= 0){
adjustHeap(nums, lastParNode, last);
lastParNode -= 1;//建立最大堆，是从后往前调整，每调整好一个节点，就从后往前移动一个节点
}
//上面的while循环结束之后，即建立起了一个最大堆
//接下来开始堆排序，精髓就是，交换头和尾，把最大的放最后面，再调整为最大堆，继续交换
while (last > 0){
swap(nums[0], nums[last]);
adjustHeap(nums, 0, last-1);//从前往后调整最大堆
last -= 1;
}
}
int main(){
int temp[] = {7, 9, 5, 1, 2, 8, 6, 4, 0, 3, 10};
vector<int> result;
for (int i = 0; i < 11; i++) {
result.push_back(temp[i]);
}
printArray(result);
heapSort(result);
printArray(result);
return 0;
}四 归并排序搞起来！
Q：实现归并排序
冷静分析：
归并排序也很经典，我就不画图了，大概讲一下思路：
归并排序的精髓：将大问题不断递归拆分为小问题，直到不能拆分为止，对最终拆分的一个个小部分进行排序&合并，然后一步一步向上回溯，最后一次是将两个有序数组合并为了一个有序数组，整体是递归&回溯的思想~
至于代码实现，就是讲原始数组，按下标一半进行拆分，然后将左边的数组递归拆分，将右边的数组递归拆分，直到不能拆分；此时进行回溯，即合并两个有序数组，一步一步向上回溯，最终合并两个大的有序数组~
个人认为归并排序的算法思路最精妙，也是本人最喜欢的排序算法
//
// Created by renyi on 2019-07-26.
//
#include <iostream>
#include <vector>
using namespace std;
void printArray(vector<int> nums){
for (int i = 0; i < nums.size(); i++) {
printf("[%d]", nums[i]);
}
printf("\n");
}
void mergeTwoSortedVector(vector<int>& vec1, vector<int>& vec2, vector<int>& vec){
int i = 0;//遍历vec1的下标
int j = 0;//遍历vec2的下标
while (i < vec1.size() && j < vec2.size()){
if (vec1[i] <= vec2[j]){
vec.push_back(vec1[i]);
i++;
} else{
vec.push_back(vec2[j]);
j++;
}
}
for (; i < vec1.size(); i++) {//谁更长，直接把剩余部分追加进去vec
vec.push_back(vec1[i]);
}
for (; j < vec2.size(); j++) {
vec.push_back(vec2[j]);
}
}
void mergeSort(vector<int>& vec){
if (vec.size() < 2){
return;
}
int mid = vec.size() / 2;
vector<int> vec1;
vector<int> vec2;
for (int i = 0; i < mid; i++) {
vec1.push_back(vec[i]);
}
for (int j = mid; j < vec.size(); j++) {
vec2.push_back(vec[j]);
}
mergeSort(vec1);
mergeSort(vec2);
vec.clear();
mergeTwoSortedVector(vec1, vec2, vec);
}
int main(){
int temp[] = {7, 9, 5, 1, 2, 8, 6, 4, 0, 3, 10};
vector<int> result;
for (int i = 0; i < 11; i++) {
result.push_back(temp[i]);
}
printArray(result);
mergeSort(result);
printArray(result);
return 0;
}这三份代码的运行结果皆一致，均为
