网站建设wap站,中国文化网站建设策划书,湖南网站制作方案,企业品牌vi设计公司文章目录 插入排序直接插入排序希尔排序 选择排序选择排序堆排序升序 交换排序冒泡排序快速排序递归hoare版本挖坑法前后指针版本 非递归Hoare挖坑法前后指针 快排的优化三数取中法选key递归到小的子区间时#xff0c;可以考虑使用插入排序 归并排序递归实现非递归实现 排序算… 文章目录 插入排序直接插入排序希尔排序 选择排序选择排序堆排序升序 交换排序冒泡排序快速排序递归hoare版本挖坑法前后指针版本 非递归Hoare挖坑法前后指针 快排的优化三数取中法选key递归到小的子区间时可以考虑使用插入排序 归并排序递归实现非递归实现 排序算法复杂度以及稳定性 插入排序
直接插入排序 直接插入排序是一种简单的插入排序法其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 可以理解为一遍摸扑克牌一边进行排序 在待排序的元素中假设前面n-1(其中n2)个数已经是排好顺序的现将第n个数插到前面已经排好的序列中然后找到合适自己的位置使得插入第n个数的这个序列也是排好顺序的。 按照此法对所有元素进行插入直到整个序列排为有序的过程称为插入排序 当插入第n个元素时前面的n-1个数已经有序用第n个数与前面的n-1个数比较我们将第n个数假设为tmp ,也就是说将tmp插入到[0 ,end] 的区间中 第一种情况如果tmp比end大就放在end后面 第二种情况如果tmp比end小但是比数组前面的几个数据大,插入之后tmp之后的数据就往后挪动 第三种情况如果tmp比数组所有元素都小,所有数据都需要挪动,end就得挪动到数组下标为-1的位置才结束 动图演示
void InsertSort(int* a , int n )
{for (int i 1; i n ; i){//一趟插入排序 int tmp a[i];int end i-1; //end是数组下标while (end 0){//如果tmp比end小但是比数组前面的几个数据大,插入之后tmp之后的数据就往后挪动if (tmp a[end]){a[end 1] a[end];//往后挪动end--;}else{break;}}//如果tmp比数组所有元素都小,所有数据都需要挪动,end就得挪动到数组下标为-1的位置才结束//如果tmp比end大就放在end后面a[end 1] tmp;//包含上述两种情况}
}时间复杂度O(N^2) 空间复杂度O(1) 希尔排序 第一步先选定个小于n的数字作为gap将所有距离为gap的数分为一组进行预排序,预排序的目的就是使数组接近有序与直接插入排序相同直接插入排序的间隔为1预排序的间隔变为gap了 再选一个小于gap的数作为新的gap重复第一步的操作 当gap的大小减到1时就相当于整个序列被分到一组进行一次直接插入排序排序完成 举例分析一下: 我们用序列长度的一半作为第一次排序时gap的值此时相隔距离为5的元素被分为一组共分了5组每组有2个元素然后分别对每一组进行直接插入排序 gap的值折半此时相隔距离为2的元素被分为一组共分了2组每组有5个元素然后再分别对每一组进行直接插入排序 gap的值再次减半此时gap减为1即整个序列被分为一组进行一次直接插入排序。 为什么是选一个小于gap的数作为新的gap也就是要gap由大变小 gap越大数据跳跃的幅度越大数据挪动得越快gap越小数据跳跃的幅度越小数据挪动得越慢。前期让gap较大可以让数据更快得移动到自己对应的位置附近减少挪动次数,提高算法效率 void ShellSort(int* a, int n) // 希尔排序
{int gap n;while (gap 1){//一趟排序gap / 2;for (int i gap; i n; i gap){int end i - gap; //有序序列最后一个元素的下标int tmp a[end gap];while (end 0){//如果tmp比end小但是比数组前面的几个数据大,插入之后tmp之后的数据就往后挪动if (tmp a[end]){a[end gap] a[end]; //往后挪动 end - gap;}else{break;}}//tmp比数组中所有数据都小 ,一直往后挪动 end挪到了-1//tmp a[end] a[end gap] tmp;}}
}选择排序
选择排序 基本思想 : 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 在元素集合array[i]到array[n-1]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换 在剩余的array[i] 到 array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素 注意特殊情况 如果Maxi在left位置当a [ Mini ] 和 a [ left ] 互换时此时Maxi的位置就变成了Mini 我们添加一个判断条件 判断left Maxi 修正Maxi 防止Maxi更改 以升序为例做分析 经过第一躺交换最小的元素排在了数组的第一个位置 经过第二趟交换 第二小的元素已经到了数组第二个元素位置 经过第三趟排序 第三小的元素已经排在了第三个位置 最后一趟排序 数组已经有序了 动图演示
代码实现
void SelectSort(int* a, int n)//选择排序
{//升序 int left 0, right n - 1;while (left right){//选出最大最小数的下标 int Mini left;int Maxi left;//一趟 for (int i left1 ; i right; i){if (a[i] a[Mini]){Mini i; // 更新Mini}if (a[i] a[Maxi]){Maxi i; //更新Maxi }}// Mini和左边交换Swap(a[left], a[Mini]);// Maxi 在左边 Maxi 被换成Mini 修正Maxiif (left Maxi){Maxi Mini; }//Maxi与右边交换Swap(a[right], a[Maxi]);left;right--;}
}选择排序效率较低,实际中很少使用 时间复杂度O(N^2) 空间复杂度O(1) 稳定性不稳定 堆排序
排降序 建立小堆 排升序 建立大堆
升序 向上调整建堆,时间复杂度为O(N* longN) 使用向上调整算法建大堆将数组建成大堆后,此时堆顶元素是最大的 将堆顶元素和最后一个元素进行交换,这样最大的元素就到了数组最后一个元素,对剩下的元素使用向下调整 当下一次向下调整时我们不管这个处在数组最后一个位置的最大元素有点类似堆的删除 此时第二大的元素来到的堆顶 堆顶元素继续与最后一个元素进行交换注意第一个交换过去的最大的元素已经不在范围内了 依次类推 升序就完成了 void HeapSort(int* a, int n){//向上调整建堆for (int i 0; i n; i){AdjustUp(a, i);}//向下调整排序int end n - 1;// end 是最后一个元素的下标while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}}int main(){int a[10] { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };HeapSort(a, 10);return 0; }向下调整建堆的前提是左右子树都是堆 从倒数第一个非叶子节点开始倒着调整,如何找到倒数第一个非叶子节点通过最后一个节点的父节点来找到 , 那为什么要找倒数第一个非叶子节点 因为倒数第一个非叶子节点的左右子树都满足大堆或小堆的条件 void HeapSort(int* a, int n){//向下调整建堆for (int i (n-1-1)/ 2; i 0; i--) // n-1是最后一个节点的下标n-1-1)/2 通过下标找到最后一个节点的父节点{AdjustDown(a,n , i);}//向下调整排序int end n - 1; //end 是最后一个元素的下标 while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}}int main(){int a[10] { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };HeapSort(a, 10);return 0; }交换排序
冒泡排序
以升序为例 冒泡排序该排序的命名非常形象即一个个将气泡冒出。冒泡排序一趟冒出一个最大或最小值 如果前一位的数字大于后一位的那么这两个数字交换位置因此最大的数字在第一轮循环中不断像一个气泡一样向上冒 动图演示 代码实现 :
void BubbleSort(int* a, int n)
{for (int i 0; i n-1; i){//一趟 for (int j 0; j n-1 - i; j){assert(j n-1);if (a[j] a[j 1]){assert(j 1 n);Swap(a[j], a[j 1]);}}}
}冒泡排序 时间复杂度 O(N^2) 快速排序
递归
hoare版本 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 单趟排序 一趟下来的结果是让Key左边的数据全部都小于KeyKey右边的数据全部都大于Key 就相当于Key这个基准值被排好序了快速排序的单趟排序本质上就是在排一个数的顺序 步骤 1 选最左边的或者最右边的当作基准值Key 2 定义一个Left和一个RightRight从右向左走, 若Right遇到小于Keyi的数则停下,Left从左向右开始走直到Left遇到一个大于Keyi的数时将Left和Right的内容交换 Right再次开始走如此进行下去直到Left和Right最终相遇此时将相遇点的内容与key交换即可 需要注意的是若选择最左边的数据作为基准值Key则需要Right先走若选择最右边的基准值数据作为基准值Key则需要Left先走 注意Left 和Right相遇位置一定比Key小 3 然后我们再将Key的左序列和右序列再次进行这种单趟排序如此反复操作下去 其实就是一个递归 如果选择最左边的数据作为基准值Key ,为什么不能Left先走呢 快排hoare版本 单趟动图演示 代码实现
void QuickSort(int* a, int left , int right ) // Hoare 版本
{int begin left;int end right;//升序 // 从左向右走 , 从右向左走 int Keyi left; // 最左边为基准值 if (left right)return; while (left right ){//单趟排序 //右边找小 while (right left a[right] a[Keyi]){right--;assert(right 0);}//左边找大while (left right a[left] a[Keyi]){left;assert(left right);}Swap(a[left], a[right]);}Swap(a[Keyi], a[left]); //Left和Right最终相遇此时将相遇点的内容与key交换即可//递归 类似二叉树的前序遍历 // [begin , Keyi-1 ] Keyi [Keyi1 , end] Keyi left;assert(Keyi - 1 0);QuickSort( a, begin, Keyi -1);QuickSort(a, Keyi1, end );}快排时间复杂度 如果每趟排序所选的Key都正好是该序列的中间值即单趟排序结束后Key位于序列正中间那么快速排序的时间复杂度就是O(NlogN) 挖坑法
以升序为例 单趟排序一趟下来的结果是让Key左边的数据全部都小于KeyKey右边的数据全部都大于Key 步骤(在最左边挖坑为例 1 选出最左边或者最右边的一个数 ,存放在Key变量中并且在该数据位置形成一个坑 2 定义一个Left和一个RightLeft从左向右走找比Key大的数 Right从右向左走找比Key小的数。注意 如果是在最左边挖坑则需要Right先走如果是在最右边挖坑则需要Left先走 3 因为是以最左边挖坑为例 ,所以是Right 先走 , 在Left和Right 遍历的过程中,如果Right遇到小于Key的数则将该数放到最左边的坑位并在Right当前位置形成新的坑位这时Left再向右边走若遇到大于Key的数则将其抛入到刚才在Right位置形成的一个坑位然后在Left 当前位置形成一个坑位如此循环下去直到最终Left和Right相遇而且Left和Right相遇一定相遇在坑位处 ,这时将Key填在坑位即可。 Key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时便停止操作 单趟动图演示 代码实现
//快排挖坑法
void QuickSort(int* a, int left, int right)
{int begin left;int end right;if (left right)return; // 升序 最左边挖坑 右边先走//选最左边为 Key,并形成hole int holeleft;int Key a[left];while (left right){//单趟排序 //right 找小 while (left right a[right] Key){right--;}//找到比Key小的数 放进最左边的坑位 并在right当前位置形成新的坑位a[hole] a[right];hole right;assert(hole 0);//left 找 大 while (right left a[left] Key){left;}// 找到比Key大的数 放进right当时形成的坑位 并在Left当前位置形成新的坑位 a[hole] a[left];hole left;assert(hole 0);}//直到最终Left和Right相遇这时将Key填在坑位即可。assert(hole 0);a[hole] Key;//递归 //递归 类似二叉树的前序遍历 // [begin , Key-1 ] Key [Key1 , end] Key left;assert(Key - 1 0);QuickSort( a, begin, Key -1);QuickSort(a, Key1, end );}前后指针版本
以升序为例 单趟排序一趟下来的结果是让Key左边的数据全部都小于KeyKey右边的数据全部都大于Key 步骤(以最左边为Key 为例 1 选最左边的或者最右边的当作基准值Key 2 定义一个prev 和 cur prev指针指向序列开头 prev 从左往右遍历 ,cur指针指向prev1, cur从左往右遍历 。 3、若cur指向的内容小于Key则prev先然后交换prev和cur的值然后cur若cur的值大于key则cur指针直接。如此进行下去直到cur指针越界此时将Key和prev指针指向的内容交换即可。 然后我们再将Key的左序列和右序列再次进行这种单趟排序如此反复操作下去 其实就是一个递归 单趟动图演示
代码实现
int PartSort2(int* a, int left, int right) //前后指针法
{int begin left;int end right;//升序 // 单趟排序int prev left;int cur prev 1;int Keyi left; //选最左边为Key //cur 找比Key小的 while (cur right) //cur未越界就继续 {//如果cur找到比Key小 往后if (a[cur] a[Keyi] prev ! cur) //prev !cur , 有可能数组前几个元素比Key小但是没必要交换{Swap(a[cur], a[prev]); //交换 }cur; }assert(cur right1); Swap(a[prev], a[Keyi]);/*递归 类似二叉树的前序遍历 [begin , Keyi-1 ] Keyi [Keyi1 , end] */Keyi prev;assert(Keyi - 1 0);return prev;
}
void QuickSort(int* a, int left, int right)
{//递归 if (left right)return;int keyi PartSort2(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}非递归 将一个用递归实现的算法改为非递归时一般需要借用一个数据结构那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本 Hoare版本、挖坑法和前后指针法 这三种排序都只写单趟 后面再写一个非递归的快速排序在函数内部调用单趟排序的函数 Hoare
单趟排序代码实现
//Hoare版本单趟排序
int PartSort1(int* a, int left, int right)
{int keyi left;//key的下标while (left right){//right走找小while (left righta[right] a[keyi]){right--;}//left先走找大while (left righta[left] a[keyi]){left;}if (left right){Swap(a[left], a[right]);//交换left和right的值}}int meeti left;//L和R的相遇点Swap(a[keyi], a[meeti]);//交换key和相遇点的值return meeti;//返回相遇点即key的当前位置
}
挖坑法
单趟排序代码实现
//挖坑法单趟排序
int PartSort2(int* a, int left, int right)
{int key a[left];//在最左边形成一个坑位while (left right){//right向左找小while (left righta[right] key){right--;}//填坑a[left] a[right];//left向右找大while (left righta[left] key){left;}//填坑a[right] a[left];}int meeti left;//L和R的相遇点a[meeti] key;//将key抛入坑位return meeti;//返回key的当前位置
}
前后指针
单趟排序代码实现
//前后指针法单趟排序
int PartSort3(int* a, int left, int right)
{int prev left;int cur left 1;int keyi left;while (cur right)//当cur未越界时继续{if (a[cur] a[keyi] prev ! cur)//cur指向的内容小于key{Swap(a[prev], a[cur]);}cur;}int meeti prev;//cur越界时prev的位置Swap(a[keyi], a[meeti]);//交换key和prev指针指向的内容return meeti;//返回key的当前位置
}
快排的优化
三数取中法选key 如果这个序列是非常无序快速排序的效率是非常高的 ,一旦序列有序 每次选取最左边或是最右边的数作为基准值Key时间复杂度就会从O(N*logN)变为O(N^2),这样快排的效率极低 也就是说影响快排时间复杂度就是基准值Key的选取如果选取的Key离中间位置越近则效率越高 为了解决这个问题 ,也就出现了三数取中 : 三数取中当中的三个数指的是最左边的数、最右边的数以及中间位置的数。 三数取中就是取这三个数当中值的大小居中的那个数作为该趟排序的Key 因为它离中间位置最近。这就确保了我们所选取的数不会是序列中的最左边的数、最右边的数 代码实现
//三数取中 ,得到中间元素的下标
int GetMiddleIndexi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[right] a[mid]){return mid;// a[right] a[mid] a[left]}// a[mid]a[right] 此时a[mid]是最大的 只需要比较a[left] ,a[right] else if (a[left] a[right])// a[mid] a[left] a[right] {return left;}else //a[left] a[right]{return right; // a[mid] a[right] a[left]}}else //a[left] a[mid]{if (a[mid] a[right]){return mid;}//a[mid] a[right] ,此时a[mid]已经是最小的 只需要比较a[left] 和a[right]else if (a[left] a[right]) // a[left] a[right] a[mid] {return right; }else // a[left] a[right]{return left; //a[right] a[left] a[mid ]}}}递归到小的子区间时可以考虑使用插入排序
归并排序 归并排序是采用分治法的一个非常典型的应用。其基本思想是将已有序的子序合并从而得到完全有序的序列即先使每个子序有序再使子序列段间有序 动图演示
递归实现
核心步骤 分解得到子序列 如何得到有序的子序列 ? 序列分解到只有一个元素或是没有元素时就可以认为是有序了 然后合并两个有序的子序列 ,思路与Leetcode. 88合并两个有序数组 相似 ,依次比较 较小值尾插到tmp数组中 创建一个与待排序列大小相同的tmp数组 ,合并完毕后再将tmp数组里的数据拷贝回原数组 最后将tmp 数组释放 。 代码实现 void _MergeSort(int* a, int left, int right, int * tmp)
{int mid (left right) / 2;//分割// [begin , mid] [mid1 , end ]int begin left;int end right; if (begin end)//序列分解到只有一个元素或是没有元素时就可以认为是有序了return;_MergeSort(a, begin, mid, tmp); //end-begin1 是元素个数 _MergeSort(a, mid 1, end, tmp);//归并 ——类似合并两个有序数组 ,[begin , mid] [mid1 , end ]int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin; //不能取0 , 两段有序区间不一定是从头开始的区间 while (begin1 end1 begin2 end2 ) {if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//begin1 先走完 begin2还没有走完,begin2尾插到tmp数组后面while (begin2 end2 ){tmp[i] a[begin2];}//begin2 先走完 begin1还没有走完, begin1尾插到tmp数组后面 while (begin1 end1){tmp[i] a[begin1];}//将tmp数组拷贝到原数组中 memcpy(abegin, tmpbegin, sizeof(int*) * ( right- left 1));
}
void MergeSort(int* a , int left , int right , int *tmp )
{//申请一个与原数组大小的tmp数组 tmp (int*)malloc(sizeof(int) * (right -left 1 ) );//归并_MergeSort( a, left, right , tmp);//释放tmp 数组 free(tmp);}tmp 和 a的后面为什么都要加begin ? 如图所示 非递归实现 递归实现的缺点就是会一直调用栈帧而栈帧内存往往是很小的。所以我们尝试着用循环的办法去实现也就是用非递归的方式去实现 但是非递归需要处理几个边界条件 和递归的区别就是递归要将区间一直细分要将左区间一直递归划分完了再递归划分右区间而借助数组的非递归是一次性就将数据处理完毕并且每次都将下标拷贝回原数组 归并排序的非递归基本思路是将待排序序列a[0…n-1]看成是n个长度为1的有序序列将相邻的有序表成对归并 非递归的核心就是需要控制每次参与合并的元素个数使序列变为有序 如果排序的数是奇数就会出现一些越界的情况需要特殊处理 end1越界begin2 和end2绝对也越界了 那就不对end1后面的进行归并 举例 begin2 和end2越界,那不需要对begin2和end2之间的数进行归并 举例 end2 越界还是需要归并修正end2就可以了 举例 void MergeSort(int* a,int n )
{int* tmp (int*)malloc(sizeof(int) * (n ) );if (tmp NULL){printf(malloc fail);exit(-1);}int gap 1;while (gapn){//归并for (int i 0; i n; i 2 * gap){//归并 ——类似合并两个有序数组 ,[begin , end1] [begin2 , end2 ]int begin1 i, end1 i gap - 1;int begin2 i gap - 1 1, end2 i 2 * gap - 1; //从图中分析可得int index i;printf([%d %d] [%d %d] , begin1, end1, begin2, end2);/*end1 和begin2越界*/if (end1 n || begin2 n){break;}//end2越界,修正if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}//begin1 先走完 begin2还没有走完,begin2尾插到tmp数组后面while (begin2 end2){tmp[index] a[begin2];}//begin2 先走完 begin1还没有走完, begin1尾插到tmp数组后面 while (begin1 end1){tmp[index] a[begin1];}//将tmp数组拷贝到原数组中 memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
}归并排序时间复杂度 每一层归并排序的消耗是O(N) ,有 log层 所以归并排序的时间复杂度 O(N * logN) 排序算法复杂度以及稳定性 稳定的排序有直接插入排序、冒泡排序、归并排序 不稳定的排序有希尔排序、选择排序、堆排序、快速排序、计数排序 如果你觉得这篇文章对你有帮助不妨动动手指给点赞收藏加转发给鄃鳕一个大大的关注 你们的每一次支持都将转化为我前进的动力
