算法学习--各种排序的思想和实现

本文总阅读量次
发表于   |  

一、直接插入排序

１、思想

从第二个元素到末尾，逐个向前面的有序序列插入，使之成为有序序列。

  • 插入过程在有序序列中从后向前比较，遇到比当前元素大的元素，则把它向后移动一个。
    遇到比当前元素小的元素，直接break。把当前元素放到比它小的元素的下一个。

2、代码

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
package Sort;

import java.util.Scanner;

/**
 * 直接插入排序
 * 
 * Author: Wayne 13186259527@163.com
 */
public class InsertSort {
    
    private static void Insertsort(int[] arr, int n) {
			int x = 0;
			int j;
			int i ;
			for (i = 1; i < n; i++) {
				x = arr[i];
				for ( j = i-1; j >=0; j--) {
					if (arr[j] > x) {
						arr[j+1] = arr[j];
					}
					else {
						break;
					}
				}
				arr[j+1] = x;
			}
	}
    
	public static void main(String[] args) {
		System.out.println("please input a order number and order");
		System.out.println("eg: 5 回车  5 8 2 4 9(以空格隔开)");
		/**
		 * 输入序列个数
		 */
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n="+ n);
		/**
		 * 输入序列
		 */
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： "+i);
		}
		/**
		 * 排序
		 */
		Insertsort(arr, n);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}

二、直接选择排序

１、思想

在无序区间内选择一个最小值(或最大值)与无序区间第一个交换，并且每趟都缩小无序区间，直到无序区间只剩一个元素。

2、代码

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
package Sort;

import java.util.Scanner;

/**
 * 直接选择排序
 * 
 * Author: Wayne 13186259527@163.com
 */
public class Selectsort {
    
    private static void Selectsort(int[] arr, int n) {
		int x = 0;
		int j;
		int i;
		int min;
		int t;
		for (i = 0; i < n - 1; i++) {
			min = i;
			for (j = i; j < n; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			if (min != i) {
				t = arr[min];
				arr[min] = arr[i];
				arr[i] = t;
			}
		}
	}
    
	public static void main(String[] args) {
		System.out.println("please input a order number and order");
		System.out.println("eg: 5 回车  5 8 2 4 9(以空格隔开)");
		/**
		 * 输入序列个数
		 */
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n=" + n);
		/**
		 * 输入序列
		 */
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： " + i);
		}
		/**
		 * 排序
		 */
		Selectsort(arr, n);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}

三、冒泡排序

1、思想

通过相邻元素的比较交换，让当前最大的元素“冒泡”般的放在最后

2、实现

  • 外层循环0<=i<n-1(因为比较至剩下一个元素便不用比较了，已经有序)
  • 内层循环1<=j<n-i(第一趟比较的对象时全部元素，第二趟是从开始到n-1的元素，之后每次减少一个。直到剩下第一个元素为止)
  • 如果有一趟外层循环结束没有移动元素，则说明已经有序，直接退出返回

3、代码

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
package Sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 冒泡排序
 * 
 * Author: Wayne 13186259527@163.com
 * 
 * 
 * 这是选择排序(⊙ˍ⊙)：
 * 外层循环n-1趟
 * 		内层循环次数逐层减少，每趟找到最大的下标。
 * 		然后和最后一个元素交换。
 * 
 * 这才是冒泡排序：
 * 外层循环n-1趟
 * 		内层循环让每个相邻元素比较，让大的向后移动。
 * 		如果有一趟没有移动元素，则说明已经有序，直接退出返回
 *
 *两层循环：外层 i:0到n-1
 *			内层 j:1到n-i
 */
public class BubbleSort {
    
    /**
	 * 这个不太像严格意义的冒泡，因为没有连续相互比较，而是直接找最大的
	 * 不对，这是直接选择排序啊
	 * 卧槽。。。
	 * @param arr
	 */
	private static void Bubblesort(int[] arr) {
		int max;
		int t;
		int j;
		for (int i = 0; i < arr.length-1; i++) {
			max = 0;
			for ( j = 1; j < arr.length-i; j++) {
				if (arr[j] > arr[max]) {
					max = j;
				}
			}
			t = arr[max];
			arr[max] = arr[j-1];
			arr[j-1] = t;
			
		}
	}
	private static void Bubblesort2(int arr[]){
		int i,j,t;
		boolean flag;
		for ( i = 0; i < arr.length-1; i++) {
			flag = true;
			for ( j = 1; j < arr.length-i; j++) {
				if(arr[j-1] > arr[j]){
					t = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = t;
					flag = false;
				}
			}
			if(flag) break;
		}
	}
	public static void main(String[] args) {
		System.out.println("please input a order number and order");
		System.out.println("eg: 5 回车  5 8 2 4 9(以空格隔开)");
		/**
		 * 输入序列个数
		 */
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n=" + n);
		/**
		 * 输入序列
		 */
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： " + i);
		}
		Bubblesort2(arr);
		//输出
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}

四、归并排序

１、思想

分治法，将大的问题分为更小的问题，分到很容易解决后解决。然后不断合并为最终答案

