排序算法详解（java版本）_java版本的排序算法

排序算法的介绍

排序的分类：

相关术语：
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度： 一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
n: 数据规模
k: “桶”的个数
In-place: 不占用额外内存
Out-place: 占用额外内存

（1）时间复杂度为O（n^2）的排序算法：

			冒泡排序（交换排序）
			选择排序
			插入排序
			希尔排序（性能略优于O（n^2）,但是又比不上O（nLongn）） （插入排序）
1
2
3
4

（2）时间复杂度为O（nLogn）的排序算法：

		快速排序 （交换排序）--> 最坏时间复杂度为O(n^2)
		归并排序
		堆排序 （选择排序）
1
2
3

（3）时间复杂度为线性的排序算法：

		计数排序
		桶排序
		基数排序（是桶排序的扩展）
1
2
3

（4）按照内部排序外部排序分类！

冒泡排序的实现

public static void main(String[] args){
		int[] array = new int[]{2,5,14,6,5,8,4};
		sort(array);
		System.out.println(Arrays.toString(array));
	}
	public static void sort(int array[]){
		//第一趟排序，就是将最大的数放在最后
		int temp = 0;
		for(int i = 0；i < array.length-1； i++ ){
			boolean isSorted = true;
				for(int j = 0;j < array.lenhth-1-i;j++){
					if(array[j] > array[j + 1]){
						temp = array[j];
						array[i] = array[j + 1];
						array[j + 1] = temp;
			//因为有元素交换，所以不是有序的，标记变为false
						isSorted = false;
					}
				}
			if(isSorded){
				break;
			}
		}
	}
}
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

  冒泡排序的特点：
  （1）一共进行 数组的长度-1次大的循环
  （2）每一趟排序的次数在减少
   (3) 我们发现在某趟排序中，没有发生交换，可以提前结束排序
1
2
3
4

选择排序的实现

