快排和插排的Java实现

发表于   |   分类于   |     |   阅读次数

这图吊炸天

《大话数据结构》是以C语言编著，对于我主攻java来说，脑子要转点弯。后来有捡着《数据结构与算法分析——Java语言描述》的有关查找排序的章节看，觉得此书是宝典，可是我看不懂。。。术语太尼玛多了。所以很有必要整理一下排序算法，排序算法有很多，就书中介绍的就有，冒泡、选择、插入、归并、希尔（归并的加强版）、快排还有堆排序等等。
这里主要是快速排序和插入排序的Java实现。

快速排序实现

据说能手写代码的，年薪都很客观哦。。。快速排序一种分治的递归算法。它首先把一个大的数组分成两个小的子数组：较小的数的数组和较大的数的数组。再对这子数组做递归处理。

原理

  1. 从数组中任意选择一个元素，称为枢纽元（pivot）。虽然无论选择哪个元素作为pivot都可以完成排序，但是有些选择显然优于其他选择。将第一个元素作为pivot是一种错误的做法。安全的做法是随机选取pivot。最好的做法是选择数组的中值：一般的做法是使用左端、右端和中心位置上的三个元素的中值作为pivot。
  2. 对数组进行重新排序，所有比pivot小的数在pivot前面，所有比pivot大的数在pivot后面（相等的可以在任何一边）。经过这样的分区后，pivot就在它最终的位置上了。这个步骤叫做分区操作。
  3. 把上述的步骤对含有较小数的子数组和含有较大数的子数组进行递归操作。

enter description hereenter description here

实现

这里为了说明分组递归的问题，还是选择第一个数作为枢纽元，也就是我们常说的基准。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class QucikSort {
	/*
	 * 快速排序——分治法的典型
	 * @parm:
	 * arr 待排序的整型数组，
	 * start 数组开始位置
	 * end 数组结束位置
	 */
	public  void qucikSort(int [] arr,int start, int end){
		int i=start,j=end;//设置数组两头两个指针
		int pivot=arr[start];//选第一个数为基准
		
		while(i<=j){
			while((i<arr.length)&&(arr[i]<pivot)){
				i++;
			}
			while((j>0)&&(arr[j]>pivot)){
				j--;
			}
			if(i<=j){
				swap(arr,i,j);
				i++;
				j--;
			}
		}
		if(start<j)
			qucikSort(arr,start,j);
		if(i<end)
			qucikSort(arr,i,end);
		
	}
	
	//交换数组中两个元素
	public void swap(int[] arr,int i,int j){
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	
}

优化

1，对现在浩如烟海的大数据而言，用快排是再好不过了。但如果是小数组，倒不如用插入排序。还有就是枢纽元的选择方式，最好的是选择中值。
2，还有一个明显地缺陷：输入数据基本有序甚至完全有序的时候，这算法退化为冒泡排序，不再是O(n㏒n)，而是O(n^2)了。所以为了避免这样的问题，可以先对输入数据做一个打乱处理，虽然会耗费点时间，但是我认为还蛮有必要的。

插入排序

插入排序是个蛮简单的数组，就是对已经排好序的数组从后向前扫描，找到响应的位置插入。就好比每次班主任分座位，按高矮个排队一回事。什么你没分过座位！！！那说明你在班主任心里是有位置的。懂吗。

原理

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

enter description hereenter description here

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class InsertSort {
	/*
	 * 很简单的插入排序
	 * 把前面的数认为是已经排好序的
	 */
	public void insetSort(int [] arr){
		int tmp=0;
		for(int index=1;index<arr.length;index++){
			tmp=arr[index];
			int i=index;
			while((i>0)&&(arr[i-1]>tmp)){
				arr[i]=arr[i-1];
				i--;
			}
			arr[i]=tmp;
		}
	}
}

优化

可以容易地想到如果数据为逆序的话，效率很低，因为每个未排序的数都要移动前面已经排序的所有数。所以当数据是基本有序的时候且数据量小，利用插入排序的时候，效率会很高。

参考资料

经典排序算法总结与实现(python)
Sorting Algorithms Animations
用Java写算法之五：快速排序
白话经典算法

热评文章