`
haoran_10
  • 浏览: 443240 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

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

阅读更多

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

 

首先排序分为四种: 

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

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

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

      合并排序: 合并排序。

 

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

 

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排好序数组的右边的数组排序
}

 

 

 

4
3
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics