常用算法（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]已经被挖坑了。

代码如下：??

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

?

?

?

常用算法（1）--交换排序（冒泡排序&快速排序）

原文：http://haoran-10.iteye.com/blog/2266055