招标网站建设申请报告,济南市建设工程招标投标协会网站,wordpress 链接优化插件,织梦网站导航如何删除文章目录 一、冒泡排序1、定义2、思想及图解3、代码 二、快速排序1、hoare版本2、挖坑法3、前后指针法4、非递归快排5、快速排序优化1#xff09;三数取中选key值2#xff09;小区间优化 三、直接插入排序1、定义2、代码 四、希尔排序1、定义2、图解3、代码 五、选择排序1、排… 文章目录 一、冒泡排序1、定义2、思想及图解3、代码 二、快速排序1、hoare版本2、挖坑法3、前后指针法4、非递归快排5、快速排序优化1三数取中选key值2小区间优化 三、直接插入排序1、定义2、代码 四、希尔排序1、定义2、图解3、代码 五、选择排序1、排序思想2、代码 六、堆排序1、定义2、向上调整建堆排序3、向下调整建堆排序 七、归并排序1、定义2、思想及图解3、代码1递归实现2非递归实现 八、计数排序1、原理2、图解3、代码 九、总结 一、冒泡排序
如需更详细步骤可见冒泡排序
1、定义 冒泡排序(bubble sort)是最基础的排序算法它是一种基础的交换排序。它的原理就像汽水一样汽水中常常有许多小气泡飘到上面。而冒泡排序这种排序算法的每一个元素也可以像小气泡一样根据自身大小一点点地向着数组一端移动。 2、思想及图解
冒泡排序的思想相邻元素两两比较当一个元素大于右侧相邻元素时交换他们的位置当一个元素小于或等于右侧元素时位置不变。
对于以下这个无序的数列用冒泡排序的思想进行排序
冒泡排序单次排序图解 当通过一轮排序之后元素9作为最大的元素移动到了数列的最右端。9是目前有序数列的唯一元素。然后继续对数列进行排序…
整体流程图解 3、代码
//交换
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){//记录交换次数int e 0;for (int j 1; j n-i; j){if (a[j] a[j - 1]){Swap(a[j], a[j - 1]);e;}}//本次没有交换过已经有序if (e 0){break;}}
}时间复杂度O(n2) 空间复杂度O(1)
二、快速排序
如需更详细步骤可见快速排序
1、hoare版本 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后左右子序列重复该过程直到所有元素都排列在相应位置上为止。 算法思想
定义一个keyi存入随机一个数key的下标换到数组首元素这里先直接默认key为数组首元素定义一个left和一个right分别存入数组首元素和尾元素的下标用来移动交换排升序我们让右边right先向左移动找到比key的值小的元素则停下来换到left移动left向右移动找到比key的值大的元素则停下交换下标为left和right的元素重复以上操作直到left与right相遇相等交换key和下标为left的元素此时key的左边都是比它小的数右边都是比它大的数再分别对左右序列进行以上的单趟排序反复操作直到左右序列只有一个或者没有元素时停止操作数列即可有序
hoare版本单趟排序图示 hoare版本代码
//交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//hoare版本
void QuickSort1(int* a, int begin, int end)
{//递归结束条件if (begin end){return;}int keyi begin;int left begin;int right end;//每趟排序直到左右相遇while (left right){//右边先走找到比key值小的while (left right a[right] a[keyi]){right--;}//right找到比key值小的之后换到left走找到比key值大的while (left right a[left] a[keyi]){left;}//交换Swap(a[left], a[right]);}//将key值换到中间Swap(a[keyi], a[left]);//更新keykeyi left;//对左右序列继续排序QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi 1, end);
}整体流程图 2、挖坑法
挖坑法思想
先将第一个数据存在变量key中将此处作为最开始的坑位用下标hole记录然后right开始向前走找到比key值小的元素后停下将此元素放进坑里下标为hole处然后此处变为坑hole变为此时的right然后left开始向后移动找到比key值大的元素后停下将此元素放进坑里下标为hole处然后此处变为坑hole变为此时的left然后又换回right移动如此反复直到left与right相遇left与right相遇的地方一定是坑然后将key放入left与right相遇的位置也就是坑的位置此时hole左边都是小于等于它的右边都是大于等于它的如此单趟排序便结束然后继续对hole左右序列继续反复执行以上操作直到左右序列只有一个或者没有元素时停止操作数列即可有序
挖坑法单趟排序图示 挖坑法代码
//挖坑法
void QuickSort2(int* a, int begin, int end)
{//递归结束条件if (begin end){return;}int left begin;int right end;int key a[left];//坑最初与left一样在开始位置int hole left;//每趟排序直到左右相遇while (left right){//右边先走找到比key值小的while (left right a[right] key){right--;}//将right找到的比key小的元素放进坑中a[hole] a[right];//更新坑的位置hole right;//然后左边走找到比key值大的元素停下来while (left right a[left] key){left;}//将left找到的比key大的元素放进坑中a[hole] a[left];//更新坑的位置hole left;}//将key放入坑中a[hole] key;//对左右序列继续排序QuickSort2(a, begin, hole - 1);QuickSort2(a, hole1, end);
}3、前后指针法
前后指针法思想
定义一个keyi存入随机一个数key的下标换到数组首元素这里先直接默认key为数组首元素定义一个prev为开头元素的下标定义一个cur为prev下一个元素的下标cur下标处的值与key比较直到cur找到比key小的值则停下来prev下标后移一位然后与cur下标处的值交换然后cur后移一位prev相当于前面比key小的那些数的最后一个的下标所以要先后移一位再交换cur继续寻找比key小的值反复执行直到cur的值大于n将key与prev下标处的值交换此时key左边都是小于等于它的右边都是大于等于它的如此单趟排序便结束然后继续对key左右序列继续反复执行以上操作直到左右序列只有一个或者没有元素时停止操作数列即可有序
前后指针法单趟排序图示 前后指针法代码
//交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//前后指针
void QuickSort3(int* a, int begin, int end)
{//递归结束条件if (begin end){return;}int keyi begin;int prev begin;int cur begin 1;//每趟排序直到cur下标大于endwhile (cur end){//cur找比key小的值if (a[cur] a[keyi] prev ! cur){Swap(a[cur], a[prev]);}cur;}//将key换到中间Swap(a[keyi], a[prev]);//更新key的下标keyi prev;//对左右序列继续排序QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi 1, end);
}快速排序是一种不稳定的排序它的时间复杂度为O(N*logN)但最坏可以达到O(N2) 它的空间复杂度为O(logN)
4、非递归快排
以上三种方法都是采用了分治法递归实现的快排其实快速排序也可以非递归实现非递归实现快排需要利用栈来实现
思路
将数组首尾下标存入栈中在循环中依次取出作为left和right对数组进行排序然后对得到的key的左右两边序列也进行相同的操作其中左边为left到keyi-1右边为keyi1到right这些下标的入栈顺序需要看取出的顺序如下面代码中是先取出后面元素下标的所以入栈时要先入后面的因为栈的特点是先入后出。 非递归快排代码
该代码中用到的栈需自己实现C语言实现栈可参考栈的实现
//非递归快速排序
void QuickSortNonR(int* a, int begin, int end)
{//创建一个栈ST st;//初始化栈STInit(st);//插入尾元素下标STPush(st, end);//插入首元素下标STPush(st, begin);//栈为空停下while (!STEmpty(st)){//取出栈顶元素作为leftint left STTop(st);//取出后在栈中删除STPop(st);//取出栈顶元素作为rightint right STTop(st);//取出后在栈中删除STPop(st);int keyi begin;//每趟排序直到左右相遇while (left right){//右边先走找到比key值小的while (left right a[right] a[keyi]){right--;}//right找到比key值小的之后换到left走找到比key值大的while (left right a[left] a[keyi]){left;}//交换Swap(a[left], a[right]);}//将key值换到中间Swap(a[keyi], a[left]);//更新key的下标keyi left;// 当前数组下标样子 [left,keyi-1] keyi [keyi1, right]//右边还有元素按顺序插入right和keyi1if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}//左边还有元素按顺序插入keyi-1和leftif (left keyi - 1){STPush(st, keyi - 1);STPush(st, left);}}STDestroy(st);
}5、快速排序优化
1三数取中选key值
前面三种快速排序的方法起初都要随机选取一个值作为key我们之前是直接默认为数组首元素的这样不够随机容易出现最坏的情况使得它的时间复杂度接近O(N2)所以我们可以写一个函数来选取这个key使得它比较随机而不是直接为首元素。
三数取中
在一个数组最前面、最后面中间这三个位置的数中选出大小处于中间的数
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[right]){if (a[right] a[mid]){return right;}else if(a[mid]a[right]a[mid]a[left]){return mid;}else{return left;}}else{if (a[left] a[mid]){return left;}else if (a[mid] a[left] a[mid] a[right]){return mid;}else{return right;}}
}在快排时用三数取中法选取key值再将它换到数组开头可以有效避免出现最坏的情况大大提升算法效率
2小区间优化
当递归到数据较小时可以使用插入排序使得小区间不再递归分割降低递归次数
三、直接插入排序
1、定义 直接插入排序就是将待排序的记录按照它的关键码值插入到一个已经排好序的有序序列中直到所有的记录都插入完得到一个新的有序序列。 插入排序的思想就像我们平时玩扑克牌理牌时一样将每张牌逐个插入到一个有序的牌的序列里最终所有的牌都是有序的。 2、代码
//插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n-1; i){//end可看作从左至右有序的最后一个数的下标int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}end--;}//此时tmp的值大于或等于下标为end的值所以插入在它的后面a[end1] tmp;}
}当插入第i(i1)个元素时前面的a[0],a[1],…,a[i-1]已经排好序此时用a[i]的排序码与a[i-1],a[i-2],…的排序码顺序进行比较找到插入位置即将a[i]插入原来位置上的元素顺序后移
直接插入排序是一种稳定的排序算法元素集合越接近有序直接插入排序算法的时间效率越高它的时间复杂度为O(n2)空间复杂度为O(1)
四、希尔排序
如需更详细步骤可见希尔排序
1、定义 希尔排序法又称缩小增量法。希尔排序的基本思想是先选定一个整数gap把待排序数列中所有记录分成个gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后缩小gap可以取它的一半重复上述分组和排序的工作。当gap到达1时该数列便已有序。 当gap1时相当于直接插入排序。所以希尔排序可以拆分为预排序和直接插入排序两部分
预排序当gap大于1时预排序可以让大的数更快地到序列后面小的更快到前面gap越大跳的越快越不接近有序gap越小跳的越慢越接近有序直接插入排序gap不断减小当gap为1时相当于直接插入排序进行最后一次直接插入排序后数列便已有序
2、图解
对如下图数列用希尔排序算法进行排序 该数列一共有8个数我们选定最初的gap值为8/24相隔4的数为一组如下图同一组数颜色相同 对每一组排序了之后gap再除2变为2 对每一组排序了之后gap再除2变为1此时相当于直接插入排序 3、代码
//希尔排序
void ShellSort(int* a, int n)
{//gap进入循环后会先除2int gap n ;while (gap 1){gap / 2;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];}else{break;}end - gap;}a[end gap] tmp;}}
}希尔排序是不稳定的它是对直接插入排序的优化因为gap的取值方法不止一种导致希尔排序的时间复杂度很难去计算
五、选择排序
1、排序思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素
2、代码
这里的代码是优化过的同时找最大和最小元素最小的放左边最大的放右边然后对除了两边找出的值外剩下的元素继续进行相同操作直到left不再小于right则有序
//交换
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//选择排序
void SelectSort(int* a, int n)
{int left 0;int right n - 1 ;while (left right){int maxi left;int mini left;for (int i left 1; i right; i){//找区间内最大元素下标if (a[i] a[maxi]){maxi i;}//找区间内最小元素下标if (a[i] a[mini]){mini i;}}Swap(a[left], a[mini]);//如果最大数的下标等于left上一次交换最小数时已经被换到下标为mini元素上if (maxi left){maxi mini;}Swap(a[right], a[maxi]);left;right--;}
}时间复杂度O(N2) 空间复杂度O(1)
六、堆排序
如需更详细步骤可见堆排序
1、定义 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆 1、根据要排什么序建大堆或小堆此时堆顶端的元素就是最值 2、将顶端元素和末尾元素交换此时末尾元素就是有序的剩下的还有n-1个元素 3、将剩下的n-1个元素再次构建成堆然后将堆顶端元素与第n-1个元素互换反复执行便可得到有序数组
2、向上调整建堆排序
使用向上调整算法建堆的堆排序
例如将数组a用堆排序按从小到大排列升序 向上调整算法的前提条件是前面的元素是堆
对于单个结点来说既可以看作一个大堆所以便可以通过向上调整算法依次对数组元素进行调整那进行调整的元素前就一定是堆满足条件 创建好的大堆如下
将堆的顶端元素7和末尾元素2进行交换对除7外剩下的元素进行向下调整重新构建大堆 此时7已经是有序的将元素6和元素3进行交换对除6、7外剩下元素进行向下调整重新构建大堆 此时6、7已经有序将元素5和元素2进行交换对除5、6、7外剩下元素进行向下调整重新构建大堆 此时5、6、7已经有序将元素4和元素2进行交换此时数组已经有序 排序完数组a变为
用向上调整算法建堆的升序的堆排序代码如下
#includestdio.h
#includestdlib.h
#includestdbool.h
typedef int HPDataType;
//交换结点的函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
//向上调整算法(大堆)
void AdjustUp(HPDataType* a, int child)
{//找出双亲的下标int parent (child - 1) / 2;while (child0){//孩子结点比双亲大则交换if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}//向下调整算法(大堆)
void AdjustDown(HPDataType* a, int n, int parent)
{//先默认左孩子是较大的int child parent * 2 1;while (child n){//找出左右孩子中较大的if (child 1 n a[child 1] a[child]){child;}//孩子节点更小则交换if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
//排序
void HeapSort(int* a, int n)
{//向上调整建堆for (int i 1; i n; i){AdjustUp(a, i);}//最尾端数据下标为总数减一int end n - 1;while (end 0){Swap(a[0], a[end]);//对剩余元素进行向下调整AdjustDown(a, end, 0);end--;}
}
建堆的 空间复杂度O(1) 平均时间复杂度O(nlogn)
3、向下调整建堆排序
向下调整建堆排序与向上调整建堆排序不同的地方就在于建堆时用的算法不同建好堆之后的后续操作都是相同的。
还是对上面那个案例我们用向下调整算法建堆
向下调整算法前提条件左右子树必须是堆才能调整 对于这个完全二叉树来说它的倒数第一个非叶子节点2的左子树为4没有右子树可以用向下调整再上一个节点6的左右子树是单个节点也可以看作堆所有我们就可以从倒数第一个非叶子节点也就是最后一个节点的父亲开始向下调整 利用向下调整建好堆之后的后续操作与向上调整建好堆之后的操作一样这里就不再演示
用向下调整算法建堆的升序的堆排序代码更改如下
void HeapSort(int* a, int n)
{向上调整建堆//for (int i 1; i n; i)//{// AdjustUp(a, i);//}// //向下调整建堆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--;}
}利用向下调整建堆的堆排序时间复杂度为O(n)比利用向上调整建堆更优
七、归并排序
如需更详细步骤可见归并排序
1、定义 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 2、思想及图解
归并排序算法有两个基本的操作一个是分解另一个是合并。分解是把原数组划分成两个子数组的过程合并可以将两个有序数组合并成一个更大的有序数组。
将待排序的线性表不断地切分成若干个子表直到每个子表只包含一个元素这时可以认为只包含一个元素的子表是有序表。将子表两两合并每合并一次就会产生一个新的且更长的有序表重复这一步骤直到最后只剩下一个子表这个子表就是排好序的线性表。 3、代码
1递归实现
//归并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{//递归结束条件if (begin end){return;}int mid (begin end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid1, end);// 归并到tmp数据组再拷贝回去int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;int index begin;//begin小于end说明还有两部分都还有数据while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}//由于右边没有数据跳出的上一个循环将左边剩下的数放入tmp数组对应位置while (begin1 end1){tmp[index] a[begin1];}//由于左边没有数据跳出的上一个循环将右边剩下的数放入tmp数组对应位置while (begin2 end2){tmp[index] a[begin2];}// 拷贝回原数组memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}2非递归实现
非递归实现时当gap的值不同时有许多数组的数据个数不适合当前gap访问就会越界比如9个值时当gap1就会访问到下标为9的下标越界所以要在代码中加入解决措施。当第一组右边界越界第二组左边界也一定越界了所以可分为第二组左边界越界和第二组右边界越界两种情况处理。
//非递归归并
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){// 归并到tmp数据组再拷贝回去int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;// 如果第二组不存在这一组不用归并了if (begin2 n){break;}// 如果第二组的右边界越界修正一下if (end2 n){end2 n - 1;}int index i;//begin小于end说明还有两部分都还有数据while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}//由于右边没有数据跳出的上一个循环将左边剩下的数放入tmp数组对应位置while (begin1 end1){tmp[index] a[begin1];}//由于左边没有数据跳出的上一个循环将右边剩下的数放入tmp数组对应位置while (begin2 end2){tmp[index] a[begin2];}// 拷贝回原数组memcpy(a i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}free(tmp);
}时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定
八、计数排序
1、原理
计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。
操作步骤为
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中
2、图解
首先找出数组a的最大值和最小值计算出range 创建一个range大小的数组count在下标为i的位置存储原数组中大小为imin的数的个数 然后按顺序将数据放入原数组中 按照这样便可以将所有数据排好序 3、代码
//计数排序
void CountSort(int* a, int n)
{int min a[0];int max a[0];//找出最大值和最小值for (int i 1; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}//确定建立数组的长度int range max - min 1;int* count (int*)malloc(sizeof(int) * range);//printf(range:%d\n, range);if (count NULL){perror(malloc fail);return;}//初始化数组countmemset(count, 0, sizeof(int) * range);//计数for (int i 0; i n; i){count[a[i] - min];}//排序int j 0;for (int i 0; i range; i){while (count[i]--){a[j] min i;}}
}计数排序在数据范围集中时效率很高但是适用范围及场景有限仅适用于整型排序。
时间复杂度O(Nrange) 空间复杂度O(range) 稳定性稳定
九、总结 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 时空复杂度及稳定性
排序算法时间复杂度空间复杂度稳定性直接插入排序O(N2)O(1)稳定希尔排序O(N1.3)O(1)不稳定选择排序O(N2)O(1)不稳定堆排序O(N*logN)O(1)不稳定冒泡排序O(N2)O(1)稳定快速排序O(N*logN)O(logN)不稳定归并排序O(N*logN)O(N)稳定计数排序O(MAX(N,范围))O(范围)稳定
