C++ 六大排序算法实现和比较

浅浅的花香味﹌ 2022-09-06 10:27 150阅读 0赞

### 文章目录 ###

*  一. 快速排序
 *   *  1.1 介绍
     *  1.2 函数片段
     *  1.3 快排应用
 *  二. 归并排序
 *   *  2.1 介绍
     *  2.2 函数片段
 *  三. 插入排序
 *   *  3.1 介绍
     *  3.2 函数片段
 *  四. 冒泡排序
 *   *  4.1 介绍
     *  4.2 函数片段
 *  五. 选择排序
 *   *  5.1 介绍
     *  5.2 函数片段
 *  六. 桶排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]

**错误提示:** 快排的空间复杂度是O(1), 因为在原始位置进行置换, 不需要用到快排, 这里感谢字节小姐姐的纠错, 果然是大厂的工程师, 一眼就能看出问题, 差点误人子弟, 在这里给所有人道歉.

[常用的排序算法][Link 1]

*  **本文介绍多种排序算法, 利用图示进行解析**
 *  最后部分是整个可执行 带 主 函 数 的 代 码 \\color\{\#FF3030\}\{带主函数的代码\} 带主函数的代码

# 一. 快速排序 #

## 1.1 介绍 ##

*  快速排序是一种查找一个值的绝对位置, 根据此位置将序列分成左右两个位置  
    是一个分而治之的思路, 先解决一个点, 以此扩散, 具体介绍跟代码见下文;
 *  快排的优点是速度快O(logn), 占用空间小O(1), algorithm里面的sort()函数使用的就是快排

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 1]

## 1.2 函数片段 ##

/** * v =[5,3,4,6,2,4,64] * key=5, last从64向左, 直到遇到小于5的4, */
    // 快排 
    // 找到low的绝对位置, 并把比nums[low]大的都放到low右侧, 比其小的都放到low左侧
    // 最后while最后的结果是nums[low] = val, 此时的low指向的是val的绝对位置
    int find_fixed_low(vector<int> &nums, int low, int high){ 
    	int val = nums[low];
    	while (low < high){ 
    		while(low<high && val<=nums[high]) high--;
    		nums[low] = nums[high];
    		while(low<high && nums[low]<=val) low++;
    		nums[high] = nums[low];
    	}
    	nums[low] = val;
    	return low;	
    }
    
    void quickSort(vector<int> &nums, int low, int high){ 
    	if(low < high){ 
    		int pos = find_fixed_low(nums, low, high);
    		quickSort(nums, low, pos-1);
    		quickSort(nums, pos+1, high);
    	}
    }
    
    void quickSort2(vector<int>& nums, int low, int high){ 
    	int val = nums[low]; // 保存中间数
    	if(low<high){ 
    		int l=low, h=high;
    		while(low < high){ 
    			while(low<high && val<=nums[high]) high--;
    			nums[low] = nums[high];
    			while(low<high && nums[low]<=val) low++;
    			nums[high] = nums[low];
    		}
    		nums[low] = val; // 这里的low已经属于中间位置了
    		quickSort2(nums, l, low-1);
    		quickSort2(nums, low+1, h);
    	}
    }

## 1.3 快排应用 ##

[215-数组中的第K个最大元素][215-_K]

> 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

> 输入: \[3,2,1,5,6,4\] 和 k = 2  
> 输出: 5

利用快速选择, 确定左值的绝对位置, 比较目标位置, 一次选择

// 找到val的绝对位置, 并且返回val的绝对位置, 同时将val的左右进行分类
    int quickSelection(vector<int>& nums, int low, int high){ 
        int l=low, h=high;
        int val = nums[low];
        while(low<high){  
            while(low<high && val<=nums[high]) high--;
            nums[low] = nums[high];
            while(low<high && nums[low]<=val) low++;
            nums[high] = nums[low];
        }
        nums[low] = val;
        return low;
    }
    
    // 找出第K大的值
    int findKthLargest(vector<int>& nums, int k) { 
        if(nums.size() < k) return -1;
        int n=nums.size(); 
        int destination = n-k;
        int low=0, high=n-1;
        while(true){ 
            int mid = quickSelection(nums, low, high);
            if(mid == destination) return nums[mid];
            else if(mid < destination) low = mid+1;
            else high = mid-1;  
        }
    }

[第二种解法是堆排序, 利用优先队列解题][Link 2]

# 二. 归并排序 #

## 2.1 介绍 ##

*  正经的分为知之的经典算法, 先将待排序序列打散成小数组, 每个小数组排序完在一层层排序
 *  用到了归并有序数组的方式
 *  速度快, 与快排一样, 对于树形结构的排序一般都很快  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 2]

## 2.2 函数片段 ##

void merge_sort(vector<int> &nums, int low, int high, vector<int> &temp){ 
        if(low < high){ 
            int mid = (low+high)/2;
            merge_sort(nums, low, mid, temp);
            merge_sort(nums, mid+1, high, temp);
    
            // 之类low-mid, mid+1~high 两个list已经排序好了
            int l=low, h=mid+1;
            int t=low; // t=0;
            while(l<=mid && h<=high){ 
                temp[t++] = nums[l] < nums[h] ? nums[l++] : nums[h++];
            }
            while(l<=mid) temp[t++] = nums[l++];
            while(h<=high) temp[t++] = nums[h++];
    
            for(int i=low; i<=high; i++){ 
                nums[i] = temp[i];
            }
            // for(int i=0; i<t; i++){ 
            // nums[low+i] = temp[i];
            // }
        }
    }
    
    vector<int> sortArray(vector<int> &nums) { 
        vector<int> ans(nums.size());
        merge_sort(nums, 0, nums.size()-1, ans);
        return nums; 
        // return ans; // 注意这里如果返回ans, 也不能把merge_sort最后的for赋值给注释掉
    }

