|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 糖逗 于 2020-5-14 14:58 编辑
一、冒泡排序
参考视频：https://www.bilibili.com/video/av26394341?p=6
n代表待排序的元素个数
时间复杂度：最好情况O(n）、最坏情况O(n^2)、平均情况O(n^2)
空间复杂度:O(1)
稳定性：稳定
属于内排序
代码实现：#include <iostream>
#include <vector>
using namespace std;
void quick_sort(vector<int>& input){
int len = input.size();
for(int i = 0; i < len; i++){//i是辅助
for(int j = 1; j < len - i; j++){
if(input[j-1] > input[j]){
swap(input[j-1], input[j]);
}
}
}
}
int main(void){
vector<int> temp;
int number;
while(cin >> number){
temp.push_back(number);
}
quick_sort(temp);
for(auto cha : temp) cout << cha << " ";
return 0;
}
注意事项：
1.参考链接：https://mp.weixin.qq.com/s/KWf_1Ntbo3WM52JWkP70Cg
2.稳定性和内外排序的定义参考《大话数据结构》第九章
二、选择排序
参考视频：https://www.bilibili.com/video/B ... 6255878836178982189
n代表待排序的元素个数
时间复杂度：最好情况O(n^2)、最坏情况O(n^2)、平均情况O(n^2)
空间复杂度:O(1)
稳定性：稳定
属于内排序
#include <iostream>
#include <vector>
using namespace std;
void select_sort(vector<int>& input){
int len = input.size();
int index;
for(int i = 0; i < len-1; i++){
index = i;
for(int j = i+1; j < len; j++){
if(input[j] < input[index]) index = j;
}
swap(input[i], input[index]);
}
}
int main(void){
vector<int> temp;
int number;
while(cin >> number){
temp.push_back(number);
}
select_sort(temp);
for(auto cha : temp) cout << cha << " ";
return 0;
}
三、插入排序
参考视频：https://www.bilibili.com/video/B ... 5355451024347335047
n代表待排序的元素个数
时间复杂度：最好情况O(n)、最坏情况O(n^2)、平均情况O(n^2)
空间复杂度:O(1)
稳定性：稳定
属于内排序
#include <iostream>
#include <vector>
using namespace std;
void sort(vector<int>& input){
int len = input.size();
for(int i = 1; i <len; i++){
for(int j = i; j > 0; j--){
if(input[j] < input[j-1]){
swap(input[j], input[j-1]);
}else{
break;
}
}
}
}
int main(void){
vector<int> temp;
int number;
while(cin >> number){
temp.push_back(number);
}
sort(temp);
for(auto cha : temp) cout << cha << " ";
return 0;
}
四、希尔排序
参考视频：https://www.bilibili.com/video/B ... 9271654472112320607
https://www.bilibili.com/video/B ... 9243453532555366843
n代表待排序的元素个数
时间复杂度：最好情况O(n^1.3)、最坏情况O(n^2)、平均情况O(nlogn)~O(n^2)
空间复杂度: O（1）
稳定性：不稳定
属于内排序
#include <iostream>
#include <vector>
using namespace std;
void sort(vector<int>& input){
int len = input.size();
for(int gap = len/2; gap > 0; gap /=2){
for(int i = gap; i < len; i++){
for(int j = i; j > 0; j--){
if(input[j] < input[j-gap]){
swap(input[j], input[j-gap]);
}else{
break;
}
}
}
}
}
int main(void){
vector<int> temp;
int number;
while(cin >> number){
temp.push_back(number);
}
sort(temp);
for(auto cha : temp) cout << cha << " ";
return 0;
}
五、堆排序
参考视频：https://www.bilibili.com/video/B ... 9245800988927155643
n代表待排序的元素个数
时间复杂度：最好情况O(nlogn)、最坏情况O(nlogn)、平均情况O(nlogn)
空间复杂度: O（1）
稳定性：不稳定
属于内排序
#include <iostream>
#include <vector>
using namespace std;
void maxHeap(vector<int>&input, int n, int len){
if(n >= len) return;
int root = n, left = 2*n+1, right = 2*n+2;
if(left < len && input[left] > input[root]) root = left;
if(right < len && input[right] > input[root]) root = right;
if(root != n){
swap(input[n], input[root]);
maxHeap(input, root, len);
}
}
void build(vector<int>&input, int n){
for(int i = (n-2)/2; i >= 0; i--) maxHeap(input, i, n);
}
void sortHeap(vector<int>&input, int n){
build(input, n);
for(int i = n; i > 0; i--){
swap(input[0], input[i-1]);
maxHeap(input, 0, i-1);
}
}
int main(void){
vector<int> input = {3,23,1,6,24,99,35,2,5};
sortHeap(input, input.size());
for(auto cha : input) cout << cha << " ";
return 0;
}
六、归并排序
视频参考：https://www.bilibili.com/video/B ... 4868815010429455110
代码参考：https://www.cnblogs.com/chengxiao/p/6194356.html
n代表待排序的元素个数
时间复杂度：最好情况O(nlogn)、最坏情况O(nlogn)、平均情况O(nlogn)
空间复杂度: O（n）
稳定性：稳定
属于外排序
#include<iostream>
#include<vector>
using namespace std;
void merge(vector<int>&input, int left, int mid, int right, vector<int>&temp){
int i = left;
int j = mid + 1;
int t = 0;
while(i <= mid && j <= right){
if(input[i] <= input[j]) temp[t++] = input[i++];
else temp[t++] = input[j++];
}
while(i <= mid) temp[t++] = input[i++];
while(j <= right) temp[t++] = input[j++];
//将temp中的元素全部拷贝到原数组中
t = 0;
while(left <= right) input[left++] = temp[t++];
}
void sort(vector<int>&input, int left, int right, vector<int>&temp){
if(left >= right) return;
if(left < right){
int mid = (right + left)/2;
sort(input, left, mid, temp);
sort(input, mid+1, right, temp);
merge(input, left, mid, right, temp);
}
}
int main(){
vector<int> input = {1,3,5,2,6,21,234,12};
int len = input.size();
vector<int> temp(len, 0);
sort(input, 0, len-1, temp);
for(auto cha :input) cout << cha << " ";
return 0;
}
七、快速排序
快速排序感觉看代码比看教程更清楚
n代表待排序的元素个数
时间复杂度：最好情况O(nlogn)、最坏情况O(n^2)、平均情况O(nlogn)
空间复杂度: O(nlogn)~O（n）
稳定性：不稳定
属于内排序
#include <iostream>
#include <vector>
using namespace std;
void quick_sort(int left, int right, vector<int>&input){
if(right <= left) return;
int i = left, j = right;
int base = input[i];
while(i < j){
while(i < j && input[j] >= base) j--;//这一句和下一句的顺序不能变
while(i < j && input[i] <= base)i++;
if(i < j) swap(input[i], input[j]);
}
swap(input[left], input[i]);
quick_sort(left, i-1, input);
quick_sort(i+1, right, input);
}
int main(void){
vector<int> input = {1, 3, 34, 54, 3,90, 34, 6, 2};
quick_sort(0, input.size()-1, input);
for(auto cha : input) cout << cha << " ";
return 0;
}
八、计数排序（桶排序的一种）
视频参考：https://www.bilibili.com/video/B ... 333.788.videocard.1
n代表待排序的元素个数， k代表数据中可能出现的不同数的个数
时间复杂度：最好情况O(n+k)、最坏情况O(n+k)、平均情况O(n+k)
空间复杂度: O(k)
稳定性：稳定
属于外排序
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int>&input){
vector<int> res;
map<int, int> store;
for(int i = 0; i < input.size(); i++){
store[input[i]] ++;
}
int min = *min_element(input.begin(), input.end());
int max = *max_element(input.begin(), input.end());
for(int i = min; i<= max; i++){
while(store.find(i) != store.end() && store[i] != 0){
res.push_back(i);
store[i] --;
}
}
return res;
}
int main(){
vector<int> input = {1, 20, 2, 7, 8, 14, 13, 15, 15, 2};
vector<int> res = solution(input);
for(auto cha : res) cout << cha << " ";
return 0;
}
九、基数排序（桶排序的一种）
视频参考：https://www.bilibili.com/video/B ... 4452742656427140512
n代表待排序的元素个数， k代表最高位数的长度。
时间复杂度：最好情况O(n*k)、最坏情况O(n*k)、平均情况O(n*k)
空间复杂度: O(n+k)
稳定性：稳定
属于外排序
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
void solution(vector<int>&input, int len){
for(int i = 0; i < len; i++){
map<int, vector<int>> count;
int division = pow(10, i);
for(int j = 0; j < input.size(); j++){
int num = input[j] / division % 10;
count[num].push_back(input[j]);
}
vector<int> temp;
for(int m = 0; m < 10; m++){
if(count.find(m) != count.end()){
temp.insert(temp.end(), count[m].begin(), count[m].end());
}
}
input = temp;
}
}
int main(){
vector<int> input = {1, 20, 2, 7, 8, 14, 13, 15, 15, 2};
int len = 2;
solution(input, len);
for(auto cha : input) cout << cha << " ";
return 0;
}
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2020-5-8 14:18:42
置顶卡
千斤顶
显身卡
楼主
