排序

改变Arrays.sort()的排序方向

Arrays.sort()默认为升序，要想降序可以实现Comparator接口并重写compare(Integer o1, Integer o2)方法，此处可以用匿名内部类实现

此时需要使用包装类，不能是基本数据类型

Arrays.sort(nums,new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return o2-o1;//此时为降序
			}
		});

快速排序

/**
 * 快速排序
 */
public static void quickSort(int[] L, int low, int high) {
	int pivot;//枢纽，左边的值都比它小，右边的值都比它大,是下标
	if(low<high) {
		pivot = partition(L,low,high);//算出pivot，将L[low]...L[high]一分为二
		quickSort(L, low, pivot-1);//低子表排序
		quickSort(L, pivot+1, high);//高子表排序
	}
}
public static int partition(int[] L,int low,int high) {
	int key = L[low];//将数组的第一个记录作为pivot
	while(low<high) {
		while(low<high && L[high]>key) {//右边大，不交换，high-1下一个high
			high--;
		}
		int temp1 = L[high];
		L[high] = L[low];
		L[low] = temp1;//右边比key小，则交换
		while(low<high && L[low]<key) {//左边小，不交换，low++下一个low
			low++;
		}
		int temp2 = L[high];
		L[high] = L[low];
		L[low] = temp2;//左边比key大，则交换
	}
	return low;
}

快速排序优化：

• 在选取pivotkey时，一般认为pivotkey是出于整个序列的中间位置最佳，此时可以选用三数取中的方法取得比较靠中间的值
• 优化不必要的交换，将交换替代为替换，最终再将最后被替换掉的数据补回来

public static int optimizedPartition(int[] L,int low,int high) {
	int pivotkey;//优化pivotkey的选取，三数取中法
	//		int mid = low + (low + high)/2;
	//		if(L[low] > L[high]) swap(L, low, high);//保证左端最小
	//		if(L[mid] > L[high]) swap(L, mid, high);//保证mid最小
	//		if(L[low] > L[mid]) swap(L, mid, low);//保证左端最小
	//		pivotkey = L[mid];

	pivotkey = L[low];//枢纽关键字备份

	while(low<high) {
		while(low<high && L[high]>=pivotkey) high--;//先做high
		L[low] = L[high];
		while(low<high && L[low]<=pivotkey) low++;
		L[high] = L[low];//替换，而非交换
	}
	L[low] = pivotkey;//补回最后被替换掉的数
	return low;
}

插入排序

/**
 * 插入排序
 */
public static void insertSort(int[] L) {

	for (int i = 1; i < L.length; i++) {

		if (L[i] < L[i - 1]) {// 在L[0]...L[i-1]的有序数列中找到合适的位置插入L[i]

			int temp = L[i];// 哨兵保存L[i]的值
			int j;
			for (j = i-1; j>=0 && L[j]>temp; j--) {
				L[j + 1] = L[j];// 记录后移,把比L[i]大的数据向后移动

			}
			L[j + 1] = temp;// 把L[i]插入到有序序列中
		}
	}
}

选择排序

/**
 * 选择排序
 * @param L
 */
public static void selectSort(int[] L) {
	for(int i=0;i<L.length;i++) {

		int min = i;//初始为同一位置，如果i+1比i大则min仍然为i.循环进入i+1，min也为i+1

		for(int j=i+1;j<L.length;j++) {
			if(L[j]<L[min])
				min = j;//找到i后面的数据的最小值，下标给min
		}
		if(i!=min) {//比较的是下标
			int temp = L[i];
			L[i] = L[min];
			L[min] = temp;
		}
	}
}

冒泡排序

优化冒泡排序

/**
 * 优化冒泡排序，对有序的数列不再进行判断，设置flag
 */
public static void bubbleSort2(int[] L) {
	boolean flag = true;
	for(int i=0;i<L.length-1 && flag;i++) {//flag为false则说明没有发生交换，退出循环；若为true则说明发生了交换，仍需进一步判断排序
		flag = false;//初始为false，没有数据交换
		for(int j=L.length-1;j>i;j--) {
			if(L[j-1]>L[j]) {//交换
				int temp = L[j];
				L[j] = L[j-1];
				L[j-1] = temp;
				flag = true;
			}
		}
	}
}

堆排序

public static void heapSort(int[] L) {
	//构建大顶堆
	for(int i=(L.length-1)/2;i>=0;i--) heapAdjust(L, i, L.length-1);
	for(int i=L.length-1;i>0;i--) {
		swap(L, 0, i);
		heapAdjust(L, 0, i-1);
	}
}

/**
 * L[begin]之外，L[begin+1...end]已经满足大顶堆
 * 使L[begin...end]成为一个大顶堆
 end是堆的最 后一个节点序号，只用于判断s是否越界
 * @param L
 * @param begin
 * @param end
 */
public static void heapAdjust(int[] L,int begin, int end) {
	int temp = L[begin];//暂存当前节点
	for(int i=begin*2;i<=end;i *= 2) {//i与i+1是begin的左右孩子
		if(i<end && L[i]<L[i+1]) i++;//先找到比较大的孩子
		if(temp >= L[i]) break;//大的孩子与节点比较，父亲大则堆已成立，退出循环
		L[begin] = L[i];//
		begin = i;
	}
	L[begin] = temp;
}

单例模式

多线程懒汉式

public class Singleton {
	private static volatile Singleton instance;
	private Singleton() {

	}

	public static Singleton getInstance() {
		if(null == instance) {
			synchronized(Singleton.class) {
				if(null == instance) {
					instance = new Singleton();
				}
			}
		}
		return instance;
	}
}

volatile 的必要性：new 对象的时候分为三个步骤,请求对象空间，对象初始化，指针指向对象。volatile保证了不发生指令重排，避免在if判断时，double check多线程出错