黑龙江网站建设费用,电商网站建设关键词优化,重庆行业网站建设,视频制作价格明细目录
前言#xff1a;
冒泡排序
冒泡排序代码实现
冒泡排序特性总结
快速排序
单趟排序hoare版本
单趟排序挖坑法
单趟排序快慢指针法 快速排序整体概览
快排的优化
三数取中法选key
小区间优化 前言#xff1a; 上文介绍了直接插入排序#xff0c;希尔排序…目录
前言
冒泡排序
冒泡排序代码实现
冒泡排序特性总结
快速排序
单趟排序hoare版本
单趟排序挖坑法
单趟排序快慢指针法 快速排序整体概览
快排的优化
三数取中法选key
小区间优化 前言 上文介绍了直接插入排序希尔排序选择排序堆排序并对四种排序进行了详尽的探讨本文将以排序的基本思想代码实现和各种排序的特性总结三个角度继续分析冒泡排序快速排序 冒泡排序 冒泡排序的基本思想 将待排序的序列从前向后依次比较相邻元素的值如果逆序则交换 升序将数组中相邻元素从前往后依次进行比较如果前一个元素比后一个元素大则交换一趟下来后最大元素就在数组的末尾 降序将数组中相邻元素从前往后依次进行比较如果前一个元素比后一个元素小则交换一趟下来后最小元素就在数组的末尾 具体步骤如下 比较待排序序列中相邻的两个元素如果发现左边的元素比右边的元素大则交换这两个元素每一对相邻的两个元素重复第一步的动作从左至右依次执行最后的元素一定是最大的元素由于最大的元素位于数组尾元素的位置下一趟两两比较的范围为待排序序列的首元素到 倒数第二个元素所处的位置这段范围成为新的待排序序列重复步骤1步骤2持续以上步骤 1 步骤 2 步骤 3 的工作每重复一次需要排序的序列中少一个最右边的元素直到没有任何一对数字需要比较排序 ...... 冒泡排序代码实现
void bubblesort(int arr[], int n)
{// 外层循环控制冒泡排序的趟数int i 0;for (i 0; i n - 1; i){//内层循环控制要比较元素的个数int j 0;for (j 0; j n - i - 1; j){int temp 0;if (arr[j]arr[j 1]){temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}冒泡排序特性总结
1.时间复杂度
冒泡排序的平均 时间复杂度是O(n^2)最好时间复杂度是O(n)最坏时间复杂度是O(n^2) 2. 空间复杂度 额外开辟的空间为常数个所以空间复杂度为O(1) 3.算法稳定性 冒泡排序是一种稳定的排序算法即相等元素的相对位置在排序前后不会发生改变 快速排序 快速排序的基本思想 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后对左右子序列分别递归地进行快速排序直到所有元素都排列在相应位置上为止 单趟排序hoare版本 思路如下 1. 选取待排序序列最左边元素作为基准值key定义两个指针left和right分别指向待排序序列的最左侧和最右侧right从右向左走left 从左向右走 2.right先走right指针找比基准值key小的数left后走 left找比基准值key大的数找到后将两个数交换位置 3. 当left指针与right指针相遇时将相遇位置的值与基准值key进行交换 void swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}
//单趟排序hoare版本
int PartSort(int* a, int left, int right)
{int keyi left;//选取左边作为基准值则右边先走while (left right)//left与right相遇,左边找大右边找小的循环终止{//右边找小while (leftright a[right] a[keyi]){right--;}//左边找大while (leftright a[left] a[keyi]){left;}//交换swap(a[left], a[right]);}swap(a[keyi], a[left]);return left;
} 思考: 为什么left与right相遇位置处的数值比key要小 left与right相遇有如下俩种情形 相遇的第一种情形right动left不动,相遇位置为left位置,left位置与前一个right位置进行了交换,交换之后left位置比key小 相遇的第二种情形right不动left动,相遇位置为right位置,此时left找大没有找到与right相遇,而right位置一定比key小 思考为什么左边取基准值key,右边先走 保证当left与right相遇时相遇位置小于基准值 right 停下时left 与 right 相遇由于right 找比 key小的值所以此时 right 的位置一定比key小left 停下时right 与 left 进行交换交换后 left 指向的值比 key 小此时 right 遇到 left 的位置一定比key小 单趟排序挖坑法 思路如下 1. 选择数组第一个数作为基准数,基准数的位置形成一个坑位 2. 定义两个指针left与right分别指向待排序序列的第一个数和最后一个数 3. 从right开始向前遍历,找到第一个小于基准数的数a[right]将其赋值给a[left],a[right]成为一个新的坑位 4. 从left开始向后遍历,找到第一个大于基准数的数a[left]将其赋值给a[right],a[left]成为一个新的坑位 5. 重复步骤3和4直到left right 6. 将基准数填入最后一个坑中,a[left]key //单趟排序挖坑法
int PartSort(int* a, int left, int right)
{int key a[left];int hole left;while (left right){//右边先走while (left right a[right] key){right--;}a[hole]a[right];hole right;//左边再走while (left righta[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}
单趟排序快慢指针法 思路如下 1. 选取待排序序列的第一个元素作为基准值key 2. 定义两个指针prev和cur,prev指针指向序列开头,cur指针指向prev指针的后一个位置 3. 从cur开始向前遍历如果遇到比key小的元素就将prev指针向后移动一位并交换prev和cur指向的元素 4. 遍历结束后将key与prev指向的元素交换位置此时prev指向的位置就是key的最终位置 //单趟排序前后指针法
int PartSort(int* a, int left, int right)
{int keyi left;int prev left;int cur prev 1;while (cur right){//(prev)!cur为了防止prev与cur指向相同数值,此时交换毫无意义;if (a[cur] a[keyi](prev)!cur){swap(a[cur], a[prev]);}cur;}swap(a[keyi], a[prev]);return prev;
} 快速排序整体概览
快速排序首先选取基准值key将待排序序列分为两个子序列左子序列放比基准值小的数右子序列放比基准值大的数然后再将子序列以以上方式同样分割直到数组有序下图单趟排序采取hoare版本
经过一趟hoare排序区间被划分为[begin, keyi-1] U keyi U [keyi1, end] 单趟排序一次就会唯一确定一个元素来到最终排序所确定的位置 先递归排序左子序列[begin, keyi-1] , 再递归排序右子序列[keyi1, end]类似二叉树前序遍历 根据上图可得出递归终止条件为区间不存在(beginend)或者只有一个元素(beginend)
void QuickSort(int*a, int begin, int end)
{//递归终止的条件//1.区间不存在(beginend)或者只有一个元素(beginend)if (begin end)return;int keyi PartSort3(a, begin, end);// 一趟排序原排序区间划分为如下三部分//[begin keyi-1]U[keyi]U[keyi1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
快排的优化
三数取中法选key 若选取的基准值key是序列中最大或最小的数值则快速排序的递归深度会非常深排序效率会很低若是一个有序数组使用快速排序则递归深度为n单趟排序也为n时间复杂度为O(n^2) 假定待排序序列的左下标left , 右下标right左右下标所对应的中间下标 midi(leftright)/2,取三个下标所对应的值的中间值为基准值key可以防止快排出现最差情形 //三数取中法选keyi keyi为中间值的下标
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}//mid为最小值else if (a[left] a[right]){return right;}else{return left;}}else{if (a[mid] a[right]){return mid;}//mid为最大值else if (a[left]a[right]){return left;}else{return right;}}
}
小区间优化 由于快速排序是递归实现的而每一次函数调用均需要开辟函数栈帧当递归到最后几层时此时数组中的值其实已经接近有序最后几层的函数调用会极大占用函数栈帧所开辟的空间 假设数组大小N10即二叉树节点个数N10 10个数值递归了3~4层而最后三层占据比例为87.5%调用函数的次数就越多开辟函数栈帧的消耗越大导致效率下降代价太大在递归分割过程中当区间较小时不再递归分割排序序列在递归分割过程中子序列已经接近有序插入排序每一次单趟排序都只向前遍历到最大值之后一共执行n次若数组有序则总共只执行n次最差情况下每次都只是从i遍历到0下标综合考虑是执行次数最优故选择直接插入排序进行优化 void QuickSort(int* a, int begin, int end)
{if (begin end)return;// 小区间优化小区间不再递归分割排序降低递归次数if ((end - begin 1) 10){int keyi PartSort(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);}
}
