文档章节

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

haoran_10
 haoran_10
发布于 2016/07/15 16:37
字数 1153
阅读 27
收藏 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
粉丝 25
博文 88
码字总数 80846
作品 0
杭州
程序员
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

70.shell的函数 数组 告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析 20.16/20.17 shell中的函数: ~1. 函数就是把一段代码整理到了一个小单元中,并给这个小单元起一个名字,当用到这段...

王鑫linux
今天
2
0
分布式框架spring-session实现session一致性使用问题

前言:项目中使用到spring-session来缓存用户信息,保证服务之间session一致性,但是获取session信息为什么不能再服务层获取? 一、spring-session实现session一致性方式 用户每一次请求都会...

WALK_MAN
今天
6
0
C++ yield()与sleep_for()

C++11 标准库提供了yield()和sleep_for()两个方法。 (1)std::this_thread::yield(): 线程调用该方法时,主动让出CPU,并且不参与CPU的本次调度,从而让其他线程有机会运行。在后续的调度周...

yepanl
今天
4
0
Java并发编程实战(chapter_3)(线程池ThreadPoolExecutor源码分析)

这个系列一直没再写,很多原因,中间经历了换工作,熟悉项目,熟悉新团队等等一系列的事情。并发课题对于Java来说是一个又重要又难的一大块,除非气定神闲、精力满满,否则我本身是不敢随便写...

心中的理想乡
今天
42
0
shell学习之获取用户的输入命令read

在运行脚本的时候,命令行参数是可以传入参数,还有就是在脚本运行过程中需要用户输入参数,比如你想要在脚本运行时问个问题,并等待运行脚本的人来回答。bash shell为此提 供了read命令。 ...

woshixin
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部