public static void sort(int[] array){
		for(int i = 0;i < array.length - 1;i++){
			int minIndex = i;
			int min = array[i];
			for(int j = i + 1;j < array.length;j++){
				if(min  > array[i]){//说明假定的最小值，并不是最小值
					min = array[i];//重置
					minIndex = j;//充值
				}
			}
			//将最小值放在arr[0]位置，也就是交换
			if(minIndex != i){
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
		}	
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

插入排序的实现

//插入的数比较小的时候，后移的次数明显增多，对效率影响较大
public static void insertSort(int[] arr){
	for(int i = 1;i < arr.length;i++){
		//定义待插入的数
		int insertVal = arr[i];
		int insertIndex = i-1 ；//arr[i ]前面数字的下标
		//给insertVal找到插入的位置
		//md：
		//1.insertIndex >= 0 保证在给insertVal找插入的位置，不越界
		//2.insertVal < arr[insertIndex] 待插入的数字，还没有找到插入的位置
		//3.就需要将arr[insertIndex]后移
		while(insertIndex >= 0 && insertVal < arr[insertIndex]){
			arr[insertIndex + 1] = arr[insertIndex];
			insertIndex--;
		}
		//当退出while循环的时候，说明插入的位置找到，insertIndex + 1
		arr[insertIndex + 1] = insertVal;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

希尔排序实现

希尔排序法基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减到1的时候，整个文件恰好被分为一组，算法便终止。
1

//交换法
  public static void shellSort(int[] arr){
  	int temp = 0;
	for(int gap = arr.length/2 ; gap > 0; gap /= 2){
		for(in i =gap;i < arr.length;i++){
		//遍历各组中的元素，步长为gap，共gap组，
			for(int j = i-5;j  >= 0; j-=5){
				if(arr[j] > arr[j + 5]){
					temp = arr[i];
					arr[j] = arr[j + 5];
					arr[j + 5] = temp;
				}
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//移位法
  public static void shellSort(int[] arr){
	for(int gap = arr.length/2 ; gap > 0; gap /= 2){
	//从第gap个元素，逐个对其所在的组进行直接插入排序
		for(in i =gap;i < arr.length;i++){
			int j = i;
			int temp = arr[j];
			if(arr[j] < arr[j - gap]){
				while(j - gap >= 0 && temp < arr[j - gap]){
					//移动
					arr[j] = arr[j - gap]
					j -= gap;
				}
			}
			//当退出while吼，就给temp找到插入的位置
			arr[j] = temp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

快速排序的实现

快速排序的思想：

快速排序实在冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分为两部分，其中一部分的数据都比
另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以
递归进行，以此达到整个数据变成有序的。
1
2
3

//quickSort
public static void quickSort(int[] arr，int left,int right){
	int l = left;
	int r = right;
	int pivot = arr[(left + right) / 2]
	int temp= 0；
	//循环的目的是让比pivot小的放在左边，比pivot大的放在右边,第一次分割
	while( l < r){
		//在pivot的左边一直找，找到大于等于pivot的值，才退出
		while(arr[l] < pivot){
			l += 1;
		}
		while(arr[r] > pivot){
			r -= 1;
		}
		//说明pivot左右两边的值已经按照左边小于pivot，右面大于pivot
		if( l >= r){
			break;
		}
		//交换
		temp = arr[l];
		arr[l] = arr[r];
		arr[r] = temp;
		//交换完之后，发现arr[l] == pivot  r-- --> 前移
		if(arr[l] == pivot){
			r -= 1;
		} 
		//交换完之后，发现arr[r] == pivot  l++ --> 后移
		if(arr[r] == pivot){
			l += 1;
		} 
	}
	//如果 l==r 必须l++,r--否则为栈溢出
	if(l == r){
		l += 1;
		r- = 1;
	}
	//左递归
	if(left < r){
		quickSort(arr,left,r);
	}
	//右递归
	if(right > 1){
		quickSort(arr,l,rgiht);
	}
}


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

归并排序的实现

分治思想的体现
合并次数n-1次
1
2

public class MergeSort{
	public static void main(String[] args) {
		int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 }; 
		int temp[] = new int[arr.length]; //归并排序需要一个额外空间
 		mergeSort(arr, 0, arr.length - 1, temp);
 		System.out.println("归并排序后=" + Arrays.toString(arr));
	}
//分+合方法
	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if(left < right) {
			int mid = (left + right) / 2; //中间索引
			//向左递归进行分解
			mergeSort(arr, left, mid, temp);
			//向右递归进行分解
			mergeSort(arr, mid + 1, right, temp);
			//合并
			merge(arr, left, mid, right, temp);
			
		}
	}
//合并的方法
	/**
	 * 
	 * @param arr 排序的原始数组
	 * @param left 左边有序序列的初始索引
	 * @param mid 中间索引
	 * @param right 右边索引
	 * @param temp 做中转的数组
	 */
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		
		int i = left; // 初始化i, 左边有序序列的初始索引
		int j = mid + 1; //初始化j, 右边有序序列的初始索引
		int t = 0; // 指向temp数组的当前索引
		
		//(一)
		//先把左右两边(有序)的数据按照规则填充到temp数组
		//直到左右两边的有序序列，有一边处理完毕为止
		while (i <= mid && j <= right) {//继续
			//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
			//即将左边的当前元素，填充到 temp数组 
			//然后 t++, i++
			if(arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t += 1;
				i += 1;
			} else { //反之,将右边有序序列的当前元素，填充到temp数组
				temp[t] = arr[j];
				t += 1;
				j += 1;
			}
		}
		//(二)
		//把有剩余数据的一边的数据依次全部填充到temp
		while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
			temp[t] = arr[i];
			t += 1;
			i += 1;	
		}	
		while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
			temp[t] = arr[j];
			t += 1;
			j += 1;	
		}
		
		//(三)
		//将temp数组的元素拷贝到arr
		//注意，并不是每次都拷贝所有
		t = 0;
		int tempLeft = left; // 
		//第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
		//最后一次 tempLeft = 0  right = 7
		while(tempLeft <= right) { 
			arr[tempLeft] = temp[t];
			t += 1;
			tempLeft += 1;
		}	
	}
}
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

基数排序

基数排序基本思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
eg：
将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

第1轮排序 [按照个位排序]:
说明： 事先准备10个数组(10个桶)， 0-9 分别对应 位数的 0-9
(1) 将 各个数，按照个位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出

第2轮排序 [按照十位排序]

(1) 将 各个数，按照十位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出

第3轮排序 [按照百位排序]

(1) 将 各个数，按照百位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出

桶排序的说明：
1.基数排序是对传统桶排序的扩展，速度很快.
2.基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
3.基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
有负数的数组，我们不用基数排序来进行排序。

public class RadixSort {

	public static void main(String[] args) {
		int arr[] = { 53, 3, 542, 748, 14, 214};
		radixSort(arr);
		System.out.println("基数排序后 " + Arrays.toString(arr));
	}

	//基数排序方法
	public static void radixSort(int[] arr) {
		
		//根据前面的推导过程，我们可以得到最终的基数排序代码
		
		//1. 得到数组中最大的数的位数
		int max = arr[0]; //假设第一数就是最大数
		for(int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		//得到最大数是几位数
		int maxLength = (max + "").length();
		
		
		//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
		//说明
		//1. 二维数组包含10个一维数组
		//2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
		//3. 名明确，基数排序是使用空间换时间的经典算法
		int[][] bucket = new int[10][arr.length];
		
		//为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
		//可以这里理解
		//比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
		int[] bucketElementCounts = new int[10];
		
		
		//这里我们使用循环将代码处理
		
		for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
			//(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
			for(int j = 0; j < arr.length; j++) {
				//取出每个元素的对应位的值
				int digitOfElement = arr[j] / n % 10;
				//放入到对应的桶中
				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
				bucketElementCounts[digitOfElement]++;
			}
			//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
			int index = 0;
			//遍历每一桶，并将桶中是数据，放入到原数组
			for(int k = 0; k < bucketElementCounts.length; k++) {
				//如果桶中，有数据，我们才放入到原数组
				if(bucketElementCounts[k] != 0) {
					//循环该桶即第k个桶(即第k个一维数组), 放入
					for(int l = 0; l < bucketElementCounts[k]; l++) {
						//取出元素放入到arr
						arr[index++] = bucket[k][l];
					}
				}
				//第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
				bucketElementCounts[k] = 0;
				
			}
			//System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
			
		}
		
		/*
		
		//第1轮(针对每个元素的个位进行排序处理)
		for(int j = 0; j < arr.length; j++) {
			//取出每个元素的个位的值
			int digitOfElement = arr[j] / 1 % 10;
			//放入到对应的桶中
			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
			bucketElementCounts[digitOfElement]++;
		}
		//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
		int index = 0;
		//遍历每一桶，并将桶中是数据，放入到原数组
		for(int k = 0; k < bucketElementCounts.length; k++) {
			//如果桶中，有数据，我们才放入到原数组
			if(bucketElementCounts[k] != 0) {
				//循环该桶即第k个桶(即第k个一维数组), 放入
				for(int l = 0; l < bucketElementCounts[k]; l++) {
					//取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
			}
			//第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
			bucketElementCounts[k] = 0;
			
		}
		System.out.println("第1轮，对个位的排序处理 arr =" + Arrays.toString(arr));
		
		
		//==========================================
		
		//第2轮(针对每个元素的十位进行排序处理)
		for (int j = 0; j < arr.length; j++) {
			// 取出每个元素的十位的值
			int digitOfElement = arr[j] / 10  % 10; //748 / 10 => 74 % 10 => 4
			// 放入到对应的桶中
			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
			bucketElementCounts[digitOfElement]++;
		}
		// 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
		index = 0;
		// 遍历每一桶，并将桶中是数据，放入到原数组
		for (int k = 0; k < bucketElementCounts.length; k++) {
			// 如果桶中，有数据，我们才放入到原数组
			if (bucketElementCounts[k] != 0) {
				// 循环该桶即第k个桶(即第k个一维数组), 放入
				for (int l = 0; l < bucketElementCounts[k]; l++) {
					// 取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
			}
			//第2轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
			bucketElementCounts[k] = 0;
		}
		System.out.println("第2轮，对个位的排序处理 arr =" + Arrays.toString(arr));
		
		
		//第3轮(针对每个元素的百位进行排序处理)
		for (int j = 0; j < arr.length; j++) {
			// 取出每个元素的百位的值
			int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
			// 放入到对应的桶中
			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
			bucketElementCounts[digitOfElement]++;
		}
		// 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
		index = 0;
		// 遍历每一桶，并将桶中是数据，放入到原数组
		for (int k = 0; k < bucketElementCounts.length; k++) {
			// 如果桶中，有数据，我们才放入到原数组
			if (bucketElementCounts[k] != 0) {
				// 循环该桶即第k个桶(即第k个一维数组), 放入
				for (int l = 0; l < bucketElementCounts[k]; l++) {
					// 取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
			}
			//第3轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
			bucketElementCounts[k] = 0;
		}
		System.out.println("第3轮，对个位的排序处理 arr =" + Arrays.toString(arr)); */
		
	}
}

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
151
152
153