几年前备案的网站现在网站不在了备案号还在吗,wordpress彩色标签云插件,上海网站seo排名优化,wordpress底端小工具一、排序算法的作用#xff1a; 排序算法的主要作用是将一组数据按照特定的顺序进行排列#xff0c;使得数据更加有序和有组织。 1. 查找效率#xff1a;通过将数据进行排序#xff0c;可以提高查找算法的效率。在有序的数据中#xff0c;可以使用更加高效的查找算法…一、排序算法的作用 排序算法的主要作用是将一组数据按照特定的顺序进行排列使得数据更加有序和有组织。 1. 查找效率通过将数据进行排序可以提高查找算法的效率。在有序的数据中可以使用更加高效的查找算法如二分查找、插值查找等减少了查找的时间复杂度。 2. 统计分析在排序过程中可以对数据进行各种统计分析如计算各种统计量、查找中位数、众数等。有序的数据更加便于进行统计分析和数据挖掘。 3. 数据压缩和编码排序算法可以将数据重新排列进而提供更好的数据压缩和编码方式减少存储空间和传输带宽。 4. 数据归并和合并在某些应用中需要将多个有序的数据集合进行归并或合并排序算法提供了这样的功能。例如在合并两个有序的数组时可以使用归并排序算法。 5. 数据的可视化和展示有序的数据更容易进行可视化展示可以更加直观地表达数据的分布和关系。 6. 数据库和文件系统中的索引数据库和文件系统中的索引结构通常需要对数据进行排序以提高查询和检索的效率。 总之排序算法能够对数据进行有序排列提高数据的组织性和可读性提高查找和统计等操作的效率是计算机科学和实际应用中的基础算法之一。 二、基础排序算法
1选择排序 故名思义选择排序算法就是有选择地进行排序。其算法思想是 1、将数组分成【已排序区】和【待排序区】 2、每一轮从【待排序区】中选择一个最小的元素放到【已排序区】 3、直到【待排序区】没有元素为止 其算法的时间复杂度无论好坏都为O() 稳定性不稳定 其过程如图 关键代码实现
#define swap(a,b){\ //交换a,b__typeof(a) __c(a);\ //将a赋值给__c,同时__c的类型与a的类型一样(a)(b);\ //将b赋值给a(b)__c;\ //将__c赋值给b
}
void selection_sort(int *arr,int l,int n){ //选择排序for(int il;in-1;i){ //从下标0开始int indi; //假设下标为ind的数组元素最小for(int ji1;jn;j){if(arr[ind]arr[j])indj; //如果有比下标ind更小的则更新下标ind}swap(arr[i],arr[ind]); //将两个元素交换}return;
}
2插入排序 故名思义插入排序就是不断进行插入调整的排序。其算法思想是 1、将数组分成【已排序区】和【待排序区】 2、将【待排序区】后面第一个元素向前插入到【已排序区】并进行调整 3、直到【待排序区】没有元素为止 其算法的时间复杂度最好的情况下为O(n),最坏的情况下或平均情况下为O() 稳定性稳定 其过程如图 关键代码实现
#define swap(a,b){\ //交换a,b__typeof(a) __c(a);\(a)(b);\(b)__c;\
}
void insert_sort(int *arr,int b,int n){ //插入排序b0for(int ib1;in;i){ //待排序区从1开始int ji; //记录已排序区的最大下标while(jbarr[j]arr[j-1]){ //对新插入到已排序区的元素进行排序swap(arr[j],arr[j-1]);j-1;}}return;
}
3希尔排序 希尔排序Shell Sort是插入排序的一种改进版本也称为递减增量排序。它通过将原始数组分割成多个子序列对每个子序列进行插入排序然后逐步缩小子序列的范围最终完成排序。 希尔排序的基本算法思想 选择一个增量序列通常选择n/2、n/4、n/8...直到增量为1。 对每个增量进行插入排序将间隔为增量的元素分为一组对每组进行插入排序。 缩小增量重复第2步的操作直到增量为1即进行最后一次插入排序。 其算法的时间复杂度最好的情况下是O(nlogn)最坏的情况下是O() 稳定性不稳定 其过程如图 关键代码实现
#define swap(a,b){\ //交换a,b__typeof(a) __c(a);\ //将__c的类型在编译时转换为与a相同的类型并赋值(a)(b);\ //赋值交换(b)__c;\ //赋值交换
}
void insert_sort(int *arr,int b,int n,int step){ //插入排序b为起始下标n为最大下标int indb; //记录要开始进行插入排序的点for(int ibstep;in;istep){ //每次对间隔为step的元素排序if(arr[i]arr[ind])indi; //记录数组下标大而数据小的元素}while(indb){ swap(arr[ind],arr[ind-step]); //交换元素ind-step; //每次对间隔为step的元素进行排序}for(int ib2*step;in;istep){int ji;while(arr[j]arr[j-step]){swap(arr[j],arr[j-step]);j-step;}}return;
}
void shell_sort(int *arr,int b,int n){int k2,bc(n-b),step;do{stepbc/k0?1:(bc/k);for(int ib,Ibstep;iI;i){insert_sort(arr,i,n,step);}k*2;}while(step!1);return;
}
4快速排序 快速排序是通过选择一个基准元素将数组分成两个子数组一组小于基准元素另一组大于基准元素。然后对两个子数组分别递归地进行快速排序最终将整个数组排序。 快速排序的基本算法思想 1. 选择一个基准元素通常选择数组的第一个或最后一个元素。 2. 定义两个指针一个指向数组的第一个元素一个指向数组的最后一个元素。 3. 移动左指针直到找到一个大于等于基准元素的元素。 4. 移动右指针直到找到一个小于等于基准元素的元素。 5. 交换左指针和右指针所指向的元素。 6. 重复步骤3-5直到左指针和右指针相遇。 7. 将基准元素与左指针所指向的元素互换位置。 8. 进行递归对基准元素左边的子数组和右边的子数组进行快速排序。 其算法的时间复杂度最好的情况为O(nlogn)最坏的情况为O()。 其稳定性不稳定 其过程如图 关键代码实现
#define swap(a,b){\__typeof(a) __c(a);\(a)(b);\(b)__c;\
}
void quick_sort(int *arr,int l,int r){if(r-l2){if(r-l1)return;if(arr[l]arr[l1])swap(arr[l],arr[l1]);return;}int xl,yr-1,zarr[l];while(xy){while(xyzarr[y])--y;if(xy)arr[x]arr[y];while(xyarr[x]z)x;if(xy)arr[y]arr[x];}arr[x]z;quick_sort(arr,l,x);quick_sort(arr,x1,r);return;
}
int main(){
5归并排序 归并排序Merge sort是一种经典的排序算法它采用分治法的思想将问题分解为更小的子问题并且通过递归的方式解决这些子问题。然后将子问题的解合并起来最终得到原问题的解。 归并排序的基本算法思想 1. 每次将数组不断地二分为两个子数组直到每个子数组只剩下一个元素。 2. 然后将两个子数组逐个合并起来形成一个有序的新数组。 3.合并的方式是比较两个子数组的第一个元素将较小的元素放入新数组中并移动指针继续比较下一个元素。 4. 重复上述步骤直到将所有的子数组都合并起来得到最终的有序数组。 归并排序的时间复杂度最好的情况下O(nlogn)最坏的情况下O(nlogn)。 这是一种稳定的排序算法适用于各种数据类型。但是归并排序需要额外的存储空间来存储临时数组空间复杂度为O(n)。 其过程如图 原数组[54271683] 关键代码实现
#includestdio.h
#includestdlib.h
#includetime.h
#includestring.h
#define SMALL 1000000
__attribute__((constructor))
void __init_Rand__(){srand(time(0));
}
bool check(int *arr,int l,int r){for(int il1;ir;i){if(arr[i]arr[i-1])return false;}return true;
}
#define swap(a,b){\__typeof(a) __c(a);\(a)(b);\(b)__c;\
}
#define TEST(func,arr,n){\printf(TEST:%s,#func);\int *temp(int *)malloc(sizeof(int)*n);\memcpy(temp,arr,sizeof(int)*n);\long long bclock();\func(temp,0,n);\long long eclock();\if(check(temp,0,n)){\printf(\tOK);\}else{\printf(\tNO);\}\printf(\t%lldms\n,(e-b)*1000/CLOCKS_PER_SEC);\free(temp);\
}
int *getRandData(int n){int *arr(int *)malloc(sizeof(int)*n);for(int i0;in;i){arr[i]rand()%1001;}return arr;
}
int *buff; //额外存储空间
void merge_sort(int *arr,int l,int r){ r为数组长度l为开始位置初始为0if(r-l1)return; //如果只有一个元素返回结果int mid(lr)/2; //每次都将数组二分merge_sort(arr,l,mid); //递归二分前半段的数组merge_sort(arr,mid,r); //递归二分后半段的数组int p1l,p2mid,k0;//p1记录第一个数组元素下标p2记录中间元素下标k记录当前位置便于排序while(p1mid||p2r){ //前半段数组范围、后半段数组范围if(p2r||(p1midarr[p1]arr[p2])){ buff[k]arr[p1];}else{buff[k]arr[p2];}}for(int il;ir;i)arr[i]buff[i-l];return;
}
int main(){int *arrgetRandData(SMALL);buff(int *)malloc(sizeof(int)*SMALL);TEST(merge_sort,arr,SMALL);free(buff);return 0;
}
6基数排序 基数排序是一种非比较型的排序算法它将数据按照位数进行分组分别对每个位数进行排序直到最高位数排序完毕。基数排序可以用于对非负整数进行排序。 基数排序的基本算法思想如下 1. 将待排序的数据从最低位开始按照个位数进行分组。 2. 对每个分组进行计数排序将数据按照个位数的大小进行排序。 3. 将所有分组的数据按照排序结果进行合并。 4. 重复步骤1-3按照十位数、百位数等依次进行排序直到最高位数排序完毕。 基数排序的时间复杂度最好的情况下O(k*n)最坏的情况下O(k*n)。其中k是最大数的位数n是待排序数据的个数。 基数排序的空间复杂度是O(nk)。 基数排序的优点是稳定性好适用于数据量较大且每个数位数较小的情况。然而基数排序的缺点是需要占用大量的额外空间且对于负数无法直接排序。 基数排序过程如图 关键代码实现
#includestdio.h
#includestdlib.h
#includetime.h
#includestring.h
#define K 65536
#define SMALL 1000000
__attribute__((constructor))
void __init_Rand__(){srand(time(0));
}
#define swap(a,b){\__typeof(a) __c(a);\(a)(b);\(b)__c;\
}
bool check(int *arr,int l,int r){for(int il1;ir;i){if(arr[i]arr[i-1])return false;}return true;
}
#define TEST(func,arr,n){\printf(TEST:%s,#func);\int *temp(int *)malloc(sizeof(int)*n);\memcpy(temp,arr,sizeof(int)*n);\long long bclock();\func(temp,0,n);\long long eclock();\if(check(temp,0,n)){\printf(\tOK);\}else{\printf(\tNO);\}\printf(\t%lldms\n,(e-b)*1000/CLOCKS_PER_SEC);\free(temp);\
}
int *getRandData(int n){int *arr(int *)malloc(sizeof(int)*n);for(int i0;in;i){arr[i]rand()%1001;}return arr;
}
void radix_sort(int *arr,int l,int r){int *cnt(int *)malloc(sizeof(int)*K);int *temp(int *)malloc(sizeof(int)*r);memset(cnt,0,sizeof(int)*K);for(int i0;ir;i)cnt[arr[i]%K]1;for(int i1;iK;i)cnt[i]cnt[i-1];for(int ir-1;il;i--)temp[--cnt[arr[i]%K]]arr[i];memcpy(arr,temp,sizeof(int)*r);memset(cnt,0,sizeof(int)*K);for(int i0;ir;i)cnt[arr[i]/K]1;for(int i1;iK;i)cnt[i]cnt[i-1];for(int ir-1;il;i--)temp[--cnt[arr[i]/K]]arr[i];memcpy(arr,temp,sizeof(int)*r);free(temp);free(cnt);return;
}
int main(){int *arrgetRandData(SMALL);TEST(radix_sort,arr,SMALL);free(arr);return 0;
}
文章到此结束
