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