java排序

来自网络

package com.ssm.common;

public class Sort {

	/**
	 * 冒泡排序
	 * 
	 * @param data
	 */
	public void bubbleSort(int[] data) {

		for (int i = 0; i < data.length; i++) {
			for (int j = i + 1; j < data.length; j++) {
				if (data[i] > data[j]) {
					int temp = data[i];
					data[i] = data[j];
					data[j] = temp;
				}
			}
		}

	}

	/**
	 * 选择排序
	 * 
	 * @param data
	 */
	public void selectSort(int[] data) {
		int cur_small_index;// 当前最小值所处位置
		for (int i = 0; i < data.length; i++) {
			cur_small_index = i;
			for (int j = i + 1; j < data.length; j++) {
				if (data[cur_small_index] > data[j]) {
					cur_small_index = j;
				}
			}
			// 交换
			int temp = data[i];
			data[i] = data[cur_small_index];
			data[cur_small_index] = temp;
		}
	}
	
	/**
	 * 插入排序
	 * @param data
	 */
	public void insertSort(int[] data) {
		for (int i = 1; i < data.length; i++) {

			int temp = data[i];// 保存第i个数的值
			int j;
			//从第0到i位置进行排序
			for (j = i; j > 0; j--) {
				if (data[j - 1] > temp)
					data[j] = data[j - 1];
				else
					break;
			}
			data[j] = temp;// 找到合适位置后，插入即可
		}
	}
	
	/**
	 * 快速排序
	 * @param data
	 */
	public void quickSort(int data[], int low, int high) {
		int i= low, j= high, division;
		
		//通过这个条件结束循环
		if (low < high) {
			//第一步，选择基准，这里就选择第一个数
			division = data[i];
			//第二步，把数组中小于基准的放到数组左边，大于基准的放到数组右边
			while (i < j) {
				// 1.从右往左找到第一个小于pivot的元素
				while (i < j && data[j] > division)
					j--;
				if (i < j) {
					data[i] = data[j];// 第i个元素保存右边第一个小于pivot的
					i++;
				}
				//2.从左往右找，找到第一个大于pivot的元素
				while (i < j && data[i] < division)
					i++;
				if (i < j) {
					data[j] = data[i];// 第j个元素保存左边第一个大于pivot的
					j--;
				}
			}
			data[i] = division;//第i个位置就是基准的位置
			
			//第三步，递归调用把基准左边，右边的分别排序
			quickSort(data, low, i - 1);
			quickSort(data, i + 1, high);

		}
	}
	
	/**
	 * 希尔排序
	 * @param data
	 */
	public void shellSort(int[] data) {
		//这里把增量初始化为数组长度的一半，然后依次减半
		for (int interval = data.length / 2; interval > 2; interval /= 2) {
			for (int j = 0; j < interval; j++) {
				shellInsertSort(data, j, interval);//每一组内进行插入排序
			}
		}
		shellInsertSort(data, 0, 1);//最后进行一次所有元素的排序
	}

	//这个算法其实就是一次插入排序，只不过有个增量interval
	private void shellInsertSort(int[] data, int start, int interval) {
		int temp;
		for (int i = start+interval; i < data.length; i+=interval) {
			// 把第i个位置的数插到前i-1个数的某个位置，保证前i个数排好序
			temp = data[i];// 首先保存第i个数的值
			int j;
			for (j = i; j >=interval; j-=interval) {

				if (data[j - interval] > temp)
					data[j] = data[j - interval];
				else
					break;
			}
			data[j] = temp;// 找到合适位置后，插入即可
		}
	}
	
	
	/** 
	 *  归并排序
	 * @param data 是需要排序的原数组
	 * @param temp 是个临时数组，数组大小和data一样
	 * @param left 左边界
	 * @param right 右边界
	 */
	public void mergeSort(int[] data, int[] temp, int left, int right) {
		
		if (left >= right)//就剩一个元素时，直接返回，直接合并就行了。
			return;
		
		int mid = (left + right) / 2;//获得数组的中间位置
		mergeSort(data, temp, left, mid);//对左半部分递归
		mergeSort(data, temp, mid + 1, right);//对右半部分递归
		
		//把原数组中的值保存到临时数组中
        System.arraycopy(data, 0, temp, 0, data.length);
        
		//下面是完成合并，也就是把左右两个有序的数组合并到一个数组中，并使之有序
		int l= left;
		int r = mid + 1;
		for (int cur = left; cur <= right; cur++) {
			if (l == mid + 1)//第一个数组全部比较完毕，只要直接复制第二个数组的条目到合并数组即可
				data[cur] = temp[r++];
			else if (r > right)//第二个数组全部比较完毕，只要直接复制第一个数组的条目到合并数组中即可
				data[cur] = temp[l++];
			else if (temp[l] < temp[r])//把比较的两个条目中关键值小的放到合并数组中
				data[cur] = temp[l++];
			else
				data[cur] = temp[r++];
		}
	}

}