1 package com.jdk7.chapter2.sort;
2 /**
3 * 排序功能接口
4 * @author Administrator
5 *
6 */
7 public interface SortNumber {
8 public int[] sortASCNumber(
int[] intArray);
9 }
1 package com.jdk7.chapter2.sort;
2
3 /**
4 * 按升序选择排序数字
5 * @author Administrator
6 *
7 */
8 public class SelectSort
implements SortNumber {
9
10 @Override
11 public int[] sortASCNumber(
int[] intArray) {
12 if(intArray==
null){
13 return null;
14 }
else{
15 int[] array =
intArray.clone();
16 for(
int i=0;i<array.length;i++
){
17 for(
int j=i;j<array.length;j++
){
18 if(array[i]>
array[j]){
19 swithNumber(array,i,j);
20 }
21 }
22 }
23 return array;
24 }
25 }
26
27 public void swithNumber(
int[] array,
int a,
int b){
28 int temp;
29 temp =
array[a];
30 array[a] =
array[b];
31 array[b] =
temp;
32 }
33 }
1 package com.jdk7.chapter2.sort;
2 /**
3 * 按升序冒泡排序数字
4 * @author Administrator
5 *
6 */
7 public class BubbleSort
implements SortNumber {
8
9 @Override
10 public int[] sortASCNumber(
int[] intArray) {
11 if(intArray==
null){
12 return null;
13 }
else{
14 int[] array =
intArray.clone();
15 int maxChangeTimes = array.length-1
;
16 int changeTime = 0
;
17 boolean changeTag =
true;
18 //如果上一轮的最后一对两两对比没有进行交换则停止循环，每一轮循环找到最大数排在数组最后面
19 while((changeTime<maxChangeTimes) &&
changeTag){
20 System.out.println("while"
);
21 for(
int i=0;i<(maxChangeTimes-changeTime);i++
){
22 System.out.println(array[i]+" "+array[i+1
]);
23 changeTag =
false;
24 if(array[i]>array[i+1
]){
25 switchNumber(array,i,i+1
);
26 changeTag =
true;
27 }
28 }
29 changeTime++
;
30 System.out.println("changeTime: "+
changeTime);
31 System.out.println("changeTag: "+
changeTag);
32 }
33 return array;
34 }
35 }
36 public void switchNumber(
int[] array,
int a,
int b){
37 int temp;
38 temp =
array[a];
39 array[a] =
array[b];
40 array[b] =
temp;
41 }
42 }
1 package com.jdk7.chapter2.sort;
2 /**
3 * 线性插入排序
4 * @author Administrator
5 *
6 */
7 public class LinearInsertSort
implements SortNumber {
8
9 @Override
10 public int[] sortASCNumber(
int[] intArray) {
11 if(intArray==
null){
12 return null;
13 }
else{
14 int[] array =
intArray.clone();
15 int index = 0
;
16 int size =
array.length;
17 int temp = 0
;
18 for(
int i=1;i<size;i++
){
19 temp =
array[i];
20 index =
i;
21
22 System.out.println("(temp<array[index-1]) = "+(temp<array[index-1
]));
23 System.out.println("(index>0) = "+((index>0
)));
24 //每次循环中的数组都会按照升序排列,while中的短路与条件必须先要有index>0，然后再有右面的条件，否则数组的索引值会小于0
25 while((index>0) && (temp<array[index-1
])){
26 System.out.println(array[index-1]+" "+
temp);
27 array[index] = array[index-1
];
28 index--
;
29 }
30 System.out.println("array[index]: "+
array[index]);
31 array[index] = temp;
//放在while里面和while外面是一样的效果，在每次while执行时一起执行
32 SortTest.printIntArray(array);
33 }
34 return array;
35 }
36 }
37 }
1 package com.jdk7.chapter2.sort;
2 /**
3 * 快速排序
4 * @author Administrator
5 *
6 */
7 public class QuickSort
implements SortNumber {
8
9 @Override
10 public int[] sortASCNumber(
int[] intArray) {
11 if(intArray==
null){
12 return null;
13 }
else{
14 int[] array =
intArray.clone();
15 return quickSort(array, 0, array.length-1
);
16 }
17 }
18
19 public int[] quickSort(
int[] array,
int first,
int last){
20 if(first<
last){
21 int pos =
partition(array, first, last);
22 System.out.println("pos = "+
pos);
23 //所有左分治执行完成以后，再执行右分治
24 quickSort(array, first, pos-1
);
25 quickSort(array, pos+1
, last);
26 }
27 return array;
28 }
29
30 public int partition(
int[] array,
int first,
int last){
31 System.out.println("调用partition方法"
);
32 int temp =
array[first];
33 int pos =
first;
34 for(
int i=first+1;i<=last;i++
){
35 if(array[i]<
temp){
36 pos++
;
37 //连续比第一位小都不需要换位，遇到比第一位大的数跳过进行下一次循环，在后面的循环中遇到比第一位小的值则将该值与大值进行换位，直到最大值在最末位
38 swap(array, pos, i);
39 SortTest.printIntArray(array);
40 }
41 }
42 //将数组中第二大数值放置在倒数第二位
43 swap(array, first, pos);
44 System.out.println("将分治点和第一个值进行交换"
);
45 SortTest.printIntArray(array);
46 return pos;
47 }
48
49 public void swap(
int[] array,
int src,
int dest){
50 int temp =
array[src];
51 array[src] =
array[dest];
52 array[dest] =
temp;
53 }
54
55 }
转载于:https://www.cnblogs.com/celine/p/8290254.html
相关资源：数据结构—成绩单生成器
