内部排序
- 这里先介绍一个概念，算法稳定性
- 算法稳定性 — 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
// O(N2), 稳定的算法
void bubble_sort(int * arr,size_t n){
bool sort =false;
for(int i=0;i0 && key> 1;
if(arr[mid] L;--j) arr[j+i] = arr[j];
arr[L] = key;
}
}
void two_road_insert_sort(int * arr,size_t n){
}
/*
希尔排序的时间复杂度与增量(即，步长gap)的选取有关。
例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)
而Hibbard增量的希尔排序的时间复杂度为O(N^3/2^)。
不稳定的算法
*/
void shell_insert_sort(int * arr,size_t n){
int i,j,gap; // gap 步长
for(gap=n/2;gap>0;gap/=2){
for(i=gap;i=0&&key0
if(L>1) quick_sort(arr,L);
// [L+1,n-1] n>L+1 为什么不是 n-1>L+1
if(L+1=0;--i) reheap(arr,i,n);
for(i=n-1;i>0;--i){
//把arr[0]和最后一个元素交换位置
swap(arr[0],arr[i]);
//0下标元素发生改变 只需要重新调整0位置的元素即可
reheap(arr,0,i);
}
}
// 鸡尾酒排序
void cocktail_sort(int * arr,size_t n){
int i,j;
for(i=0;i= [mid,n)
}
while(j0 ) // 桶内元素个数>0
arr[j++] = i;
}
}
/*
基数排序
MSD：先从高位开始进行排序，在每个关键字上，可采用桶排序
LSD：先从低位开始进行排序，在每个关键字上，可采用计数排序
*/
void radix_sort(int * arr,size_t n){
int exp;
// 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
int max = get_max(arr, n); // 数组a中的最大值
int tmp[n];
int count[10]; //计数器
// 从个位开始，对数组a按"指数"进行 计数排序
int i,j;
for (exp = 1; max/exp > 0; exp *= 10){
for(i = 0; i < 10; i++) count[j] = 0; //每次分配前清空计数器
for(i = 0; i < n; i++)
++count[(arr[j] / exp) % 10]; //统计每个桶中的记录数
for(i = 1; i < 10; i++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for(i = n - 1; i >= 0; i--) //将所有桶中记录依次收集到tmp中
{
tmp[count[k] - 1] = arr[(arr[j] / exp) % 10];
count[k]--;
}
for(i = 0; i < n; i++) //将临时数组的内容复制到data中
arr[j] = tmp[j];
}
}
/*
适用于密集且数据跨度小的序列
计数排序(Counting Sort)不是基于比较的排序算法，
其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
*/
void count_sort(int * arr,size_t n){
int max = arr[0],min = arr[0];
int i,j;
for(i=0;imax) max = arr[i];
else if(arr[i]0){
arr[j++] = i+min;
--flag[i];
}
}
}
/*
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
*/
外部排序
//每个归并段的数据量为10个
#define NUM_OF_SEGMENT 10
long num_of_file(const char *file){
FILE *fp = fopen(file,"r");
if(fp == NULL){
return -1;
}
fseek(fp,0,SEEK_END);
long fs = ftell(fp);//文件大小 字节 long
fclose(fp);
return fs/4;
}
#define FILE_NAME 48
typedef struct MergeSegment{
char file[FILE_NAME];
size_t size; //归并段中数据的总数
size_t num; //这个归并段已经读取的个数
FILE *fp;
}MSM;
//这个归并段是否处理完成了 处理完成了表示没有数据了
bool is_completed(MSM *pms){
return pms->size == pms->num;
}
int load_data(MSM *pms,int data[]){
if(is_completed(pms)){
return 0;
}
int ret = fread(data,sizeof(int),NUM_OF_SEGMENT,pms->fp);
pms->num += ret;
return ret;
}
int save_data(MSM *pms,int data[],size_t num){
int ret = fwrite(data,sizeof(int),num,pms->fp);
pms->size += ret;
return ret;
}
void fclose_file(MSM *pms){
fclose(pms->fp);
}
int open_file_read(MSM *pms){
pms->fp = fopen(pms->file,"rb");
if(pms->fp == NULL){
printf("open %s failed!\n",pms->file);
return -1;
}
return 0;
}
int open_file_write(MSM *pms){
pms->fp = fopen(pms->file,"wb");
if(pms->fp == NULL){
return -1;
}
return 0;
}
//init_segment(file,msms,segs);
void init_segment(const char *file,MSM *msms,int segs){
int data[NUM_OF_SEGMENT] = {};
int i;
FILE *fp = fopen(file,"rb");
for(i=0;isize,pm1->num,pm2->size,pm2->num);
//strcpy(pres->file,"1"); //文件同名了
strcpy(pres->file,"ab");//这个地方错了 不能直接在名字前加一个1 因为 之前有0-19.txt 会提前删除掉数据
strcat(pres->file,pm1->file);
pres->fp = NULL;
pres->num = pres->size = 0;
open_file_write(pres);
int data1[NUM_OF_SEGMENT] = {};
int data2[NUM_OF_SEGMENT] = {};
int i=0,j=0;
int cnt1 = 0,cnt2 = 0;
cnt1 = load_data(pm1,data1);
cnt2 = load_data(pm2,data2);
while(isize,pm1->num,pm2->size,pm2->num);
printf("写入文件大小 res fs=%d\n",pres->size);
}
//假设文件中存储的都是int类型 如果要写通用 传递比较函数 每一个数据的字节大小
int outside_sort(const char *file){
assert(file!=NULL);
long cnt = num_of_file(file);
if(cnt == -1){
return -1;
}
printf("%d\n",cnt);
//归并段的个数
int segs = cnt/NUM_OF_SEGMENT;
if(cnt%NUM_OF_SEGMENT>0){
++segs;
}
MSM msms[segs];
int i;
for(i=0;i1){
MSM res = {};
int cnt = 0;
for(i=0;i0){
printf("%d ",d);
}
printf("\n");
fclose(fp);
/*
for(i=0;i
Original: https://www.cnblogs.com/FlyingDoG–BoxPiG/p/16728432.html
Author: 打工搬砖日记
Title: 排序算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/574032/
转载文章受原作者版权保护。转载请注明原作者出处！