温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

各种排序算法的编写教程

发布时间:2021-10-12 14:18:05 来源:亿速云 阅读:103 作者:iii 栏目:编程语言

本篇内容主要讲解“各种排序算法的编写教程”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“各种排序算法的编写教程”吧!

冒泡排序:

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
		show(a);
		bubbleSort(a);
		show(a);
	}

	private static void bubbleSort(int[] a) {
		for(int i=0;i<a.length-1;i++){
			for(int j=0;j<a.length-i-1;j++){
				if(a[j]>a[j+1]){
					int tmp = a[j];
					a[j] = a[j+1];
					a[j+1] = tmp;
				}
			}
		}
	}

	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}

}

快速排序(无重复值):

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,3,12,23,110};
		show(a);
		quickSort(a,0,a.length-1);
		show(a);
	}

	private static void quickSort(int[] a, int start, int end) {
		if (start>=end)
			return;
		int i=start;
		int j=end;
		int index = start;
		while(i<j){
			while(a[j]>a[index]){
				j--;
			}
			index = swap(a,j,index);
			while(a[index]>a[i]){
				i++;
			}
			index = swap(a,i,index);
		}
		quickSort(a, start, index-1);
		quickSort(a, index+1, end);
	}

	private static int swap(int[] a, int n, int index) {
		int tmp = a[n];
		a[n] = a[index];
		a[index] = tmp;
		return n;
	}

	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}

}

快速排序(可含重复值)

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,345};
		show(a);
		quickSort2(a,0,a.length-1);
		show(a);
	}

	private static void quickSort2(int[] a, int start, int end) {
		if (start>=end)
			return;
		int i=start;
		int j=end;
		int index = end;
		while(i<j){
			while(a[j]>a[index]){
				j--;
			}
			if (j!=index && a[j]==a[index]){
				index = swap(a,--j,index);
			}else{
				index = swap(a,j,index);
			}
			while(a[index]>a[i]){
				i++;
			}
			if (i!=index && a[i]==a[index]){
				index = swap(a,++i,index);
			}else{
				index = swap(a,i,index);
			}
		}
		quickSort2(a, start, index-1);
		quickSort2(a, index+1, end);
	}

	private static int swap(int[] a, int n, int index) {
		int tmp = a[n];
		a[n] = a[index];
		a[index] = tmp;
		return n;
	}

	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}
}

堆排序

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
		show(a);
		heapSort(a);
		show(a);
	}

	private static void heapSort(int[] a) {
		//建立最大堆
		int size = a.length;
		for(int i=size/2-1;i>=0;i--){
			createBigHeap(a,i,size-1);
		}
		//排序
		for(int j=0;j<size-1;j++){
			int tmp=a[0];
			a[0]=a[size-1-j];
			a[size-1-j]=tmp;
			createBigHeap(a,0,size-2-j);
		}
	}

	private static void createBigHeap(int[] a, int start, int end) {
		int tmp = a[start];
		int j = 2*start+1;
		while(j<=end){
			if (j<end && a[j]<a[j+1]){
				j++;
			}
			if (a[j]>tmp){
				a[start] = a[j];
				start = j;
				j = 2*j+1;
			}else{
				break;
			}
		}
		a[start] = tmp;
	}


	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}
}

插入排序

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,-1,3};
		show(a);
		insertSort(a);
		show(a);
	}

	private static void insertSort(int[] a) {  
        for(int i=0;i<a.length-1;i++){  
            int n = i+1;  
            int tmp = a[n];  
            for(int j=i;j>=0;j--){  
                if(tmp<a[j]){  
                    a[n] = a[j];  
                    n=j;
                }  
            }
            if (a[n]!=tmp)
            	a[n] = tmp; 
        }  
    }

	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}

}

折半插入排序

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,7,345,2,2,7,2,7,23,2,345,7,32,5,4,-1,3,7,2,3,2,3,4,2,1,2,4,5,3,345,3,2};
		show(a);
		insertSort2(a);
		show(a);
	}

	private static void insertSort2(int[] a) {  
		 for(int i=0;i<a.length-1;i++){    
	            int n = i+1; 
	            int tmp = a[n];    
	            if (tmp>a[i])
	            	continue;
	            int low = 0;
	            int high = i;
	            int mid = (high+low)/2;
	            while(high>=low){
	            	mid = (high+low)/2;
	                if(tmp<a[mid]){    
	                    high = mid -1;
	                }else if(tmp>a[mid]){
	                	low = mid + 1;
	                } else{
	                	low=mid;
	                	break;
	                } 
	            }  
	           for(int j=n;j>mid;j--){
	        	   a[j] = a[j-1];
	           }
	           a[low] = tmp;
	        }    
    }

	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}

}

希尔排序

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,-1,3,2,3,5,7,8,90,1};
		show(a);
		shellSort(a);
		show(a);
	}

	private static void shellSort(int[] a) {
		shellSort(a,a.length);
	}

	private static void shellSort (int[] a, int n){
	     int i, j, k, temp, gap;
	     int[] gaps = { 1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
	                    213331,543749,1355339,3501671,8810089,21521774,
	                    58548857,157840433,410151271,1131376761,2147483647 };
	     for (k=0; gaps[k]<n; k++);
	     while (--k >= 0){
	         gap = gaps[k];
	         for (i=gap; i<n; i++){
	             temp = a[i];
	             j = i;
	             while (j>=gap && a[j-gap]>temp){
	                 a[j] = a[j-gap];
	                 j = j-gap;
	             }
	             a[j] = temp;
	         }
	     }
	 }

	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}

}

选择排序

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,-1};
		show(a);
		selectSort(a);
		show(a);
	}

	private static void selectSort(int[] a) {
		for (int i = 0; i < a.length-1; i++) {
			int min = i;
			for (int j = i+1; j < a.length; j++) {
				if (a[j]<a[min])
					min = j;
			}
			if (min!=i){
				int tmp = a[i];
				a[i] = a[min];
				a[min] = tmp;
			}
		}
	}


	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}

}

归并排序

public class SortTest {
	public static void main(String[] args) {
		int[] a = {345,7,32,5,4,-1,3,2,3,5,7,8,90,1,432,1};
		show(a);
		mergeSort(a);
		show(a);
	}

	private static void mergeSort(int[] a) {
		//找出中间值
		int mid = a.length/2;
		//申请空间存储中间索引以左的值
		int[] left = setValue(a,0,mid);
		if (left.length>1){//继续拆分左边,直到元素值为1个
			mergeSort(left);
		}
		//申请空间存储中间索引以右的值
		int[] right = setValue(a,mid,a.length);
		if (right.length>1){//继续拆分右边,直到元素值为1个
			mergeSort(right);
		}
		//将左右值合并
		merge(a,left,right);
	}


	private static void merge(int[] a , int[] left, int[] right) {
		int i=0,j=0,k=0;
		for(;i<left.length && j<right.length;){
			if (left[i]<right[j]){
				a[k++] = left[i++];
			}else{
				a[k++] = right[j++];
			}
		}
		for(;i<left.length;i++){
			a[k++] = left[i];
		}
		for(;j<right.length;j++){
			a[k++] = right[j];
		}
	}


	private static int[] setValue(int[] a, int start,int length) {
		int[] x = new int[length-start];
		for (int i = 0; i < x.length; i++) {
			x[i] = a[start++];
		}
		return x;
	}


	private static void show(int[] a) {
		System.out.println(Arrays.toString(a));
	}

}

到此,相信大家对“各种排序算法的编写教程”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI