排序算法(三) -- 希尔、快排

1.希尔排序

1.1 简单插入排序存在的问题

我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

1.2 希尔排序法介绍

希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

1.3 希尔排序法基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

1.4 希尔排序法的示意图

1.5 位移法希尔排序代码实现如下：

public static void shellSort(int[] arr){
			//增量gap,并逐步的缩小增量
			for(int gap = arr.length/2; gap > 0 ; gap /= 2){
				//从第gap个元素，逐个对其所在的组进行直接插入排序
				for(int i = gap; i < arr.length; i++){
					int j = i;
					int temp = arr[j];
					//if(arr[j] < arr[j -gap]){
						while(j -gap >= 0 && temp < arr[j - gap]){
							//移动
							arr[j] = arr[j - gap];
							j -= gap;
						}
						//当退出while后，就给arr[j]找到了插入的位置
						arr[j] = temp;
					//}
				}
			}
		}

位移法希尔排序性能测试

public static void main(String[] args) {
		// TODO Auto-generated method stub

		//int[] arr = {8,9,1,7,2,3,5,4,6,0};
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 80000);// 生成一个[0,80000]之间的数
		}
		Date date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		//System.out.println("排序前的数组为"+Arrays.toString(arr));
		System.out.println("排序前的时间是:" + date1Str);
		shellSort(arr);//移位法
	//	System.out.println("排序后的数组为"+Arrays.toString(arr));
		Date date2 = new Date();
		String date2Str = simpleDateFormat.format(date2);
		System.out.println("排序后的时间是:"+date2Str);
	}

测试结果如下：

2.快速排序

2.1 快速排序法介绍

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.2 快速排序法示意图

3.3 快速排序的代码实现

public static void quickSort(int[] arr,int left,int right){
		int l = left;//左下标
		int r = right;//右下标
		int pivot =  arr[(left + right) / 2];
		int temp = 0; //临时变量
		//while循环的目的是让比pivot小的值放到左边，比pivot大的值放右边
		while(l < r){
			//在pivot的左边找到一个大于等于pivot的值才退出
			while(arr[l] < pivot){
				l += 1;
			}
			//在pivot的右边一直找，找到小于等于pivot的值，才退出
			while(arr[r] > pivot){
				r -= 1;
			}
			//如果 l >=  r 说明pivot的左右两值已经按照左边全部是小于等于pivot的值，右边全部是大于等于pivot的值
			if(l >= r){
				break;
			}
			//交换
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
			//如果交换完后发现这个arr[l] == pivot值 r前移
			if(arr[l] == pivot){
				r -= 1;
			}
			//如果交换完后，发现这个arr[r] == pivot值 l++ 后移
			if(arr[r] == pivot){
				l += 1;
			}
		}
		//如果l ==r，必须 l++,r--，否则出现栈溢出
		if(l == r){
			l += 1;
			r -= 1;
		}
		//向左递归
		if(left < r){
			quickSort(arr, left, r);
		}
		//向右递归
		if(right > l){
			quickSort(arr,l,right);
		}
		
	}

3.4 快速排序的性能测试：

public static void main(String[] args) {
		// TODO Auto-generated method stub

		// int[] arr = {-9,78,23,-567,70,0,-1};
		int[] arr = new int[80000];
		for(int i = 0 ; i < 80000; i++){
			arr[i] = (int)(Math.random() * 80000);//生成一个[0,800000]之间的数
		}
		Date date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		System.out.println("排序前的时间是:"+date1Str);
		quickSort(arr, 0, arr.length - 1);
		//System.out.println("arr="+Arrays.toString(arr));
		Date date2 = new Date();
		String date2Str = simpleDateFormat.format(date2);
		System.out.println("排序后的时间是:"+date2Str);
	}

测试结果如下：