第二课：复杂排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了第二课：复杂排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1960字，纯文字阅读大概需要3分钟。

内容图文

1.归并排序

	public static void mergeSort(int[] arr) {
		if(arr==null||arr.length<2){
			return;
		}
		mergeSort(arr,0,arr.length-1);
	}
	public static void mergeSort(int[] arr, int l, int r) {
		if (l==r){
			return;
		}
		int mid=l+(r-l)/2;
		mergeSort(arr,l,mid);
		mergeSort(arr,mid+1,r);
		merge(arr,l,mid,r);
	}
	public static void merge(int[] arr, int l, int m, int r) {
		int[] newArr =new int[r-l+1]; //注意这里数组定义的长度
		int left1=l;
		int left2=m+1;
		int i=0;
		while(left1<m+1&&left2<r+1){
			if (arr[left1]<=arr[left2]){
				newArr[i]=arr[left1];
				left1++;
				i++;
			}else{
				newArr[i]=arr[left2];
				left2++;
				i++;
			}
		}
		if (left1==m+1){
			while(left2<r+1){
				newArr[i++]=arr[left2++];
			}
		}
		if (left2==r+1){
			while(left1<m+1){
				newArr[i++]=arr[left1++];
			}
		}
		for (int j=0;j<newArr.length;j++){
			arr[l+i]=newArr[j];
		}
	}

2.荷兰国旗问题
1)小于等于的放左边，大于的放右边

	private static void sort(int[] test, int i, int length, int num) {
		int border=-1;
		for(int j=0;j<length;j++){
			if (test[j]<=num){
				swap(test,border+1,j);//注意交换放的是下标
				border++;
			}
		}
		printArray(test);
	}

2）小于的放左边，等于的放中间，大于的放右边

	public static int[] partition(int[] arr, int l, int r, int num) {
		int small=l-1;
		int big=r+1;
		while (l<big){
			if(arr[l]<num){
				swap(arr,small+1,l);
				small++;
				l++;     //注意当前数小于num的话l是要自增的
			}else if(arr[l]>num){
				swap(arr,big-1,l);
				big--;	//注意当前数大于num的话l是不需要自增的
			}else {
				l++;
			}
		}
		return arr;
	}

3.快速排序

	public static void quickSort(int[] arr) {
		if (arr==null||arr.length<2){
			return;
		}
		quickSort(arr,0,arr.length-1);
	}
	public static void quickSort(int[] arr, int l, int r) {
		if(l<r){//注意这个条件
			int[] p=partition(arr,l,r);
			quickSort(arr,l,p[0]);
			quickSort(arr,p[1],r);
		}
	}
	public static int[] partition(int[] arr, int l, int r) {
		int less=l-1;
		int more=r;
		while(l<more){
			if (arr[l]<arr[r]){
				less++;
				swap(arr,less,l);
				l++;
			}else if(arr[l]>arr[r]){
				more--;
				swap(arr,l,more);
			}else{
				l++;
			}
		}
		swap(arr,l,r);//注意这里是要交换的
		return new int[]{less,more+1};//注意返回的是less
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

内容总结

以上是互联网集市为您收集整理的第二课：复杂排序算法全部内容，希望文章能够帮你解决第二课：复杂排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---