  • 分解：将问题分解，直到不能再分解
  • 解决：使用归并分别递归地排列两个子序列
  • 合并：合并两个已排序的序列为有序序列

2、代码

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
package Sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 归并排序
 * 
 * Author: Wayne 13186259527@163.com
 *
 */
public class MergeSort {
    
    private static void Mergesort(int[] arr, int p, int r) {
		if (p < r) {
			int q = (p + r) / 2;
			Mergesort(arr, p, q);
			Mergesort(arr, q + 1, r);
			Merge(arr, p, q, r);
		}
	}
    /**
	 * @param arr 	存放所有数据的数组
	 * @param p		当前两个子序列的最开始的下标
	 * 
	 * arr[p..q] 有序  arr[q+1..r] 有序 但两个区间之间无序，所有要存在Merge函数
	 * 
	 * @param q		当前两个子序列的分隔开的位置
	 * @param r		当前两个子序列的最后的下标
	 */
	private static void Merge(int[] arr, int p, int q, int r) {
		int arr1[] = new int[q-p+1];
		int arr2[] = new int[r-q];
		for (int i = 0; i < arr1.length; i++) {//存放前面一半数据
			arr1[i] = arr[p + i];
		}
		for (int i = 0; i < arr2.length; i++) {//存放后面一半数据
			arr2[i] = arr[q + 1 +i];
		}
		int i = 0;
		int j = 0;
		int k;
		for ( k = p; k <= r; k++) {//合并2边数据
			if(arr1[i] < arr2[j]){
				arr[k] = arr1[i];
				i++;
			}else {
				arr[k] = arr2[j];
				j++;
			}
			if( (i == arr1.length) || (j == arr2.length) ){
				break;
			}
		}
		if(i == arr1.length){
			//前面一半先跑完，把另一半后面的直接放上去
			for (int m = j; m < arr2.length; m++) {
				arr[++k] = arr2[m];
			}
		}
		else {
			for (int m = i; m < arr1.length; m++) {
				arr[++k] = arr1[m];
			}
		}
	}
    
	public static void main(String[] args) {
		System.out.println("please input a order number and order");
		System.out.println("eg: 5 回车  5 8 2 4 9(以空格隔开)");
		/**
		 * 输入序列个数
		 */
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n=" + n);
		/**
		 * 输入序列
		 */
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： " + i);
		}
		/**
		 * 排序
		 */
		Mergesort(arr, 0, n - 1);
		
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}

五、 堆排序

１、思想

利用大根堆的性质，每次将堆顶元素和最后一个元素交换，然后不带最后一个位置的元素的调整为新的大根堆。迭代这个过程，直到堆的大小减小至1

  • 建队：自输入的最后一个节点的父节点到根节点循环调用堆调整算法MAXHEAPIFY，完成后则是大根堆(或小根堆)。
  • 排序：
  • (1)将堆顶元素和最后一个元素交换，并且将堆的大小heapsize减一。然后对堆顶调用MAXHEAPIFY。
  • (2)一直循环调用至堆的heapsize为1为止。

2、堆调整函数MAXHEAPIFY(arr,i)

调整存储在arr里面的以i为根节点的堆为大根堆

隐含前提：以i为根的堆，它的左右子女的二叉树都是满足大根堆性质的。但是以i节点为根的堆可能不满足大根堆性质

  • 计算i的左右子女下标
  • 左子女节点不越界并且数值大于i节点的值，则max=left,否则max=i
  • 右子女不越界并且数值大于max节点的值，则max=right
  • 交换节点max和i的数值
  • 若max和i节点不是同一个节点。则说明以i为根的堆的堆顶元素和它的某个子女交换了，则以i的某个子女为根的堆可能又不满足大根堆的性质了。所以递归调用MAXHEAPIFY(arr,max)

3、代码

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
package Heap;

import java.util.Scanner;

/**
 * 堆排序
 * 
 * Author: Wayne 13186259527@163.com
 * 
 * heapsize全局变量，用来指示当前需要大根调整的元素个数。
 * 完成堆排序的最大输出在最后。
 */

public class HeapSort {
	public static int heapsize;
    
    /**
	 * @param MaxHeap 大根堆数组
	 */
	private static void HeapSort(int[] MaxHeap) {
		for (int i = MaxHeap.length - 1; i >= 0; i--) {
			int t;
			t = MaxHeap[0];
			MaxHeap[0] = MaxHeap[i];
			MaxHeap[i] = t;
			/**
			 * 这里heapsize全局变量每次递减，保证了每次放在后面的数据不会再参与对调整。
			 * 从而变得逐步有序
			 */
			heapsize--;
			maxHeapify(MaxHeap, 0);
		}
	}
	private static int[] buildMaxHeap(int arr[]) {
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			maxHeapify(arr, i);
		}
		return arr;
	}
	private static void maxHeapify(int a[], int i) {
		int left = i * 2 + 1;
		int right = (i * 2) + 2;
		/*
		 * 这句话是有问题的，如果有一个下标是越界的，而另一个没有，则会出现比较不完全的问题 
		 * if(left >= heapsize || right>= heapsize)//把大于号改为了大于等于，小于号改为了小于等于 
		 * return;
		 */
		int max;
		int tmp;
		// 此处越界判断应放在前面的条件判断，否则会出现下标越界的错误
		if ((left < heapsize) && (a[left] > a[i]))
			max = left;
		else
			max = i;
		if ((right < heapsize) && (a[right] > a[max]))
			max = right;
		if (max != i) {
			tmp = a[max];
			a[max] = a[i];
			a[i] = tmp;
			maxHeapify(a, max);
		}
	}
	public static void main(String[] args) {

		System.out.println("please input a order number and order");
		System.out.println("eg: 5 回车  5 8 2 4 9(以空格隔开)");
		/**
		 * 输入序列个数
		 * 
		 */
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n=" + n);
		/**
		 * 输入序列
		 */
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[n];
		heapsize = arr.length;
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： " + i);
		}
		int MaxHeap[] = new int[arr.length];
		// 建堆
		MaxHeap = buildMaxHeap(arr);
		// 把构建好的大顶堆进行排序
		HeapSort(MaxHeap);
		// 输出
		for (int i : MaxHeap) {
			System.out.print(i + " ");
		}
	}
}

六、快速排序

1、思想

基于分治法，以一个元素为分界线，把数组划分为2个子数组。让这个元素在中间，左边的数组的元素都小于它，右边的数组的元素都大于它。左右数组递归地进行上述操作，直至问题规模为1。

和归并排序的区别：

归并排序是先分解问题，然后再一层一层的合并(重点在合并)

快速排序是以一个元素为划分基准来分解问题，然后一层一层的分解。不用合并(重点在分解)

2、代码

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
package Sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 快排
 * 
 * Author: Wayne 13186259527@163.com
 *
 */
public class QuickSort {
    
    private static void Quicksort(int[] arr, int p, int r) {
		if (p < r) {
			int q = Partition(arr, p, r); 
			Quicksort(arr, p, q-1);
			Quicksort(arr, q+1, r);
		}
	}
    private static int Partition(int[] arr, int p, int r) {
		/**
		 * 大概写一下这个过程，以备以后看的时候更快
		 * x:分隔元素
		 * i:指示当前最后一个小于等于x的元素。
		 * j:指示遍历的每个元素
		 * t:用作交换
		 * 
		 * 用j扫描每个元素，当元素大于x时，则什么都不干。
		 * 					当元素小于等于x时，则把i指示的下一个元素(当前从前向后第一个大于x的数据)
		 * 					和这个元素(小于等于x)交换。
		 * 最后把x和i+1的元素互换。返回i+1.
		 * 
		 * i元素指示的值，就是两边的分割线。下标小于等于i的元素都小于等于x。大于i的都大于x。
		 * x和i+1换了后，即x左边的都小于等于x，x右边的都大于x。
		 */
		int x = arr[r];
		int i = p-1;
		int t;
		for (int j = p; j < r; j++) {
			if (arr[j] <= x) {
				i++;
				t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
		}
		t = arr[i+1];
		arr[i+1] = arr[r];
		arr[r] = t;
		return i+1;
	}
	public static void main(String[] args) {
		System.out.println("please input a order number and order");
		System.out.println("eg: 5 回车  5 8 2 4 9(以空格隔开)");
		/**
		 * 输入序列个数
		 */
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n=" + n);
		/**
		 * 输入序列
		 */
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： " + i);
		}	
		Quicksort(arr, 0, arr.length-1);
		
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}

七、计数排序

1、前提

输入的元素在一定范围内，例如[0,k]

2、思想

对于每一个输入元素x，确定小于x的元素的个数。那么x最终的位置即可确定。

3、实现

