5种排序算法ppt课件.ppt
常用的5种排序算法,1.冒泡排序,简介:冒泡排序（Bubble Sort），是一种计算机领域领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。,冒泡排序原理:比较相邻的元素，将小的放到前面,(每一轮找出数组中最大的放在后面，后面排好序的数组元素不参与下轮排序),下面将数组7,8,5,1,3里面的元素进行排序。,7 8 5 1 3,1.1: 7 8 5 1 3 7和8进行比较，因为78所以2个元素的位置不变,2.1: 5 7 1 3 8,1.3: 7 5 1 8 3 8和1进行比较，因为81所以2个元素的位置互换,1.4: 7 5 1 3 8 同理，8和3互换位置，得到最大数8，并且不参与下一轮排序,1.2: 7 5 8 1 3 8和5进行比较，因为85所以2个元素的位置互换,.,同理第二轮排序得到最大数是7，放在最后，依次得到每一轮的最大值，这样小的数就在前面，大的数放在后面，最后得到所要的数组1,3,5,7,8。,1.选择排序,简介:将数组中每个元素与第一个元素比较，如果这个元素小于第一个元素，则交换这两个元素。,原理:1.将数组中每个元素与第一个元素比较，如果这个元素小于第一个元素，则交换这两个元素2.循环第1条规则，找出最小元素，放于第1个位置3.经过n-1轮比较完成排序,5 2 7 3 8,1.1: 2 5 7 3 8 25，所以2和5互换位置,1.3: 2 5 7 3 8,1.4: 2 5 7 3 8 第一轮得出最小的元素为”2”,1.2: 2 5 7 3 8 72，所以2个元素位置不变,同理第三轮排序得到该轮最小数是5，放在第三个位置，依次得到每一轮的最小值，这样小的数就在前面，大的数放在后面，最后得到所要的数组2,3,5,7,8。,2.1: 2 5 7 3 8 第二轮从5的位置开始比较,75，位置不变,2.2: 2 3 7 5 8 35,位置互换,2.3: 2 3 7 5 8 83,位置不变,2.4: 2 3 7 5 8 第二轮排序结束得到该轮最小值”3”,1.插入排序,简介:将数组分为两部分, 将后部分的第一个逐一与前部分每一个元素比较，在合理位置插入。,原理:1.将数组分为两部分, 将后部分的第一个逐一与前部分每一个元素比较，在合理位置插入2.插入排序算法效率要高于选择排序和冒泡排序,7 8 5 1 3 将数组分为7和8,5,1,3两部分,1: 7 8 5 1 3 87，所以位置不变,3: 1 5 7 8 3 1 8 & 17 & 15,所以1放到5,7,8的前面,4: 1 3 5 7 8 将3依次和前面元素比较，得到33，所以3在1和5之间，结束,2: 5 7 8 1 3 58 & 57,所以5放到7和8的前面,这样我们发现，插入排序速度要比冒泡排序和选择排序快很多,1.快速排序,简介:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束。,原理:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。,4 7 8 5 10 9 3 12 11,1: 选10位一个基准数，进行第一次排序，小于10的放左边，大于10的放右边，得到新的数组4,7,8,5,9,3,10,12,11,以10为基准分成左右2部分,4,7,8,5,9, 3,10,12,11，两边数组分别进行快速排序,以数组第一个元素作为基准进行排序。当前数据为4,7,8,5,9,3,10,12,11,2: 4,7,8,5,9,3以第一个元素4作为基准排序得到3,4,5,7,8,9；后面的数组为11,12，结束。当前数据为3,4,5,7,8,9,10,11,12，因为3为单个的，所以3不需再进行排序，目前只需对5,7,8,9进行处理,3: 5,7,8,9,以第一个元素5作为基准排序，得到5,7,8,9当前数据为3,4,5,7,8,9,10,11,12,4: 类似步骤3，分别把7,8,9给独立出来，最终得到数据3,4,5,7,8,9,10,11,12,1.桶子排序,简介:依次进行个位、十位、百位的比较和排序，得到最后的结果。,原理:依次进行个位、十位、百位的比较和排序，得到最后的结果。,21 10 8 13 123 5,0 10 1 2123 13,12345 5678 89,个位,依次从上至下排序,得到10,21,13,123,5,8,0 5,8 1 10,132 21,1233 1345 678 9,十位,依次从上至下排序,得到5,8,10,13,21,123,0 5,8,10,13,21 1 1232 3 45 678 9,百位,依次从上至下排序,得到5,8,10,13,21,123,桶子排序总结:由于每次对各个位数进行比较排序时都遍历一遍数组，所以对于个别元素的位数比较大时，性能会降低不少。,附:,