# 三. 插入排序 #

## 3.1 介绍 ##

*  插入排序的特点是: 每次都是将当前值向前翻滚, 直到滚到相对排序位置停止,
 *  比如1,3,4,2, 这个2向前滚动就是先跟4交换, 再跟3交换, 然后跑到1后面;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 3]

## 3.2 函数片段 ##

// 插入排序, 正序遍历值, 反向翻滚向前面插入
    void insertSort(vector<int> & nums, int low, int high){ 
    	for(int i=low; i<high; i++){ 
    		for(int j=i+1; j>low; j--){ 
    			// printf("%d, %d\n", j-1, j);
    			if(nums[j-1] > nums[j]) swap(nums[j-1], nums[j]);
    		}
    		cout<<endl;
    	}
    }

# 四. 冒泡排序 #

## 4.1 介绍 ##

*  冒泡排序的关键在于每次都是将最大的值向前翻滚, 就像一只小泡泡, 向上升的过程中越来越大, 直到最大

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 4]

## 4.2 函数片段 ##

// 冒泡排序, 正序遍历值, 起点都在low, 每次将最大翻滚放到最后
    void bubbleSort(vector<int> &nums, int low, int high){ 
    	bool noChange;
    	for(int i=low; i<high; i++){ 
    		noChange=true;
    		for(int j=low+1; j<high-(i-low)+1; j++){ 
    			if(nums[j-1] > nums[j]) { 
    				noChange=false;
    				swap(nums[j-1], nums[j]);
    			}
    		}
    		if (noChange) break;
    	}
    }

# 五. 选择排序 #

## 5.1 介绍 ##

*  选择排序:是索引的变化,也就是根据比较, 找到最小值得索引, 然后将最小值拉到第一位  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 5]

## 5.2 函数片段 ##

// 选择排序, 找到该值的应该所在的位置, 放到对应位置
    // 正序遍历值, 将nums[i]拿出来, 与i+1,high比较, 得到i对应的绝对位置
    void selectSort(vector<int>&nums, int low, int high){ 
    	int mid;
    	for(int i=low; i<high; i++){  // low, high-1
    		mid=i;
    		for(int j=i+1; j<=high; j++){   //i+1, high 
    			if(nums[j] < nums[mid]) mid = j; //mid等于小的, 这样遍历一遍后, 将最小值给第一位
    		}
    		swap(nums[mid], nums[i]);
    	}
    }

# 六. 桶排序 #

桶排序的思路就是根据数据的范围创建木桶, 比如统计数据, 数据都在1-10之间, 则创建1-10的木桶, 遍历数据放入对应的木桶即可  
![在这里插入图片描述][20210206181217734.png]  
[347. 前 K 个高频元素][347. _ K]

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

> 输入: nums = \[1,1,1,2,2,3\], k = 2  
> 输出: \[1,2\]

首先利用无序hash map进行数值频率统计, 然后再用数组按照频率统计, 在从头遍历 `buckets[频率].push_back(值);`

// 利用桶排序, 每个值对应一个桶, 记录这个值出现的次数,
    vector<int> topKFrequent(vector<int>& nums, int k) { 
        unordered_map<int ,int> counts; // 记录数字出现的频率
        int max_count = 0; // 记录最大的频率
        for(const auto &num: nums){ 
            counts[num]++;
            max_count = max(max_count, counts[num]);
        }
    
        vector<vector<int>> buckets(max_count+1);  // 桶(一种频率一个桶)
        for(const auto&p: counts){ 
            buckets[p.second].push_back(p.first);  // 将相同频率的值装入到桶中
        }
    
        vector<int>ans;
        for(int i=max_count; i>=0; i--){  // 从最宽的桶开始遍历, 到k个结束
            for(const auto& num: buckets[i]){  
                ans.push_back(num);
                int b = ans.size();
                if(ans.size() == k){ 
                    return ans; // 这里不能使用break, 因为这是两层for
                }
            }
        }
        return ans;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]: /images/20220829/2b492a1ab4e94d25bae952554efc9e9c.png
[Link 1]: https://leetcode-cn.com/problems/sort-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 1]: /images/20220829/0ef62183b6994f1194ca3b8f49f9df60.png
[215-_K]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[Link 2]: https://blog.csdn.net/qq_32460819/article/details/117827146
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 2]: /images/20220829/f7e8dd5e33204164b9705221d6a79a1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 3]: /images/20220829/8b50156e3c0444498a1d97a829c9a37b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 4]: /images/20220829/659c1d34540c48a0b87bcde4c4813fb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 5]: /images/20220829/3ac08958c8c04af1ae8ae1034f5e5bec.png
[20210206181217734.png]: /images/20220829/03012f03876a402d912d7c5adba8320d.png
[347. _ K]: https://leetcode-cn.com/problems/top-k-frequent-elements/