  • 输入数组a[],输出数组b[],辅助数组c[k+1]
  • c[]中的每个元素表示小于等于该下标的元素的个数
  • 把数组a的每个元素都放入数组b中，下标为以该元素为下标c数组的值。
  • 把c数组中对应元素减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
package Sort;

import java.io.IOException;
import java.util.Scanner;
/**
 * 计数排序
 * 
 * Author: Wayne 13186259527@163.com
 * 
 * 例如：9 回车
 * 4 2 5 9
 * 排序结果 2 4 6 9
 *
 *思想：对于每一个输入元素x，确定小于x的元素的个数。那么x最终的位置即可确定。
 */
public class CountSort {

	static void Countsort(int a[], int b[], int k) {
		//k代表所有元素都小于等于k
		k += 1;
		int c[] = new int[k];
		
		for (int i : c) {
			i = 0;
			//System.out.println(i + "  " + c[i]);
		}
		for (int j : a) {
			c[j] = c[j] + 1;
		}
		for (int i = 1; i < c.length; ++i) {
			c[i] = c[i] + c[i - 1];
		}
		//for (int j = a.length - 1; j >= 0; --j) {
		for (int j = 0; j <= a.length - 1; ++j) {

			b[c[a[j]] - 1] = a[j];//这里因为b数组下标从0开始
			 /**
			  * 例如输入为a = [4 6 2 5]  b = [0 0 0 0]
			  * 	c = [0 0 1 1 2 3 4]
			  * 	6对应的小于等于6的是c[6],b[4]已经越界了
			  */
			c[a[j]]--;
			//c[a[j]]++;
		}
	}
	public static void main(String[] args) throws IOException {
		System.out.println("请输入小于等于n的数字，以空格分隔开:");
		System.out.println("例如：9 回车");
		System.out.println("4 2 5 9");
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n="+ n);
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[split.length];
		for (int i = 0; i < arr.length; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： "+i);
		}
		int brr[] = new int[arr.length];
		Countsort(arr, brr, n);
		for (int i : brr) {
			System.out.print(i + " ");
		}
	}
}

八、基数排序

1、思想

从每个数的各位开始排序，然后依次比较十位、百位。。。

实际过程是在每一位进行排序都调用的是计数排序 (每位上的数都是0-9的数字，所以用计数排序)

2、代码

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
package Sort;

import java.util.Scanner;

/**
 * 基数排序 给每一位都进行一次计数排序
 * 
 * Author: Wayne 13186259527@163.com
 *
 */
public class RadixSort {
	public static int d;

    /**
	 * count[]:辅助数组(类似于计数排序里的c[])
	 * temp[]:每一位拍好序的数组，临时放到temp
	 * 
	 * @param arr
	 */
	private static void radixSort(int arr[]) {
		int k = 10;
		int i, j;
		int p;
		int count[] = new int[k];
		int temp[] = new int[arr.length];
		//d:数字的最大位数
		for (i = 1; i <= d; i++) {
			// 每一层其实都是一个计数排序
			for (j = 0; j < k; j++) {
				count[j] = 0;
			}
			for (j = 0; j < arr.length; j++) {
				count[getdigit(arr[j], i)]++;
			}
			/**
			 * 此循环结束，count上的元素count[k]表示：当前第i位，小于等于k的个数。 
			 * eg:i =3，count[3]表示，第三位（百位）上的数，小于等于3的有count[3]个。
			 */
			for (j = 1; j < count.length; j++) {
				count[j] = count[j] + count[j - 1];
			}
			/**
			 * arr[p]:该元素值 
			 * getdigit(arr[p],i)：该元素第i位是几 
			 * count[t]：小于等于该元素的元素个数
			 */
			for (p = arr.length - 1; p >= 0; p--) {
				int t = getdigit(arr[p], i);
				temp[count[t] - 1] = arr[p];// 把该元素放到小于它的最右边，减一是因为下标从0开始
				count[t]--;// 放一个元素，减一
			}
			for (p = 0; p < temp.length; p++) {
				arr[p] = temp[p];
			}
		}
	}
	/**
	 * 得到i的第d位上的数
	 * 
	 * @param i
	 * @param a取值为1到d位
	 *            （从个位向前数）
	 * @return
	 */
	private static int getdigit(int arg, int a) {
		int r = 0;
		for (int j = 1; j <= a; j++) {
			r = arg % 10;
			arg = arg / 10;
		}
		return r;
	}
	public static void main(String[] args) {
		System.out.println("please input a order number and order");
		System.out.println("eg: 5 =====个数\n 回车\n 3======最高的位数（最高的数百位输入3）\n"
				+ "  5 84 22 434 98(以空格隔开)");
		/**
		 * 输入序列个数
		 */
		Scanner s = new Scanner(System.in);

		int n = s.nextInt();
		System.out.println("n=" + n);

		/**
		 * 输入序列最高的位数
		 */
		Scanner s2 = new Scanner(System.in);
		d = s2.nextInt();
		System.out.println("d=" + d);
		/**
		 * 输入序列
		 */
		Scanner s1 = new Scanner(System.in);
		String line = s1.nextLine();
		String[] split = line.split("\\s");
		int arr[] = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(split[i]);
			System.out.println(arr[i] + "地址： " + i);
		}
		// 排序
		radixSort(arr);

		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
	
}

九、桶排序

1、前提

输入数据均匀分布在[0,1)上

2、思想

因为对数据有要求，所以可以把数据分别放入不同的链表(桶)中。在桶内排好序，再依次按桶输出即可

3、实现

