全国建设地产网站,用模板建商场购物网站,wordpress 文章发布 编辑器,网页作品制作的一般过程个人主页~
堆排序看这篇~ 还有这篇~ 排序 一、排序的概念及应用1、概念2、常见的排序算法 二、常见排序的实现1、直接插入排序#xff08;1#xff09;基本思想#xff08;2#xff09;代码实现#xff08;3#xff09;时间复杂度#xff08;4#xff09;空间复杂度 2… 个人主页~
堆排序看这篇~ 还有这篇~ 排序 一、排序的概念及应用1、概念2、常见的排序算法 二、常见排序的实现1、直接插入排序1基本思想2代码实现3时间复杂度4空间复杂度 2、希尔排序1基本思想2代码实现3时间复杂度4空间复杂度 3、选择排序1基本思想2代码实现3时间复杂度4空间复杂度 4、堆排序1基本思想2代码实现3时间复杂度4空间复杂度 5、冒泡排序1基本思想2代码实现3时间复杂度4空间复杂度 6、快速排序1基本思想2代码实现①hoare版本②挖坑法版本③前后指针版本 3时间复杂度4空间复杂度 一、排序的概念及应用
1、概念
排序就是按照某一关键字递增和递减排列起来的操作 排序在生活中非常常用成绩、排行等等一切跟数字字母等有关的都能够排序
2、常见的排序算法
常见的排序算法有 插入排序直接插入排序希尔排序 选择排序选择排序堆排序 交换排序冒泡排序、快速排序 归并排序归并排序
二、常见排序的实现
1、直接插入排序
1基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列
2代码实现
//我们看做一个一个插入
void InsertSort(int* a, int n)
{for (int i 1; i n; i){//从0到end都有序tmp插入排序int end i - 1;//end存储插入前的最后一个元素的下标也就是第i-1个数据int tmp a[i];//tmp是插入的数据也就是第i个数据while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}//如果前边比后边大就交换并且--end继续向前比较else{break;//直到后边比前边大}}a[end 1] tmp;//将此时end1下标的位置赋值tmp后边的数据全都往后移了一位}
}封装一个打印数组的函数
void ArrPrint(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}
}3时间复杂度
如果按照最坏的情况 第一次排不需要比较 第二次需要比较一次 第三次需要比较两次 … 第N次需要比较N-1次 F(N)0123…N-1 (N-1)*(N)/2 所以直接插入排序的最坏时间复杂度为O(N^2) 最好时间复杂度就是有序数组O(N) 所以直接插入排序是介于它们之间的这才有了希尔排序这种优化算法降低了时间复杂度
4空间复杂度
没有占用额外空间O(1)
2、希尔排序
1基本思想
希尔排序可以说是高级的直接插入排序它是希尔通过观察和实践在直接插入排序的基础上进行算法优化将时间复杂度降低 希尔排序分为两步 第一步预排序是将无序的数组排序至接近有序 第二步直接插入排序 当gap越小越接近有序gap越大预排序的速度会更快 当gap为1时就是直接插入排序 简单来说希尔排序就是粗排后细排
2代码实现
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;//分为三组最后加一可以保证最后一次的while循环gap等于1相当于直接插入排序for (int i 0; i n - gap; i){int end i;
//每组的最后一个数字这里的最后一个是指一个一个往里面插的最后一个数字并不是真正的最后一个数字int tmp a[end gap];//记录待插入数字while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}elsebreak;}//同直接插入排序差别是分了组每次要对比的数字的下标差了gapa[end gap] tmp;}}
}3时间复杂度
希尔排序的时间复杂度并不好计算因为gap的取值很多我们没办法通过简单的计算来得出结果这是一个数学上的难以解答的问题资料中显示它的时间复杂度在O(n^1.25)到O(1.6*n ^1.25)之间我们粗略表示成O(n ^1.3)
4空间复杂度
没有占用额外空间O(1)
3、选择排序
1基本思想
遍历数组每一次将最大和最小的数据挑出来放到数列的起始和末尾位置知道所有元素全部排完 这是一种超级慢的排序方式实际使用中很少用
2代码实现
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;}void SelectSort(int* a, int n)
{int right n - 1;//定位到数组最后一个元素下标int left 0;//定位到数组第一个元素下标while (left right){int min left;//先将left作为最开始的最小值int max right;//先将right作为最开始的最大值for (int i left; i right; i){if (a[i] a[min])min i;if (a[i] a[max])max i;}//在left和right之间选出最大和最小的数Swap(a[left], a[min]);//交换a[left]与a[min]if (left max)max min;//这里注意当最大值与left重叠时将位置修正再交换Swap(a[right], a[max]);left;right--;}
}3时间复杂度
它的时间复杂度就是等差数列求和可以很容易的看出来它的时间复杂度为O(N^2)
4空间复杂度
没有占用额外空间O(1)
4、堆排序
在之前的文章中有详细的解释我们可以来到二叉树-堆文章中来详细了解
1基本思想
利用堆的特性即小堆堆顶最小大堆堆顶最大的性质来进行升序或降序排序
2代码实现
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}void AdjustDown(int* a, int n,int parent)
{int child parent * 2 1;while(child n){if (child 1 n a[child] a[child 1]){child;}//调出值较大的那个孩子if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}//交换后让孩子当爹使其跟它的孩子比较elsebreak;}
}void HeapSort(int* a, int n)
{//parent (child-1) / 2i的初始值是最后一个元素的父节点for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//调整出一个大堆int end n - 1;while (end 0){Swap(a[0], a[end]);//交换首尾元素AdjustDown(a, end, 0);end--;}
//每次调整都会将最大的一个数放在当前调整范围的最后一个位置而调整范围的最后一个位置每次都会向前一个直到成为升序数组
}3时间复杂度
在前面链接中的文章中我们计算过它的时间复杂度O(N*log₂N)
4空间复杂度
没有额外申请空间O(1)
5、冒泡排序
1基本思想
冒泡排序是我们初识C语言时的接触到的第一个排序方式也可以说是最鸡肋的排序方式简单易懂但效率很低就是两两元素相互比较大的往后移动遍历一遍下来最大的就到最后了以此类推实现排序 这里我就不过多解释了
2代码实现
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}void BubbleSort(int* a, int n)
{for (int i 0; i n; i){for (int j 0; j n - i - 1; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
}3时间复杂度
相当于等差数组求和n-1 n-2 … 1 F(N) (N-11)/2 * N/2 时间复杂度为O(N^2)
4空间复杂度
没有占用额外空间空间复杂度为O(1)
6、快速排序
1基本思想
任取待排序序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素小于基准值右子序列中所有元素大于基准值然后在左右子序列中重复该过程直到排序完成 这里我们每一次取的基准值都是左数第一个元素
2代码实现
①hoare版本
int PartSort1(int* a, int left, int right)
{int keyi left;//将最左边的元素作为关键元素即基准值记录它的下标while (left right){while (left right a[keyi] a[right]){right--;}while (left right a[keyi] a[left]){left;}Swap(a[left], a[right]);
//左右两边向中间逼近在右边找到小于基准值的数字在左边找到大于基准值的数字两者交换}Swap(a[keyi], a[left]);//循环出来之后说明left与right相遇了也就是说此时的这个位置左边的数字全部比基准值小右边的数字都比基准值大将这个位置的数字与基准值位置的数字交换位置return left;//将此时的基准值返回
}void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort1(a, left, right);//将区间分成三个部分keyikeyi左keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);//对剩下的区间继续排序
}②挖坑法版本
int PartSort2(int* a, int left, int right)
{int key a[left];//存下坑里的数字int hole left;//把最左边的位置作为坑while (left right){while (left right a[right] key)right--;//找到a[right] key的位置跳出循环a[hole] a[right];hole right;//把这个位置挖新坑将坑里的值存起来while (left right a[left] key)left;a[hole] a[left];hole left;//右边挖完左边挖左边找大于基准值的}a[hole] key;//将最开始存下来的基准值填到此时剩下的坑里return hole;
}void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort2(a, left, right);//将区间分成三个部分keyikeyi左keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);//对剩下的区间继续排序
}③前后指针版本
int PartSort3(int* a, int left, int right)
{int prev left;//初始前指针为最左边的元素int cur left 1;//初始后指针为前指针的后一个元素int keyi left;//存下前指针的下标作为基准值下标while (cur right){while (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);
//如果后指针指向的数字大小小于基准值并且前指针的后一个指针不为后指针那么前后指针指向位置的值交换
//当后指针指向的值小于基准值时前指针都会往后走这里的知识涉及到逻辑语句的短路cur;//后指针往后走}Swap(a[prev], a[keyi]);keyi prev;//最后前指针所指向元素的大小一定大于基准值将他们交换此时的基准值左边除了第一个都比它小右边都比它大return keyi;
}void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort3(a, left, right);//将区间分成三个部分keyikeyi左keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);//对剩下的区间继续排序
}3时间复杂度
快速排序是一种类二叉树类型的排序所以它的时间复杂度为O(N*log₂N)计算方法同二叉树
4空间复杂度
递归创建类二叉树空间复杂度为O(log₂N) 下期再见~
