排序算法：shell排序/基数排序/桶排序
shell排序：
1.优化后的插入排序
2.按步长step分组：步长一开始设置为元素个数/2
3.组内插入排序
4.步长=步长/2
基数排序：
1.创建临时数组
2.初始化临时数组
3.临时数组排序
4.将临时数组值赋值回原数组
5.delete临时数组
限制：1.不能有重复运算
2.空间浪费大
优点：不需要经过比较
桶排序：基数排序的升级
1.根据数据范围获取排序次数
2.制作桶并且初始化
3.遍历a数组并且按照排序依据将a数组元素存到桶里
4.放回原来数组里
总结：希尔排序速度快，不稳定
桶排序速度快，稳定，但是空间复杂度高
代码演示：
1.希尔排序：
# include<iostream>
# include<vector>
#define NUM 10
using namespace std;
void print_art(int* a, int len){
for(int i=0; i<len; i++){
printf("%d ", a[i]);
}
}
//插入排序
void insert_sort(int* a, int len){
int temp;//保存待插元素
int j;//循环变量
//插入排序三步走：
//1.从第二个元素开始往前插入
//2.找到满足条件的插入点并且将元素后移
//3.将此处a[j]与temp存储的待插元素交换
//1.从第二个元素开始往前插入
for(int i=1; i<len; i++){
temp = a[i];//保存待插元素
j = i - 1;
//2.找到满足条件的插入点并且将元素后移
while(j>=0 && a[j]>temp){
a[j+1] = a[j]; //赋值
j--;
}
//3.将此处a[j]与temp存储的待插元素交换
a[j+1] = temp;
}
}
//shell排序
void shell_sort(int* a, int len){
//shell排序三步走：
int step = len / 2;//1.初始化步长
int temp;
int j;
while(step >= 1){//2.每次步长都要减半
//3.组内插入排序
for(int i=step; i<len; i++){//注意i=step，从步数step那里开始向后
temp = a[i];
j = i - step;//每次减少一次步长
while(j>=0 && a[j]>temp){
a[j+step] = a[j]; //赋值
j = j-step;//元素后移
}
a[j+step] = temp;
}
step = step/2;//步长减一
}
}
//主函数测试
int main(){
int a[NUM] = {1, 22, 5, 8, 88, 16, 66, 20, 30, 666};
insert_sort(a, NUM);
print_art(a, NUM);
shell_sort(a, NUM);
print_art(a, NUM);
return 0;
}
2.基数排序：
# include<iostream>
# include<vector>
#define NUM 10
using namespace std;
void print_art(int* a, int len){
for(int i=0; i<len; i++){
printf("%d ", a[i]);
}
}
//基数排序
void radix_sort(int* a, int len, int max){
//基数排序5步走：
// 1.创建临时数组
// 2.初始化临时数组
// 3.临时数组排序
// 4.将临时数组值赋值回原数组
// 5.delete临时数组
int* b = new int[max+1];//创建临时数组
int j = 0;
for(int i=0; i<max+1; i++)//初始化临时数组
b[i] = -1;
for(int i=0; i<len; i++)//临时数组排序
b[a[i]] = a[i];
for(int i=0; i<max+1; i++){//将临时数组值赋值回原数组
if(b[i] != -1){
a[j++] = b[i];
}
}
delete[] b;//删除
}
int main(){
int a[NUM] = {1, 22, 5, 8, 88, 16, 66, 20, 30, 666};
radix_sort(a, NUM, 666);
print_art(a, NUM);
return 0;
}
3.桶排序：
# include<iostream>
# include<vector>
# include<string.h>
//元素个数
#define NUM 10
//数据范围限定：3位数(小于1000)
#define AREA 1000
void print_art(int* a, int len){
for(int i=0; i<len; i++){
printf("%d ", a[i]);
}
}
//桶排序
void bucket_sort(int* a, int len){
//桶排序
// 1.根据数据范围获取排序次数
// 2.制作桶并且初始化
// 3.遍历a数组并且按照排序依据将a数组元素存到桶里
// 4.放回原来数组里
for(int i=1; i<AREA; i*=10){//根据数据范围获取排序次数:三位数则排序次数为3次(个位，十位，百位)
int temp[10][NUM];//制作桶
memset(temp, -1, sizeof(int)*10*NUM);//桶初始化每个元素为-1
for(int j=0; j<len; j++){
int m = a[j] / i % 10;//取到所需要的位
temp[m][j] = a[j];//将取到的位存到对应桶里
}
int k = 0;//放回原来数组里
for(int p=0; p<10; p++){
for(int q=0; q<NUM; q++){
if(temp[p][q] != -1){
a[k++] = temp[p][q];
}
}
}
}
}
int main(){
int a[NUM] = {1, 22, 5, 8, 88, 16, 66, 20, 30, 666};
bucket_sort(a, NUM);
print_art(a, NUM);
return 0;
}