数据结构几种排序算法整理

最新整理书籍，无意间翻出大学时期数据结构课本，随便翻阅了其中关于排序这一章，粗略的看了下突然觉得比较陌生，作为计算机基础的东西，自己工作了反而用的比较少，平时自己也没有太关注，为了以后万一需要找工作方便复习这些东西，今写于此。

快速排序：快速排序是对冒泡排序的一种改进，冒泡排序是比较的相邻两个元素，故比较的次数以及元素移动的频率比较大。快速排序有效的改进了这一不足，比较的元素位置相隔比较远，并且是由两端向中间比较。
下面基于java语言实现快速排序算法。

	private static int quickSort(int low, int high , int a[] ) {
		int tmp = a[low]; //一般选取数组第一个元素为比较的元素
		while (low < high) {
			//从数组的右边也就是数组末尾向前开始比较，小的放在数组前段，大的放置于后段
			//当后段元素比tmp大，则不需移动直接进行下一个元素比较
			while ((low < high) && a[high] > tmp) {
				high--;
			}

			//当遇到后段元素比tmp小直接把后端元素交换至迁low位置
			a[low] = a[high];

			//tmp交换至后端之后，开始和前段元素进行比较
			while (low < high && a[low] < tmp) {
				low++;
			}

			//交换前端元素到后端
			a[high] = a[low];
		}
		//这是第一趟排序完成，tmp此时至于数组个元素大小的最中间
		a[low] = tmp;
		//返回中间位置即数组中间位置的下标
		//到此时整个数组的排序并未完成，完成的只是一趟，后续的排序原理相同，只是比较的数组起始位置下标不同，故可以采用递归算法实现。
		return low;
	}

	private static void quick(int low, int high , int a[] ) {
		if (a.length > 0 && low < high){
			int middle = quickSort(low, high, a);
			quick(low, middle - 1, a);
			quick(middle + 1, high, a);
		}

插入排序：

	public void insertSort1(int a[]) {
		int j; // 当前值的位置
		int i; // 指向j前的位置
		int key; // 当前要进行插入排序的值
		// 从数组的第二个位置开始遍历值
		for (j = 1; j < a.length; j++) {
			key = a[j];
			i = j - 1;
			// a[i]比当前值大时，a[i]后移一位,空出i的位置，好让下一次循环的值后移
			while (i >= 0 && a[i] > key) {
				a[i + 1] = a[i]; // 将a[i]值后移
				i--; // i前移
			}// 跳出循环(找到要插入的中间位置或已遍历到0下标)
			a[i + 1] = key; // 将当前值插入

			for (int n = 0; n < a.length; n++) {
				System.out.print(a[n] + " ");
			}
			System.out.println("\n");
		}
	}