文档章节

排序算法(1)--冒泡排序&快速排序

haoran_10
 haoran_10
发布于 2016/07/15 16:37
字数 1153
阅读 32
收藏 2

阿里云携手百名商业领袖、技术大咖,带您一探行进中的数字新基建!>>>

已经好久没写算法了,脑袋都生锈了。。

 

首先排序分为四种: 

      交换排序: 包括冒泡排序,快速排序。

      选择排序: 包括直接选择排序,堆排序。

      插入排序: 包括直接插入排序,希尔排序。

      合并排序: 合并排序。

 

本篇对交换排序进行研究。

 

1、冒泡排序

  1. 比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。
  2. 这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。
  3. N=N-1,如果N不为0就重复前面二步,否则排序完成。

精髓:相邻之间相比较交换

 

 

public static void bubbleSort(int arr[]){
	for(int i=0;i<arr.length;i++){//1.外层循环
		for(int j=0;j<arr.length-1-i;j++){//2.内层循环
			if(arr[j]>arr[j+1]){//3.逐个比较,大于则交换
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

 

 

2、快速排序

快速排序采用的思想是分治思想。

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

 

  1. 记录排序数组左边坐标,当前排序数组右边坐标,取左边的一个数据当作基点(把这个点挖出一个坑)
  2. 从右边往左边找,找到一个比base小的数据,把从右边找到的小于base的数据填到左边挖出的坑
  3. 从左往右边找,找到一个比base大的数据,把从左边找到的大于base的数据填到右边挖出的坑
  4. 把base填到最后剩下的坑
  5. 对依赖base排好序数组的左边的数组排序
  6. 对依赖base排好序数组的右边的数组排序

太抽象了。。。

还是举例子来说明吧

(1)、left=0,right=5,base=50;//首先记录左边的坐标,右边的坐标,取第一个数据做为基准。可以理解数组[0]已经被挖坑了。

0

1

2

3

4

5

50

20

10

70

30

60

(2)、从右往左找,找到一个比基准50小的数据,数据是30,此时数组[0]=30,被填坑,数组[4]被挖坑。right坐标移到4,left还是为0。

0

1

2

3

4

5

30

20

10

70

30

60

(3)、从左往右找,找到一个比基准50大的数据,数据是70,此时数组[4]=70,数组[3]被挖坑。left坐标移到3,right还是4。

0

1

2

3

4

5

30

20

10

70

70

60

(4)、继续执行第2、3步,直到left==right,此时left==right==3,把最后剩下的坑在还给base

0

1

2

3

4

5

30

20

10

50

70

60

(5)、此时,在数组[3]的左边数据都比base小,数组[3]右边的数据都比base大,然后对数组[0~2]进行上面的循环操作,对数组[4~5]进行上面的操作。直到所有数据排序完成。

 

 

代码如下:  

public static void quickSort(int array[],int sortArrayLeft,int sortArrayRight){
	if(sortArrayLeft>=sortArrayRight){
		return;
	}
	
	int left  = sortArrayLeft;  //1.1、当前排序数组左边坐标
	int right = sortArrayRight; //1.2、当前排序数组右边坐标
	int base = array[left];     //1.3、取左边的一个数据当作基点
	
	while(left<right){
		while(left<right && array[right]>=base){//2、从右边往左边找,找到一个比base小的数据
			right --;
		}
		
		array[left] = array[right];//3、把从右边找到的小于base的数据填到左边挖出的坑
		
		while(left <right && array[left] <= base){//4、从左往右边找,找到一个比base大的数据
			left ++;
		}
		
		array[right] = array[left];//5、把从左边找到的大于base的数据填到右边挖出的坑
	}
	
	array[left] = base;//6、把base填到最后剩下的坑
	
	quickSort(array, sortArrayLeft, left-1);//7、对依赖base排好序数组的左边的数组排序
	quickSort(array, left+1, sortArrayRight);//8、对依赖base排好序数组的右边的数组排序
}

 

 

 

© 著作权归作者所有

haoran_10
粉丝 27
博文 89
码字总数 82446
作品 0
杭州
程序员
私信 提问
加载中

评论(0)

四中基本排序算法几Java实现(冒泡、选择、插入、快排)

1.1 冒泡排序 冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没...

osc_cfb6ommj
2019/07/23
11
0
排序算法:冒泡排序、选择排序、插入排序、快速排序、希尔排序,以及二分查找。

排序算法: 稳定排序:两个相等的元素不会交换位置 。 1、冒泡排序:时间复杂度 O(n2),相同元素的前后顺序不会改变,冒泡排序是一种稳定排序算法。 代码实现: public static void bubbl...

osc_i5rnp27q
2019/10/14
2
0
重温前端10大排序算法(长文建议收藏)

注意:文章中排序算法性能比较都以实际情况为准。 文中代码地址:github.com/collins999/… 1、冒泡排序 思路 通过相邻元素的比较和交换,使得每一趟循环都能找到未有序数组的最大值或最小值...

蜗牛的北极星之旅
01/07
0
0
算法——列表排序和常用排序算法

一、列表排序   排序就是将一组“无序”的记录序列调整为“有序”的记录序列。   列表排序:将无序列表变为有序列表。     输入:列表     输出:有序列表   两种基本的排序方...

osc_kzm1jtt6
2018/09/12
2
0
算法导论知识梳理(二):比较排序算法及其下限

排序算法简介 交换函数 优化算法:冒泡排序、选择排序、插入排序 优化的冒泡排序 优化的选择排序 优化的插入排序 总结 分治法的应用:归并排序、快速排序 归并排序 快速排序 决策树模型 证明...

梦想翻身的咸鱼
2019/09/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Apache Jmeter 入门

Jmeter是一款优秀的开源测试工具, 是每个资深测试工程师,必须掌握的测试工具,熟练使用Jmeter能大大提高工作效率。 本文将通过一个实际的测试例子, 来讲解Jmeter的基本用法。 Jmeter 介绍...

JEECG开源社区
13分钟前
21
0
Spring Cloud 系列之 Apollo 配置中心(二)

本篇文章为系列文章,未读第一集的同学请猛戳这里:Spring Cloud 系列之 Apollo 配置中心(一) 本篇文章讲解 Apollo 部门管理、用户管理、配置管理、集群管理。      点击链接观看:Apo...

哈喽沃德先生
14分钟前
20
0
原生ES-Module

首先是各大浏览器从何时开始支持module的: Safari 10.1 Chrome 61 Firefox 54 (有可能需要你在about:config页面设置启用dom.moduleScripts.enabled) Edge 16 使用方式 首先在使用上,唯一的...

东东笔记
15分钟前
4
0
DevExpress Winforms使用技巧与窍门集合(2020年5月汇总)

下载DevExpress v20.1完整版 DevExpress Winforms Controls 内置140多个UI控件和库,完美构建流畅、美观且易于使用的应用程序。想要体验?点击下载>> 本文中包含一些示例和调整WinForms UI组...

FILA6666
16分钟前
18
0
SwitchGlass for mac 1.4(331) 系统应用快速启动

mac系统应用怎么才能快速启动?这时候你需要一款mac系统应用快速启动软件!SwitchGlass Mac版是Mac电脑上的一款系统应用快速启动工具。SwitchGlass Mac版为你的Mac应用增加了一个专用的应用程...

麦克W
19分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部