  • 有一链表数组(桶)，大小为10(有10个小桶)。
  • 给每个元素乘10，以元素的个位数字为准放入对应序号的小桶内。
  • 每个小桶内采用排序。
  • 按照小桶的序号，依次输出里面的元素。

4、代码

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
package Sort;

import java.util.Random;
import java.util.Scanner;

import javax.swing.plaf.metal.MetalIconFactory.FolderIcon16;

/**
 * 桶排序 假设：输入数据服从均匀分布，均匀、独立的分布在[0,1)上。
 * 
 * Author: Wayne 13186259527@163.com
 *
 */

public class BucketSort {
	public static Random r = new Random();

	public static class Node {
		float value;
		Node next;

		public Node(float arr) {
			this.value = arr;
			this.next = null;
		}

		public Node() {
			this.value = 0;
			this.next = null;
		}

		void setNext(Node next) {
			this.next = next;
		}

		Node getEnd() {
			Node p = null;
			for (p = this; p.next != null; p = p.next) {
			}
			return p;
		}

	}

	public static void main(String[] args) {
		System.out.println("请输入序列个数n");
		/**
		 * 输入序列个数n
		 */
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		System.out.println("n=" + n);
		/**
		 * 链表
		 */
		Node list[] = new Node[10];
		Node point = null;

		float arr[] = new float[n];
		for (int i = 0; i < arr.length; i++) {
			/**
			 * 产生只有2位小数的[0,1)的随机数 Math.floor():向下取整函数
			 */
			arr[i] = (float) (Math.floor(Math.random() * 100) / 100);
		}

		// 排序
		Bucketsort(arr, list);
		/**
		 * 输出源数据
		 */
		for (int i = 0; i < arr.length; i++) {
			System.out.println("arr[" + i + "] = " + arr[i]);
		}
		System.out.println("===========================");

		for (int i = 0; i < 10; i++) {
			point = list[i];
			// 打印每个链表中的所有数据
			while (point != null) {
				System.out.println("list[" + i + "].value: " + point.value);
				point = point.next;
			}
			System.out.println("----");
		}
	}

	/**
	 * @param arr 存放输入数据的数组
	 * @param list 链表数组(桶)
	 */
	private static void Bucketsort(float[] arr, Node[] list) {
		int t;
		Node point;
		/**
		 * 将数据都挂在一个数组链表中。
		 */
		for (int i = 0; i < arr.length; i++) {
			/**
			 * 例如arr[i] = 0.58 t = 5 5这个节点就被挂到list[5]后面
			 */
			t = (int) Math.floor(arr[i] * 10);
			point = new Node(arr[i]);
			if (list[t] == null) {
				list[t] = point;
			} else {
				// 挂链
				list[t].getEnd().setNext(point);
			}
		}
		for (int i = 0; i < 10; i++) {
			point = list[i];
			/**
			 * 桶内排序 把每一个链表里面的数据都排为升序
			 */
			point = InBuckSort(point);
		}
	}
	/**
	 * @param point链表表头
	 * @ p 工作指针 
	 * @ q 遍历链表，找当前最小的节点 
	 * @ M 指向当前已排序的最后一个节点
	 */
	private static Node InBuckSort(Node point) {

		if (point != null) {

			Node p = null, q = null, Min = null, M = null;
			float tmp;
			M = point;
			for (p = point; p.next != null; p = p.next) {
				Min = p;
				for (q = p.next; q != null; q = q.next) {
					if (q.value < Min.value) {
						Min = q;
					}
				}
				tmp = Min.value;
				Min.value = M.value;
				M.value = tmp;
				// 让M节点向后移动，来放下一个最小的元素
				M = M.next;
			}
		}
		return point;
	}
}