文档章节

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

haoran_10
 haoran_10
发布于 2016/07/15 16:37
字数 1153
阅读 28
收藏 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
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
06/05
0
0
算法系列【希尔排序】篇

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

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

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

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Dubbo分析之Cluster层

系列文章 Dubbo分析Serialize层 Dubbo分析之Transport层 Dubbo分析之Exchange 层 Dubbo分析之Protocol层 前言 紧接上文Dubbo分析之Protocol层,本文继续分析dubbo的cluster层,此层封装多个提...

ksfzhaohui
17分钟前
0
0
linux Ubuntu 安装 hyperledger fabric

一、apt-get update 二、安装docker sudo apt-get install docker.io 如果安装报错:E: Unable to locate package,请执行第一条。 # docker -v Docker version 1.6.2, build 7c8fca2 # dock......

八戒八戒八戒
21分钟前
1
0
神经网络基础及Keras入门

神经网络定义 人工神经网络,简称神经网络,在机器学习和认知科学领域,是一种模仿生物神经网络(动物的中枢神经系统,特别是大脑)的结构和功能的数学模型或计算模型,用于对函数进行估计或...

Python女神
21分钟前
1
0
Pycharm上Django的使用 Day9

编辑条目: 1.创建edit_entry的URL模式 形参entry_id存储在URL中传递的ID,这个URL模式将预期匹配的请求发送给视图函数edit_entry() 2.编写视图函数edit_entry() 1处获取用户要修改的条目对象...

不会TC的猫
21分钟前
1
0
夹点getGripPoints/捕捉点getOsnapPoints

已知圆外一点,以及圆心半径,求圆的切点: 方法1: (b-y/a-x)*(n-y/m-x)=-1(a-x)平方+(b-y)平方=r平方联立方程组求解 方法1: CPoint CalcQieDian(CPoint ptCenter, CPoint ptOutside, do...

一个小妞
33分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部