广东营销型网站建设,18年手机网站,wordpress做商城网站吗,网站搜索栏怎么做#x1f427;作者主页#xff1a;king南星 #x1f3f0;专栏链接#xff1a;c 文章目录一、八大排序算法复杂度对比二、基于比较的排序算法1.冒泡排序2.选择排序3.插入排序4.希尔排序5.直观感受四种算法的时间复杂度三、基于非比较的排序算法1.基数排序2.箱(桶)排序四… 作者主页king南星 专栏链接c 文章目录一、八大排序算法复杂度对比二、基于比较的排序算法1.冒泡排序2.选择排序3.插入排序4.希尔排序5.直观感受四种算法的时间复杂度三、基于非比较的排序算法1.基数排序2.箱(桶)排序四、递归比较排序算法1.快速排序2.归并排序1.普通归并2.归并递归一、八大排序算法复杂度对比 二、基于比较的排序算法
1.冒泡排序
介绍冒泡排序Bubble Sort是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列依次比较两个相邻的元素如果顺序如从大到小、首字母从Z到A错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端升序或降序排列就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样故名“冒泡排序” 核心 冒泡排序: 比较 NUM-1轮每轮NUM-1次 每轮相邻两个比较不符合要求则交换 找出一个最大的或者一个最小的
//冒泡排序
void bubble_sort(int* a, int len)
{int t;for ( int i 0; i len-1; i) //len-1轮{for( int j 0; j len-1-i ; j ) //每轮为无序的元素个数-1次{if ( a[j] a[j1] ) //不符合规则交换{t a[j];a[j] a[j 1];a[j 1] t;}}}
}总结 冒泡排序是一种非常容易理解的排序时间复杂度O( N2)空间复杂度O(1)稳定性稳定 2.选择排序 介绍选择排序Selection sort是一种简单直观的排序算法。它的工作原理是第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 核心 选择排序 先假设待排数组第一个为最小值 选择NUM-1轮每轮从待排数组中选最小的与第一个进行比较决定放不放到待排数组第一个 循环从待排数组中找到最小的记录其下标 交换 //选择排序
void select_sort(int* a, int len)
{int t;int minIndex;for (int i 0; i len-1; i) //len-1轮{//从待排数组中(i ----- len-1)找到最小的minIndex i; //先假设待排数组中的第一个最小for (int j i1; j len; j){minIndex a[j] a[minIndex] ? minIndex : j;}//符合条件和待排数组中的第一个元素(i)交换if ( a[minIndex] a[i] ){t a[minIndex];a[minIndex] a[i];a[i] t;}}
}总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N2)空间复杂度O(1)稳定性不稳定 3.插入排序 介绍插入排序一般也被称为直接插入排序。对于少量元素的排序它是一个有效的算法 。插入排序是一种最简单的排序方法它的基本思想是将一个记录插入到已经排好序的有序表中从而一个新的、记录数增1的有序表。在其实现过程使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找并进行移动。 核心 插入排序 设置第一个为有序数组右边NUM-1个为待插数据 然后NUM-1轮每轮把一个数据插入到有序数组中 插入方式 1. 先临时保存待插数据 2. 然后从待插数据前一个开始往前循环越界循环结束 比待插数据大则往后覆盖比待插数据小则循环结束 3. 用待插数据覆盖回来第二步结束后下标的下一个位置 插入部分图解
//插入排序
void insert_sort(int* a, int len)
{int j;int temp;//保存待插数据for (int i 1; i len; i) //len-1轮{temp a[i]; //待插数据前一个开始往前循环越界循环结束for ( j i-1 ; j 0 ; j-- ) {//比待插数据大则往后覆盖if ( a[j] temp ) a[j 1] a[j];else break;}//用待插数据覆盖回来第二步结束后下标的下一个位置a[j 1] temp;}
}总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 4.希尔排序 介绍 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”Diminishing Increment Sort是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止。 核心 希尔shell排序 一个叫做shell的科学家发明的 优化后的插入排序 引入步长的概念 一开始是 len/2 然后每次 除2 到1为止 根据步长来分组然后组内作插入排序 //希尔排序
void shell_sort(int* a, int len)
{int j, temp;int step len 2;while ( step )//根据步长来分组{//组内作插入排序//从step开始 len-1-step轮for( int i step ; i len; i ){temp a[i];//临时保存待插数据//待插数据前一个开始往前循环越界循环结束for ( j i-step; j 0 ; j - step ){//比待插数据大则往后覆盖if (a[j] temp) a[j step] a[j];else break;}//用待插数据覆盖回来第二步结束后下标的下一个位置a[j step] temp;}step 1;}
}总结 希尔排序是对直接插入排序的优化。当step 1时都是预排序目的是让数组更接近于有序。当step 1时数组已经接近有序的 了这样就会很快。这样整体而言可以达到优化的效果。希尔排序的时间复杂度不好计算需要进行推导推导出来平均时间复杂度 O(N1.3— N2稳定性不稳定 5.直观感受四种算法的时间复杂度 这里随机产出100000个数字利用上面4种排序算法进行排序结果如下可以看到希尔排序仅仅用了16ms #include stdio.h
#include time.h
#include stdlib.h
#include windows.h
//数据个数
#define NUM 100000void init(int* a, int len);
void bubble_sort(int* a, int len);
//选择排序
void select_sort(int* a, int len);
//插入排序
void insert_sort(int* a, int len);
//希尔排序
void shell_sort(int* a, int len);int main() {ULONGLONG oldTime, newTime;srand(time(NULL));int arr[NUM];init(arr, NUM);//初始化//获取排序前时间oldTime GetTickCount64();bubble_sort(arr, NUM);//排序//获取排序后时间newTime GetTickCount64();printf(bubble_sort:%llu\n, newTime - oldTime);init(arr, NUM);oldTime GetTickCount64();select_sort(arr, NUM);newTime GetTickCount64();printf(select_sort:%llu\n, newTime - oldTime);init(arr, NUM);oldTime GetTickCount64();insert_sort(arr, NUM);newTime GetTickCount64();printf(insert_sort:%llu\n, newTime - oldTime);init(arr, NUM);oldTime GetTickCount64();shell_sort(arr, NUM);newTime GetTickCount64();printf(shell_sort:%llu\n, newTime - oldTime);while (1);return 0;
}
void init(int* a, int len) {for (int i 0; i len; i)a[i] rand() % 1000;
}
//希尔排序
void shell_sort(int* a, int len) {int step len / 2;int temp;int j;while (step) {//分组//组内做插入排序for (int i step; i len; i) {//每次循环插入a[i]temp a[i];//临时存储待插数据for (j i - step; j 0 a[j] temp; j - step) {//从前往后覆盖a[j step] a[j];}a[j step] temp;}step / 2;//每次步长变成原来的一半}
}//插入排序
void insert_sort(int* a, int len) {int temp;int j;for (int i 1; i len; i) {//每次循环插入a[i]//把a[i] 插入到 a[0] - a[i-1] 数组中去temp a[i];//临时存储待插数据for (j i - 1; j 0 a[j] temp; j--) {//从前往后覆盖a[j 1] a[j];}//插入进来a[j 1] temp;}
}
//选择排序
void select_sort(int* a, int len) {int min_idx;//记录最小的元素的下标int temp;for (int i 0; i len - 1; i) {//找len-1次//每次 找出 a[i] - a[len-1] 范围内最小的元素 min_idx i;//假设a[i]最小for (int j i; j len; j) {min_idx ((a[min_idx] a[j]) ? min_idx : j);}//a[min_idx] 和 a[i]交换temp a[i];a[i] a[min_idx];a[min_idx] temp;}
}void bubble_sort(int* a, int len) {int temp;for (int j 0; j len - 1; j) {for (int i 0; i len - j - 1; i) {//0 - len-2if (a[i] a[i 1]) {//不符合要求//交换temp a[i];a[i] a[i 1];a[i 1] temp;}}}
}三、基于非比较的排序算法
1.基数排序 介绍基数排序radix sort属于“分配式排序”distribution sort又称“桶子法”bucket sort或bin sort顾名思义它是透过键值的部份资讯将要排序的元素分配至某些“桶”中藉以达到排序的作用基数排序法是属于稳定性的排序其时间复杂度为O (nlog®m)其中r为所采取的基数而m为堆数在某些时候基数排序法的效率高于其它的稳定性排序法。 核心 基数排序 O(n) 最快的排序方式 没有之一 利用数组下标天然有序的特性来进行排序 max:最大元素值 限制很多 1. 只能排正整数优化后可以对所有整数排序
2. 不能有重复
3. 空间可能耗费特别大
4. 临时空间大小//基数排序
void radix_sort(int* a, int len, int max)
{int index 0;//先准备一个临时数组 max1int* pTemp (int*)malloc(sizeof(int) * (max 1));assert(pTemp); //判断申请成功没//初始化为-1//for (int i 0; i max; i) pTemp[i] -1;memset(pTemp, -1, sizeof(int) * (max 1));//将待排数组放到临时数组中待排数组的值作为临时数组的下标for (int i 0; i len; i) pTemp[a[i]] a[i];//从临时数组中把排序好的数据放回原数组中for (int i 0; i max; i) {if ( pTemp[i] ! -1 ){a[index] pTemp[i];}}//释放内存free(pTemp);
}总结 时间复杂度Onk空间复杂度Onk不能对小数进行排序但是速度极快 2.箱(桶)排序 介绍桶排序 (Bucket sort)或所谓的箱排序是一个排序算法工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候桶排序使用线性时间Θn。但桶排序并不是 比较排序他不受到 O(n log n) 下限的影响。 核心 桶(箱)排序:bucket_sort 把数据分成若干个箱子 然后箱子里用其他排序 这里是按个位十位分箱内部类似于基数排序
//箱排序
void bucket_sort(int* a, int len)
{int idx, k;int n 1; int* pTemp NULL;while ( n AREA )//1000以内的数字AREA 1000{//1 做箱子 并初始化箱子pTemp (int*)malloc(10 * len * sizeof(int));for (int i 0; i 10 * len; i) pTemp[i] -1;//2 根据特性(对应位作为箱子的编号)放入箱子中for (int i 0; i len; i){//获取到数据这一轮要看的位上的数据idx a[i] / n % 10;pTemp[idx * len i] a[i];}//3 从箱子中取出覆盖a数组k 0;for (int i 0; i 10*len; i){if ( pTemp[i] ! -1 )a[k] pTemp[i];}//4 销毁箱子free(pTemp);pTemp NULL;n * 10;}
}四、递归比较排序算法
1.快速排序 介绍快速排序Quicksort计算机科学词汇适用领域Pascalc等语言是对冒泡排序算法的一种改进。 核心 快速排序就是分组排序 把数据分成两组 确定中间值左边都比中间值小 右边都比中间值大 递归(递推)持续分组 到 不可再分(一组只有一个数据)为止 void Quick_sort(int* a, int len)
{quick_sort(a, 0, len - 1);
}
void quick_sort(int* a, int Left, int Right)
{int L Left, R Right;if ( L R ) return; //递归结束// 先假设a[left]是中间数据,并临时保存int temp a[L];// 循环挪动l和r并覆盖 循环结束后 LRwhile ( L R ){// 先挪右边的while ( L R a[R] temp) R--;a[L] a[R];// 再挪左边的while (LR a[L] temp ) L;a[R] a[L];}// 用中间数据覆盖回来a[L] temp; //a[R] temp;quick_sort(a, Left, R - 1);quick_sort(a, L 1, Right);
}2.归并排序
介绍归并排序是建立在归并操作上的一种有效稳定的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
1.普通归并
核心两个有序数组合并成一个有序数组 void Merge_sort(int* a, int L, int M, int R)
{int Left L, Right M 1;if (L R) return;//开临时内存int* pTemp (int*)malloc(sizeof(int) * (R - L 1));int k 0;//两个中有一个放完了while ( Left M Right R ){if (a[Left] a[Right]) pTemp[k] a[Left];else pTemp[k] a[Right];}//左边还没放完if (Left M) memcpy(pTemp k, a Left, sizeof(int) * (M - Left 1));//右边还没放完else memcpy(pTemp k, a Right, sizeof(int) * (R - Right 1));//覆盖回去memcpy( a L , pTemp, sizeof(int) * (R - L 1));//释放内存free(pTemp);
}2.归并递归
核心把无序数组完全拆开再进行归并排序 void Merge_Sort(int* a, int len)
{merge__sort(a, 0, len - 1);
}
void merge__sort(int* a, int L, int R)
{// L和R不相等说明还没拆到只剩一个继续拆if (L R){int m L (R - L) / 2;merge__sort(a, L, m); //左边一半merge__sort(a, m 1, R); //右边一半Merge_sort(a, L, m, R); //拆到无法拆了就合并}
}欢迎各位→点赞 收藏 留言 总结希望你看完之后能对你有所帮助不足请指正共同学习交流
