您的当前位置:首页>新品 > 正文

大数据常用基本算法 双冒泡排序双向冒泡算法的原理及应用_今日热议

来源:CSDN 时间:2023-03-07 09:03:24


(资料图)

1、冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大 到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有 相邻元素需要交换,也就是说该元素已经排序完成 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序 排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序” 冒泡排序算法的原理如下: 1)比较相邻的元素。如果第一个比第二个大,就交换他们两个 2)对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后 的元素应该会是最大的数 3)针对所有的元素重复以上的步骤,除了最后一个 4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较 列如: 数组元素> 5 1 7 2 6 4 3 16 1)由于第一个元素5比第二个元素大1,交换它们的位置。 1 5 7 2 6 4 3 16 2)对比每个相邻的元素,此时到第二个元素5与第三个元素7,不交换位置 1 5 7 2 6 4 3 16 3)对比每个相邻的元素,此时到第三个元素7与第四个元素2,交换位置 1 5 2 7 6 4 3 16 4)对比每个相邻的元素,此时到第四个元素7与第五个元素6,交换位置 1 5 2 6 7 4 3 16 5)对比每个相邻的元素,此时到第五个元素7与第六个元素4,交换位置 1 5 2 6 4 7 3 16 6)对比每个相邻的元素,此时到第六个元素7与第七个元素3,交换位置 1 5 2 6 4 3 7 16 6)对比每个相邻的元素,此时到第七个元素7与第八个元素16,不换位置 1 5 2 6 4 3 7 16

2、双冒泡排序

双向冒泡算法,极大的减少了循环排序的次数 1)传统冒泡气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往 左进行,如此完成一次排序的动作 2)使用left与right两个旗标来记录左右两端已排序的元素位置 3)当往左递进left >=往右递进的 right时,则排序完成 例子如下所示: 排序前:45 19 77 81 13 28 18 19 77 11 往右排序:19 45 77 13 28 18 19 77 11 [81] 向左排序:[11] 19 45 77 13 28 18 19 77 [81] 往右排序:[11] 19 45 13 28 18 19 [77 77 81] 向左排序:[11 13] 19 45 18 28 19 [77 77 81] 往右排序:[11 13] 19 18 28 19 [45 77 77 81] 向左排序:[11 13 18] 19 19 28 [45 77 77 81] 往右排序:[11 13 18] 19 19 [28 45 77 77 81] 向左排序:[11 13 18 19 19] [28 45 77 77 81] 此时28>=19条件成立排序完成

3、快速排序

快速排序(Quicksort)是对冒泡排序的一种改进 快速排序的基本思想:首先选取一个记录作为枢(shu)轴,不失一般性,可选第一个记 录,依它的关键字为基准重排其余记录,将所有关键字比它大的记录都安置在它之后,而将所有关键字比它小的记录都安置在之前,由此完成一趟快速排序;之后,分别对由一趟排序分割成的两个子序列进行快速排序,在大数据情况下要使用快速排序 列如: 数组元素> 5 1 7 2 6 4 3 16 思路: 取第一个数,把小于它的数往左移动,把大于它的数右移动 1)最左侧大于5的为7,最右侧小于5的为3,7与3对调 以5为枢轴> 5 1 3 2 6 4 7 16 2)全部对调完成,此时左侧小于5,右边大于5 5 1 3 2 | 6 4 7 16 3)5移动到分割位置 1 3 2 5 6 4 7 16 4)如果把数组元素分为三部分的话 左侧<中间<右侧 1="" 2="" 3="" 4="" 5="" 6="" 7="" 16=""> 1 2 3 此时左侧 6 4 7 16 > 4 6 7 16 简单来说:定义基数,比它小的往左排,比它大的往右排

4、归并排序

归并排序(MERGESORT) 是建立在归并操作上的一种有效的排序算法,该算法是采用 分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到 完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并 成一个有序表,称为二路归并 归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法 如 设有数列1 8 2 9 3 5 6 4 10 1)第一次归并后:{1 8},{2 9},{ 3 5},{ 4 6},{10}此时两两元素排序完的归并 2)第二次归并后:{1 2 8 9},{ 3 4 5 6} ,{10}此时两两元素归并 1与2 寻找最小数 1 8与2 寻找最小数 2 8与9寻找最小数 8 {1 2 8 9} 3)第三次归并后:{1 2 3 4 5 6 8 9} , {10}此时两两元素归并 1与3寻找到最小数1 {1} 2与3寻找最小数2 {1 2} 8与3寻找最小数3 {1 2 3} 8与4寻找最小数4 {1 2 3 4} 8与5寻找最小数5 {1 2 3 4 5} 8与6寻找最小数6 {1 2 3 4 5 6} 8 9 落下{1 2 3 4 5 6 8 9} 4)第四次归并后:{1 2 3 4 5 6 8 9 10} 思路:循环找到最小值落下

标签:

最新新闻:

新闻放送
Top