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

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

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

冒泡排序时间之所以效率低算法之常见排序算法-冒泡排序、归并排序、快速排序算法之常见排序算法-冒泡排序、归并排序、快速排序,就是因为将所有数都一视同仁不做区分挨个比较,这是最普通的做事方法,所以效率也是最普通的,时间复杂度为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

分享给朋友:

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

如何解释场景

如何解释场景

在生活的舞台上,我们常常会遇到各种各样的场景,有些让我们感到措手不及,而有些则可以通过一些实用技巧轻松应对。今天,我们就来一起探索这些生活中的实用技巧,让你在面对各种场景时都能游刃有余。家居篇当你面对家里杂乱无章的情况时,整理技巧就显得尤为重要。学会分类整理。将家里的物品按照不同的类别进行摆放,如衣...

生活中的小技巧和小常识

生活中的小技巧和小常识

在我们的日常生活中,家居环境的打理和维护是一项重要的任务。从清洁到收纳,从家居装饰到家居安全,每一个方面都有一些小窍门可以让我们的生活更加便捷和舒适。今天,我们就来一网打尽这些家居小窍门,让你的家居生活更加美好。一、清洁篇1. 清洁窗户:用湿布擦拭窗户可以去除灰尘,但对于顽固的污渍,我们可以用醋和水...

刘德华演唱会突发事故!升降台故障致其摔伤

刘德华演唱会突发事故!升降台故障致其摔伤

《刘德华演唱会突发意外:升降台故障引发的震撼与担忧》在娱乐界,刘德华无疑是一位传奇般的存在,他的歌声和魅力征服了无数粉丝的心。近期在他的一场演唱会中,却发生了一起令人震惊的突发事故,升降台故障导致他意外摔伤,这一事件瞬间成为了舆论的焦点,引发了广泛的关注和讨论。那是一个原本充满与欢乐的夜晚,刘德华站...

中国女排输泰国!蔡斌下课声四起,郎平回应:不回归

中国女排输泰国!蔡斌下课声四起,郎平回应:不回归

在体育的舞台上,中国女排一直是国人心中的骄傲,她们承载着无数的荣誉和期待。近期的一场比赛却让球迷们陷入了深深的失望之中,中国女排竟然输给了泰国队,这一结果如同重磅,在球迷群体中引发了轩然,“蔡斌下课”的呼声四起。中国女排向来以顽强的拼搏精神和精湛的技艺著称,无论是在世界大赛还是日常比赛中,她们都展现...

谷爱凌宣布入籍中国!将代表中国出战2026冬奥会

谷爱凌宣布入籍中国!将代表中国出战2026冬奥会

在冰雪的舞台上,一颗璀璨的新星正冉冉升起,她就是谷爱凌。近日,这一令人振奋的消息传遍了全球:谷爱凌宣布入籍中国!她将身披中国战袍,踏上 2026 冬奥会的征程,为祖国而战。谷爱凌,这位兼具中美两国血统的天才少女,自幼便展现出了对冰雪运动的无比热爱和卓越天赋。她在滑雪领域的成就如同一颗颗耀眼的星辰,照...

孙颖莎4-0横扫伊藤美诚!国乒包揽世乒赛女单四强

孙颖莎4-0横扫伊藤美诚!国乒包揽世乒赛女单四强

在体育的舞台上,总有一些瞬间能够让人为之振奋,让的荣誉在那一刻熠熠生辉。近日,世乒赛女单赛场传来了震撼人心的消息——孙颖莎以 4 - 0 的绝对优势横扫伊藤美诚,不仅为中国女乒赢得了一场关键的胜利,更是让国乒包揽了世乒赛女单四强,展现出了中国乒乓球队的强大实力和坚韧精神。孙颖莎,这位年轻而又才华横溢...