我的代码游记

分类 · 排序专题

首页

关于

归档

排序总结

插入排序(Insertion Sort)

概念插入排序是一种简单直观的排序算法.通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 步骤 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5 举例例1现有一组数组[5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下: [5] 6 3 1 8 7 2 4我们把已排好序的数列用[]括起来,我们直接把第一个元素放入已排序数列 ..

更多
排序总结

选择排序(Selection Sort)

概念选择排序是一种简单直观的排序算法,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕.顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完.再简单点,对着一群数组说,你们谁最小出列,站到最后边,然后继续对剩余的无序数组说,你们谁最小出列,站到最后边,再继续刚才的操作,一直到最后一个,继续站到最后边,现在数组有序了.优点选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所..

更多
排序总结

冒泡排序(Bubble Sort)

概念冒泡排序是一种简单的排序算法.基本思想是迭代地对数列中的第一个元素到最后一个元素进行两两比较,当需要的时候交换这两个元素(位置).重复这个过程一直到所有元素都被排序到正确的位置上.冒泡排序得名于较小的元素如同”气泡”一样逐渐漂浮到数列的顶端. 步骤 比较相邻的元素,如果第一个比第二个大^1x,就交换它们两个的位置. 对每一对相邻元素作进行同样的步骤,从开始第一对到结尾的最后一对这步做完后. 进行一轮的比较之后,最大的数会被不断交换到最后一位,这样最后一位数就是有序^2x的了. 针对所有的元素重复以上的步骤,直到所有的元素都被排好序. 举例例 1假定有一个数组[5, 7, 4, 10, 9],我们要把这个数组按从小到大排列 我们从第一个数开始,两个一组进行比较大小,也就是把第一个数和第二个数比较,如果..

更多
loading..
排序总结

希尔排序(Shell sort)

概念 将整个序列分割成若干小的子序列,再分别对子序列进行直接插入排序,使得原来序列成为基本有序。这样通过对较小的序列进行插入排序,然后对基本有序的数列进行插入排序,能够提高插入排序算法的效率。 希尔排序也是插入排序的一种,使用了分治的思想,让排序的时间复杂度较插入排序有大幅的提升,于是单独拿出来作为一章.希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名. 步骤 先取一个正整数$d_1<n$,把所有序号相隔d1的数组元素放一组 组内进行直接插入排序 然后取$d_2<d_1$,重复上述分组和排序操作 直至$d_i=1$,即所有记录放进一个组中排序为止。举例例1以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, ..

更多