当前位置:首页 > 文化体育 > 正文内容

算法之常见排序算法-冒泡排序、归并排序、快速排序

算法之常见排序算法-冒泡排序、归并排序、快速排序

冒泡排序时间之所以效率低算法之常见排序算法-冒泡排序、归并排序、快速排序算法之常见排序算法-冒泡排序、归并排序、快速排序,就是因为将所有数都一视同仁不做区分挨个比较,这是最普通的做事方法,所以效率也是最普通的,时间复杂度为N的平方;而归并排序效率高,则是采用了分治的思想,将一个整体分成多个小份,每个小份排好序之后再互相比较,这样就比冒泡快了不少,时间复杂度为NlogN;快速排序的平均时间复杂度也是NlogN堆排序时间复杂度最坏,但是实际的耗费时间会比归并排序快两三倍(当然快排在最坏的情况下时间复杂度还是N的平方,比归并排序大)堆排序时间复杂度最坏,它的平均执行时间能比归并更快一些是因为它每次分组时不是随机分组而是相对有序的分组,即先从数组中随机取一个数作为基数,然后将数据移动,使得基数一边的数都比它小,另一边的数都比它大,再在两边各取一个基数进行相同的移动、分组操作,递归下去,这样每个细分的小组都在整体的大数组中有个位置,合并时直接按从小到大将各个分组合并起来即可,所以一般情况下会比归并快一些。

了解了思想之后,再用代码实现相对就会容易很多。此处就再借用一个直观一点的例子来说明归并与快排二者的区别。假设有1000个学生,想对他们的成绩进行排序。方法1借用归并排序的思想,具体这样做:将这1000个人分成10组,将每组的100人进行排序,排完之后再在各组之间从小到大依次进行比较,最后得到整个的成绩排名。方法2借用快速排序的思想,具体需这样做:将1000个人也是分成10组,但是是按分数段分,0-10分的放在一组,10-20分的放在一组堆排序时间复杂度最坏,20-30分的放在一组,依次类推,分完组之后再在各个小组中进行排序,而当你合并各个小组时,只需将其按从小到大的顺序直接合并就行,无需跟方法1一样将各小组中的数据取出来跟其他小组中的数据挨个比较。看到这里,想必各位道友对快排比归并排序还要快一些的原因就有了解了。

算法可以理解成做事的技巧或者说套路,我们对其的理解可以不止于编程,完全可以推广出去。比如归并的分治法,将一个大事情拆解成多个小事件,解决起来就会方便很多。闲话扯了一大堆,下面就将我自己写的排序给大家贴出来,附带上注释讲解,如果有之前不了解的道友,相信看完之后便会念头通透,原地飞升 >_< 。 正文 归并排序

// 归并排序
 public static void mergeSort (int[] arr) {
 // 建一个临时数据来存放数据
 int[] temp = new int[arr.length];
 mergeSort(arr, 0, arr.length - 1, temp);
 }
 private static void mergeSort(int[] arr, int left, int right, int[] temp) {
 if (left < right) { // 如果起始下标跟结束下标差值小于1,则不进行操作
 int mid = (left + right) / 2;
 mergeSort(arr, left, mid, temp); // 分组,将左边分为一组,递归调用进行排序
 mergeSort(arr, mid+1, right, temp); // 将右边分为一组
 merge(arr, left, mid, right, temp); //将左右分组合并
 }
 }
 private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
 int i = left; // 定义左指针
 int j = mid + 1; // 定义右指针
 int t = 0; // 给temp临时数组用的指针
 while (i <= mid && j <= right) { // 设置左右指针的移动边界
 if (arr[i] <= arr[j]) { // 此处是升序,故谁小谁先赋给临时数组
 temp[t++] = arr[i++];
 } else {
 temp[t++] = arr[j++];
 }
 }
 while (i <= mid) { // 如果左边有剩余,则放在temp中
 temp[t++] = arr[i++];
 }
 while (j <= right) { // 如果右边有剩余,依次放入temp中
 temp[t++] = arr[j++];
 }
 t = 0;

算法之常见排序算法-冒泡排序、归并排序、快速排序 第1张

// 此时temp中已经是arr数组中下标从left到right之间排好序的数据了,因为temp每次都是从0开始赋值,所以需将排好序的数放回arr的对应位置 while (left <= right) { // 将left到right之间排好序的数据放回arr中,此时left到right之间的数就是最终排好序的数 arr[left++] = temp[t++]; } }

快速排序

// 快速排序
 public static void quickSort (int[] arr, int left, int right) {
 // 先将异常情况处理掉
 if (arr == null || arr.length < 2) {
 return;
 }
 if (right <= left) {
 return;
 }
 if (right - left == 1 && arr[left] <= arr[right]) {
 return;
 }
 // 取第一个数为基准数(基数取哪个都行,此处是为了方便)
 int index = arr[left];

 int i = left + 1; // 左指针
 int j = right; // 右指针
 while (i < j && i < right && j > left) { // 设置指针的移动边界
 while (arr[j] > index && j > left) {j--;} // 找到从右边数第一个比index小的数
 while (arr[i] < index && i < right) {i++;} // 找到从左边数第一个比index大的数
 if (i < j) { // 交换这两个数 如果i == j,说明二者定位到了同一个位置,则不用交换;如果i > j,说明二者已经相遇然后背向而行了,也不交换
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }
 // 执行完上面循环后,arr已经是左边比index小,右边比index大的数组了,只是基准数仍在基准位置left处,需放到它应该在的位置
 if (j != left && arr[j] != arr[left]) {
 // j最后停留位置的数,肯定是一个小于等于index的值,所以如果不是同一个位置的话,直接将二者调换一下位置即可
 int temp = arr[j];
 arr[j] = arr[left];
 arr[left] = temp;
 }
 quickSort(arr, left, j-1); // 将基准数左边排序
 quickSort(arr, j+1, right); // 将基准数右边排序
 }

加入微信交流群:************ ,请猛戳这里→点击入群

扫描二维码推送至手机访问。

版权声明:本文由智汇百科网发布,如需转载请注明出处。

本文链接:https://zhihuibkw.com/post/4394.html

分享给朋友:

“算法之常见排序算法-冒泡排序、归并排序、快速排序” 的相关文章

詹姆斯加冕历史得分王!湖人主场球迷集体膜拜

詹姆斯加冕历史得分王!湖人主场球迷集体膜拜

在篮球的浩瀚星空中,总有一些时刻注定会被铭记史册,成为永恒的经典。而当勒布朗·詹姆斯在湖人主场加冕历史得分王的那一刻,整个篮球世界仿佛都被定格在这神圣的瞬间,湖人主场的球迷们更是集体陷入了膜拜的狂热之中。那是一个普通的比赛日,却注定成为湖人历史上最璀璨的篇章之一。詹姆斯站在球场上,眼神中透露出坚定与...

文化瑰宝与国际体育舞台的交融:中国体育文物海外首秀

文化瑰宝与国际体育舞台的交融:中国体育文物海外首秀

在世界的大舞台上,文化与体育如两颗璀璨的星辰,相互辉映,共同谱写着人类文明的壮丽篇章。而当中国的文化瑰宝与国际体育舞台相遇,那将是一场令人震撼的交融与碰撞。中国,作为拥有悠久历史和灿烂文化的文明古国,其体育文物宛如深藏在时光长河中的明珠,散发着独特的魅力。这些文物不仅是中国古代体育发展的见证,更是中...

体育赛事转播中的中国文化解读

体育赛事转播中的中国文化解读

在当今全球化的时代,体育赛事已经成为人们生活中不可或缺的一部分。而在体育赛事的转播中,除了精彩的比赛画面和激烈的对抗,中国文化的解读也逐渐成为了一道亮丽的风景线。中国文化源远流长,博大精深,其蕴含的智慧和精神在体育赛事转播中得到了充分的体现。以武术为例,武术作为中国传统文化的瑰宝,其强调的“以柔克刚...

从国内走向国际:中国体育健儿的文化使命

从国内走向国际:中国体育健儿的文化使命

在世界体育的舞台上,中国体育健儿们正以其卓越的表现,从国内走向国际,成为了中国文化的使者。他们不仅在赛场上争金夺银,更在国际舞台上传播着中国的文化和精神,肩负着重要的文化使命。中国体育健儿们的每一次拼搏,都蕴含着深厚的文化内涵。从古代的武术到现代的各类体育项目,中国文化一直与体育紧密相连。武术,作为...

体育文化交流对国内体育发展的影响

体育文化交流对国内体育发展的影响

在当今全球化的时代背景下,体育文化交流正日益成为推动国内体育发展的重要力量。它如同一场无声的,在各个层面深刻地影响着我国体育事业的前进方向和发展速度。体育文化交流为国内体育带来了全新的理念和技术。通过与世界各国的体育交流活动,我们得以接触到先进的训练方法、科学的体能恢复手段以及独特的战术理念。这些宝...

体育文化交流中的中国文化输出

体育文化交流中的中国文化输出

在当今全球化的时代,体育文化交流成为了各国之间相互了解、相互融合的重要途径。而中国作为拥有悠久历史和丰富文化的大国,在体育文化交流中发挥着越来越重要的作用,积极地进行着中国文化的输出。体育,不仅仅是身体的运动,更是一种文化的体现。中国的传统体育项目,如武术、太极拳、围棋等,以其独特的魅力在世界体育舞...