5种排序方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package Sort;

public class SortMethods {
	
	public static void main(String[] args) {
		int a[]={51,56,86,99,-2,5,4,9,3};
		//1.第一种排序，比较简单，冒泡排序
		//bubbleSort(a);
		//bubbleSort2(a);
		//2.选择排序，先遍历一遍，把最大的数的位置找出来，放在最后一个位置，即a[a.length-1]
		//selectSort(a);
		//3.插入排序，即检查第i个数字，如果左边的数字比他大，进行交换，直到左边数字比他小，就停止
		//insertSort(a);
		//4.希尔排序,记录按下标的一定增量（以下用gap表示）分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，
		//当增量减至1时，整个文件恰被分成一组，算法便终止
		//shellSort(a);
		//5.快速排序（这个是经常会用到的排序算法，可以排那种很多数据的算法）,首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，
		//然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
		quickSort(a,0,a.length-1);
		print(a);
	}
	
	//冒泡排序，把大的往后面挪，第一次把最大数排到最后位置（或者最小数，根据题意，此处把最大数排到最后）
	private static void bubbleSort(int a[]) {
		for(int i=0;i<a.length-1;i++){
			for(int j=0;j<a.length-1-i;j++){
				if(a[j]>a[j+1]){
					swap(a,j,j+1);
				}
			}
		}
		print(a);
	}
	//优化之后的冒泡排序
	private static void bubbleSort2(int a[]){
		for(int i=0;i<a.length-1;i++){
			boolean flag=true;
			for(int j=0;j<a.length-1-i;j++){
				if(a[j]>a[j+1]){
					swap(a, j, j+1);
					flag=false;
				}
				
			}
			if(flag==true){
				break;
			}
		}
		print(a);
	}
	
	//选择排序的代码
	private static void selectSort(int a[]){
		for(int i=0;i<a.length-1;i++){
			int k=i;
			for(int j=i+1;j<a.length;j++){
				if(a[k]>a[j]){
					k=j;
				}
			}
			if(k!=i){
				swap(a, i, k);
			}
		}
		print(a);
	}
	
	//插入排序的代码
	private static void insertSort(int a[]){
		for(int i=0;i<a.length-1;i++){
			int temp=a[i+1];
			int j=i;
			while(a[j]>temp){   
				a[j+1]=a[j];    //把a[j]放在a[j+1]的位置上
				j--;			//j-1，继续和左边的数比较
				if(j<0){
					break;
				}
			}
			a[j+1]=temp;
		}
		print(a);
	}
	
	//希尔排序
	private static void shellSort(int a[]){
		for(int gap=(a.length+1)/2;gap>0;){  //此处用gap表示shell排序中的增量
			//接下来用冒泡的排序算法一步步排下去
			for(int i=0;i<a.length-gap;i++){
				for(int j=i;j<a.length-gap;j+=gap){
					if(a[j]>a[j+gap]){
						swap(a, j, j+gap);
					}
				}
			}
			if(gap>1){
				gap=(gap+1)/2;
			}else if(gap==1){
				break;
			}
		}
		print(a);
	}
	
	//快速排序算法，主要思想就是把一个组分成两个组，以第一个数字为界，左边放比他小的数，右边放比他大的数
	public static void quickSort(int a[],int s,int e){  //此处s表示第一个数字的下标，e表示最后一个数字下标
		if(s<e){
			把数组划分成：两个子数组和一个元素
			// a[s:e] ==> a[s:q-1], a[q], a[q+1:e]
			int q=partition(a,s,e);
			quickSort(a, s, q-1);
			quickSort(a, q+1, e);
		}
	}
	private static int partition(int a[], int s, int e) {
		
		int rand = (int)(Math.random()*(e-s));
		swap(a,s,s+rand);
		
		int x=a[s];  //第1个元素为枢轴
		int i=s;
		int j=e+1;
		while(true){
			while(a[++i]<x&&i<e);//在左侧定位到比枢轴大的数
			while(a[--j]>x);//在右侧定位到比枢轴小的数
			if(i>=j){
				break;
			}
			swap(a, i, j);
		}
		swap(a,s,j);
		return j;
	}

	//交换方法
	private static void swap(int a[],int j,int i){
		a[j]=a[i]^a[j];
		a[i]=a[i]^a[j];
		a[j]=a[i]^a[j];
	}
	//输出的方法
	private static void print(int a[]){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
	
}