海口网站建设方案咨询,frp做网站,黑龙江省建设安全协会网站,河北三河建设局网站#x1f308;个人主页#xff1a;Yui_ #x1f308;Linux专栏#xff1a;Linux #x1f308;C语言笔记专栏#xff1a;C语言笔记 #x1f308;数据结构专栏#xff1a;数据结构 文章目录 1 交换排序1.1 冒泡排序1.2 快速排序1.2.1 hoare版本1.2.2 挖坑法1.2.3 前后指针…个人主页Yui_ Linux专栏Linux C语言笔记专栏C语言笔记 数据结构专栏数据结构 文章目录 1 交换排序1.1 冒泡排序1.2 快速排序1.2.1 hoare版本1.2.2 挖坑法1.2.3 前后指针版本 1 交换排序
基本思想所谓交换就是根据序列中的两个记录键位的比较结果来交换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
1.1 冒泡排序 冒泡排序的特点就是从前到后两两比较找到最大的数放在数组的末尾。因为已经找到数组最大元素并放置在末尾也就是说最大元素已经放置在最终的位置我们接下来就是把末尾提前来来一次找到数组中次大的元素以此类推将数组彻底排序。
#include stdio.h
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 - 1; i){int flag 1;for (int j 0; j n - i - 1; j){if (a[j] a[j 1]){swap(a[j], a[j 1]);flag 0;}}if (flag)break;}
}
int main()
{int arr[10] { 0,9,8,7,6,5,4,3,2,1 };//slectsort(arr, 10);bubblesort(arr, 10);for (int i 0; i 10; i){printf(%d , arr[i]);}return 0;
}
//打印结果
/*
0 1 2 3 4 5 6 7 8 9
*/冒泡排序总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
1.2 快速排序
快速排序是Hoare在1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序的元素序列中的某元素作为基准按照该排序码将待排序序集分割成两子序列左子序列中所有元素均小于其基准值右子序列中的所有元素均大于基准值然后左右子序列重复该过程直到所有元素都排列在相应位置上为止。 下面会给出快速排序递归实现的主框架发现于二叉树前序遍历的逻辑非常像大家在写递归框架时可以想想二叉树前序遍历的过程快速写成来。后续只需要分析如何对区间中的数据进行划分就可以了。
//假设按照升序对arr数组中的[left,right]区间中的元素进行排序
void quicksort(int* a, int left,int right)
{if (left right)return;//按照基准值对arr数组的[leftright]区间中的元素进行划分int mid PartSort1(a, left, right);//划分成功后以mid为边界形成左右两部分[left,mid-1][mid1,right]//递归排[leftmid-1]quicksort(a, left, mid - 1);//递归排[mid1,right]quicksort(a, mid 1, right);
}将区间按照基准值划分为左右部分的常见方式
1.2.1 hoare版本 通过动图我们可以发现hoare版本的做法就是先确立一个基准值key的坐标然后定义两个指针一左一右左指针找大于a[key]的右指针找小于a[key]的找到后交换左右的数据一直进行到左右指针相遇相遇后就把a[key]和左右指针相遇的位置的数据交换。如此一来就做到了把a[key]放到数组的最终位置因为此时a[key]的左边都是小于它的数右边都是大于它的数不就是a[key]的最终位置嘛。 提问为什么最终左右指针相遇时的数据一定小于a[key]? 回答这就关系到左右指针谁先走的问题。当我排升序的时候一定要让右指针先走右指针是找小嘛。在它们相遇前会存在两种情况
左指针去与右指针相遇因为右指针是先走的同时右指针又是找小于a[key]的值所以如果是左指针去与右指针相遇此时的右指针移动指向了一个小于a[key]的值。右指针去与左指针相遇因为右指针先走左指针就会有两种情况还没走指向a[key]走过了走过了然后于右指针交换数据导致指向小于a[key]的数据。当右指针与左指针相遇时的数据还是小于a[key]的数据 如此一来就说明了最终左右指针相遇时的数据一定小于a[key]
//hoare版本
int PartSort1(int* a, int left, int right)
{int key left;while (left right){while (right left a[right] a[key])right - 1;while (right left a[left] a[key])left 1;swap(a[left], a[right]);}swap(a[left], a[key]);return left;
}优化 这种情况有个致命的缺陷当数组接近有序时效率就会退化为O(N^2)。如图所示
为了解决这个问题我们在选择基准值的时候可以不选择数组的第一个数字而是选择数组中大小适中的元素。我们把这个方法叫做三数取中法。 修改后的版本
//三数取中
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;else{if (a[left] a[right])return right;elsereturn left;}}else//leftmid{if (a[mid] a[right])return mid;else//midright{if (a[left] a[right])//midleftrightreturn left;elsereturn right;}}
}//hoare版本
int PartSort1(int* a, int left, int right)
{int mid GetMidi(a, left, right);swap(a[mid], a[left]);int key left;while (left right){while (right left a[right] a[key])right - 1;while (right left a[left] a[key])left 1;swap(a[left], a[right]);}swap(a[left], a[key]);return left;
}1.2.2 挖坑法 解释先利用key保存基准值初始让left为坑位然后开始左右指针的遍历让右指针先走去找小于key的值找到后将值填入坑位然后更新坑位为right同理左指针是找大找到大于key的值后将值填入坑位然后再更新坑位位left直到相遇。循环结束后将基准值填入左右指针相遇位置。
//挖坑法
int PartSort2(int* a, int left, int right)
{int mid GetMidi(a, left, right);swap(a[mid], a[left]);int hole left;int key a[left];while (left right){while (left right a[right] key)right - 1;a[hole] a[right];hole right;while (left right a[left] key)left 1;a[hole] a[left];hole left;}a[left] key;return left;
}1.2.3 前后指针版本 创建两个指针一前一后正常情况我们一定cur指针去遍历数组每当我们指向的数据小于a[key]时就让prev1然后交换a[prev]和a[cur]的值。
//前后指针法
int PartSort3(int* a, int left, int right)
{int mid GetMidi(a, left, right);swap(a[left], a[mid]);int key left;int prev left;int cur prev 1;while (curright){if (a[cur] a[key]){prev 1;swap(a[prev], a[cur]);}cur 1;}swap(a[prev], a[key]);return prev;
}
