`
生活的聆听者
  • 浏览: 16560 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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

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

快速排序:快速排序是对冒泡排序的一种改进,冒泡排序是比较的相邻两个元素,故比较的次数以及元素移动的频率比较大。快速排序有效的改进了这一不足,比较的元素位置相隔比较远,并且是由两端向中间比较。
下面基于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");
		}
	}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics