数据结构中五种简单的排序

    今天复习了一下数据结构的排序(插入、冒泡、快速、选择、归并)，现在备份、备份。

/**
	 * 插入排序 
	 * 原理： 
	 * 1：将某一元素在一有序队列中找到合适的位置 
	 * 2：将该位置后面的元素分别后移一位 
	 * 3：将该元素复制到合适的位置
	 */
	public void InsertSort(int[] insertList) {
		int j = 0, temp;
		for (int i = 1; i < insertList.length; i++) {
			if (insertList[i] < insertList[i - 1]) {
				temp = insertList[i];
				insertList[i] = insertList[i - 1];
				for (j = i - 1; j > 0; j--) {
					if (insertList[j] > temp) {
						insertList[j] = insertList[j - 1];
					} else {
						break;
					}
				}
				insertList[j] = temp;
			}
		}
	}

/**
	 * 冒泡排序 
      *原理： 将第一个元素与第二个元素进行比较，若为逆序则交换，
	 * 再将第二个 元素与第三个元素进行比较，若为逆序则交换，依次类推为冒泡排序。
	 */
	public void maoPao(int[] maoPaoList) {
		int temp, total = maoPaoList.length;
		for (int i = 0; i < total - 1; i++) {
			for (int j = 0; j < total - 1 - i; j++) {
				if (maoPaoList[j] > maoPaoList[j + 1]) {
					temp = maoPaoList[j + 1];
					maoPaoList[j + 1] = maoPaoList[j];
					maoPaoList[j] = temp;
				}
			}
		}
	}

/**
	 * 快速排序
	 * 原理：
	 * 在无序列表中选定一个支点元素，将比该元素小的元素放到左边，
	 * 大的元素放到右边，把该元素左右两个子序列执行以上操作记得到有序表
	 * 
	 */
	private static int[] quickList = { 5, 3, 6, 2, 7, 1, 9, 54, 23, 1, 3, 5, 7 };

	public void quickSort(int low, int high) {
		if (low < high) {
			int pivotdoc = partition(low, high);
			quickSort(low, pivotdoc - 1);
			quickSort(pivotdoc + 1, high);
		}
	}

	public int partition(int low, int high) {
		int pivot = quickList[low];
		quickList[0] = quickList[low];
		while (low < high) {
			while (low < high && quickList[high] >= pivot)
				high--;
			quickList[low] = quickList[high];
			while (low < high && quickList[low] <= pivot)
				low++;
			quickList[high] = quickList[low];
		}
		quickList[low] = quickList[0];
		return low;
	}

/**
	 *选择排序
	 *原理： 
	 *第一个元素与后面的元素依次比较，如果为逆序则交换，依次类推为选择排序
	 * 
	 */
	public void selectSort(int[] selectList) {
		int count, temp;
		for (int i = 0; i < selectList.length; i++) {
			count = i;
			for (int j = i + 1; j < selectList.length; j++) {
				if (selectList[count] > selectList[j]) {
					count = j;
				}
			}
			temp = selectList[count];
			selectList[count] = selectList[i];
			selectList[i] = temp;
		}
	}

	/**
	 * 归并排序
	 * 原理：
	 * 将两个或两个有序表合成一个新的有序表
	 * 
	 */
	public int[] mergeSort(int[] mergeList, int low, int high) {
		int[] mergeCopy = new int[high + 1];
		if (low == high) {
			mergeCopy[low] = mergeList[high];
		} else {
			int mid = (low + high) / 2;
			int[] sqList1 = new int[high + 1];
			int[] sqList2 = new int[high + 1];
			int[] sqList = new int[high + 1];
			sqList1 = mergeSort(mergeList, low, mid);
			sqList2 = mergeSort(mergeList, mid + 1, high);
			int m = low, n = mid + 1;
			while (m <= mid) {
				sqList[m] = sqList1[m];
				m++;
			}
			while (n <= high) {
				sqList[n] = sqList2[n];
				n++;
			}
			mergeCopy = merge(sqList, low, mid, high);
		}
		return mergeCopy;
	}

	public int[] merge(int[] sqList, int low, int mid, int high) {
		int[] mergeList = new int[high + 1];
		int i, j, k = low;
		for (i = low, j = mid + 1; i <= mid && j <= high;) {
			if (sqList[i] < sqList[j]) {
				mergeList[k] = sqList[i];
				k++;
				i++;
			} else {
				mergeList[k] = sqList[j];
				k++;
				j++;
			}
		}
		while (i <= mid) {
			mergeList[k] = sqList[i];
			k++;
			i++;
		}
		while (j <= high) {
			mergeList[k] = sqList[j];
			k++;
			j++;
		}
		return mergeList;
	}