商城购物网站建设,如何登陆wordpress后台,动漫网站模板下载,有什么网站可以做电子排序篇(三)----交换排序
1.冒泡排序
基本思想:
通过不断地比较相邻的元素#xff0c;将较大的元素往后移动#xff0c;从而实现排序的目的。
具体的步骤如下#xff1a;
从待排序的数组中选择相邻的两个元素进行比较#xff0c;如果前一个元素大于后一个元素#…排序篇(三)----交换排序
1.冒泡排序
基本思想:
通过不断地比较相邻的元素将较大的元素往后移动从而实现排序的目的。
具体的步骤如下
从待排序的数组中选择相邻的两个元素进行比较如果前一个元素大于后一个元素则交换它们的位置。继续比较下一对相邻的元素重复上述步骤直到将整个数组排序完成。重复执行上述步骤直到没有需要交换的元素即数组已经完全排序。
冒泡排序的特点是每次只比较相邻的两个元素每一轮排序都将最大的元素移动到最后因此称为冒泡。整个排序过程类似于水泡从底部冒到顶部的过程,因此得以闻名. //冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){int exchange 1;for (int j 1; j n - i; j){if (a[j - 1] a[j]){Swap(a[j - 1], a[j]);exchange 0;}}if (exchange)return;}
} 这里面有一个小小的优化,exchange如果在这一趟排序中没有被修改过,代表着这组数据是有序的,因此可以直接return返回.
代码解析:
在给定的冒泡排序函数中参数a是要排序的数组n是数组的长度。算法的核心是两层循环。外层循环控制排序的轮数每一轮都将最大的元素移动到最后。内层循环用于比较相邻的元素并进行交换。内层循环中通过比较a[j-1]和a[j]的大小来判断是否需要交换它们的位置。如果a[j-1]大于a[j]则交换它们的位置并将exchange标志设置为0表示本轮循环有元素交换位置。如果没有发生交换说明数组已经有序可以提前结束排序。外层循环每执行一轮就会将最大的元素移动到最后所以内层循环的范围会逐渐减小。每一轮排序都可以确定一个最大的元素的位置所以外层循环只需要执行n次。
冒泡排序的特性总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
2.快速排序(递归)
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 .
void QuickSort(int* a, int left, int right)
{
// 假设按照升序对array数组中[left, right)区间中的元素进行排序if (right left)return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分//int keyi PartSort1(a, left, right);//int keyi PartSort2(a, left, right);int keyi PartSort3(a, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, keyi-1) 和 [keyi1, right)
// 递归排[left, keyi-1)QuickSort(a, left, keyi - 1);
// 递归排[keyi1, right)QuickSort(a, keyi 1, right);
} 上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像在写递归框架时想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
2.1hoare版本快排 int PartSort1(int* a, int left, int right)
{//三数取中(优化)//int keyi NumBers(a, left, right);//Swap(a[keyi], a[left]);int key left;while (left right){while (left right a[left] a[right]){right--;}while (left right a[left] a[right]){left;}Swap(a[left], a[right]);}Swap(a[left], a[key]);return left;
}代码解析:
首先定义一个变量key用于保存基准值的下标初始值为left。进入一个循环循环条件是left right即左右指针没有相遇。在循环中首先从右边开始找到第一个小于等于基准值的元素的下标将right指针左移直到找到符合条件的元素或者left和right相遇。然后从左边开始找到第一个大于基准值的元素的下标将left指针右移直到找到符合条件的元素或者left和right相遇。如果left right说明找到了需要交换的元素将a[left]和a[right]交换位置。重复步骤3到步骤5直到left和right相遇。最后将基准值a[key]和a[left]交换位置将基准值放在正确的位置上。返回分割点的下标left。
实现了一次快速排序的分割操作将数组分成两部分左边的元素都小于等于基准值右边的元素都大于基准值。然后再通过递归调用这个函数这就是hoare版的快排.
2.2挖坑法 int PartSort2(int* a, int left, int right)
{//三数取中优化//int keyi NumBers(a, left, right);//Swap(a[keyi], a[left]);int key a[left];int hole left;//为第一个坑while (left right){while (left right key a[right]){--right;}a[hole] a[right];hole right;while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}代码解析:
定义一个变量key用于保存基准值初始值为a[left]。定义一个变量hole用于保存空洞的位置初始值为left。进入一个循环循环条件是left right即左右指针没有相遇。在循环中首先从右边开始找到第一个小于基准值的元素的下标将right指针左移直到找到符合条件的元素或者left和right相遇。将a[right]的值赋给a[hole]将空洞的位置移动到right。然后从左边开始找到第一个大于基准值的元素的下标将left指针右移直到找到符合条件的元素或者left和right相遇。将a[left]的值赋给a[hole]将空洞的位置移动到left。重复步骤4到步骤7直到left和right相遇。最后将基准值key放入空洞的位置a[hole]将基准值放在正确的位置上。返回空洞的位置hole。
同样实现了将数组分成两部分左边的元素都小于等于基准值右边的元素都大于基准值。
2.3双指针法 // 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{//三数取中优化//int midi NumBers(a, left, right);//Swap(a[left], a[midi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}代码解析:
定义两个指针prev和cur分别指向left和left1。定义一个变量keyi用于保存基准值的下标初始值为left。进入一个循环循环条件是cur right即cur指针没有越界。在循环中如果a[cur]小于基准值a[keyi]则将prev指针右移一位并交换a[prev]和a[cur]的值保证prev指针之前的元素都小于基准值。将cur指针右移一位。重复步骤4到步骤6直到cur指针越界。最后将基准值a[keyi]和a[prev]交换位置将基准值放在正确的位置上。返回分割点的下标prev。
同样实现了将数组分成两部分左边的元素都小于等于基准值右边的元素都大于基准值。
以上三种方法均可实现快速排序,没有谁优谁劣,挑取自己便于理解的就行
2.4三数取中优化
三数取中是为了选择一个更好的基准值以提高快速排序的效率。在快速排序中选择一个合适的基准值是非常重要的它决定了每次分割的平衡性。
快速排序的基本思想是通过一趟排序将待排序的数据分割成独立的两部分其中一部分的所有数据都比另一部分的小然后再对这两部分分别进行快速排序递归地进行下去直到整个序列有序。
如果每次选择的基准值都是最左边或最右边的元素那么在某些情况下快速排序的效率可能会降低。例如当待排序序列已经有序时如果每次选择的基准值都是最左边或最右边的元素那么每次分割得到的两个子序列的长度差可能会非常大导致递归深度增加快速排序的效率降低。
而通过三数取中的优化可以选择一个更好的基准值使得每次分割得到的两个子序列的长度差更小从而提高快速排序的效率。
具体来说三数取中的优化是选择待排序序列的左端、右端和中间位置的三个元素然后取它们的中值作为基准值。这样选择的基准值相对于最左边或最右边的元素更接近整个序列的中间位置可以更好地平衡分割后的两个子序列的长度从而提高快速排序的效率。
通过三数取中的优化可以减少递归深度提高分割的平衡性使得快速排序的效率更稳定适用于各种不同的输入情况。
//三数取中
int NumBers(int* a, int left, int right)
{int mid (left right) / 2;// left mid rightif (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最大值{return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最小{return left;}else{return right;}}
}2.5小区间优化
小区间优化是指在快速排序中当待排序的子序列的长度小于一定阈值时不再继续使用快速排序而是转而使用插入排序。
void QuickSort(int* a, int left, int right)
{if (right left)return;if(right - left 1 10){int keyi PartSort3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}else{InsertSort(a left,right - left 1);}
}小区间优化的好处
减少递归深度使用插入排序来处理较小的子序列可以减少递归的深度从而减少了函数调用的开销。提高局部性插入排序是一种稳定的排序算法它具有良好的局部性可以充分利用已经有序的部分序列。对于较小的子序列插入排序的效率更高。减少分割次数对于较小的子序列使用插入排序可以减少分割的次数。快速排序的分割操作需要移动元素而插入排序只需要进行元素的比较和交换因此在较小的子序列中使用插入排序可以减少分割操作的次数。
小区间优化可以在一定程度上提高快速排序的性能。它通过减少递归深度、提高局部性和减少分割次数来优化算法的效率特别适用于处理较小的子序列。
3.快速排序(非递归)
这里需要借助栈的来实现非递归.关于栈详情见:数据结构剖析–栈
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(st);StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)){int begin StackTop(st);StackPop(st);int end StackTop(st);StackPop(st);int keyi PartSort3(a, begin, end);if (keyi 1 end){StackPush(st, end);StackPush(st, keyi 1);}if (begin keyi - 1){StackPush(st, keyi - 1);StackPush(st, begin);}}StackDestroy(st);
}代码解析:
将整个序列的起始和结束位置入栈。然后进入循环不断从栈中取出子序列的起始和结束位置。在每次循环中通过PartSort3函数将当前子序列分割成两部分并得到基准值的下标keyi。如果基准值右边的子序列长度大于1则将右边子序列的起始和结束位置入栈。如果基准值左边的子序列长度大于1则将左边子序列的起始和结束位置入栈。循环继续直到栈为空表示所有的子序列都已经排序完成。
通过使用栈来模拟递归的过程非递归实现避免了递归调用的开销提高了快速排序的效率。
快速排序的特性总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定
