双指针选择排序算法，附源码及对数器验证，全网唯一，Java实现

130 阅读 0 评论 86 点赞

我是靠谱客的博主斯文枕头，这篇文章主要介绍双指针选择排序算法，附源码及对数器验证，全网唯一，Java实现，现在分享给大家，希望可以做个参考。

我是一个从汽车行业转行IT的项目经理，我是Edward。最近一直在听马士兵马老师的算法课，第一个排序算法的作业就让我陷入了苦思冥想，选择排序固然简单，但是在一次遍历中加入了最大值的识别和换位增大了不少难度，临界情况的判定无疑是关键。为什么写这篇文章？原因是查了不少帖子，发现虽然有不少人是用jJava实现的，但是写的都不对，写出来的程序跑了一遍1-10成立，就以为对了，真是贻害万年！

下面是实现的代码，其中关键判定处标有注释：

复制代码

public class SelectionSortImproved {
	
	public static void sort(int[]arr) {
		for (int j = 0; j < arr.length/2; j++) {
			//一次遍历同时找出最大值和最小值并换位
			int minPos=j,maxPos=arr.length-1-j;
			for (int i = j; i <= arr.length-j-1; i++) {   
				minPos = arr[minPos]>arr[i] ? i:minPos;
				maxPos = arr[maxPos]<arr[i] ? i:maxPos;
			}
//			System.out.println("n"+"minPos:"+minPos+","+"maxPos:"+maxPos);
			if (minPos==arr.length-j-1) {   //排除临界状况
				swap(maxPos, minPos, arr);
				swap(maxPos, j, arr);	    //最大最小已换位，此时应把最大的换到最左
			}else if (maxPos==j) {
				swap(maxPos, minPos, arr);
				swap(minPos, arr.length-j-1, arr);  //最大最小已换位，此时应把最小的换到最右
			}else {
				swap(arr.length-1-j, maxPos, arr);    
				swap(j, minPos, arr);    //这里的第二次swap可能打乱原有排序
				
			}
//			System.out.println("经过第"+j+"次循环后，数组的内容为：");
//			print(arr);
			
		}
		
	}

public static void main(String[] args) {
		int[]arr= {2,8,1,9,4,7,6,3,5};
		sort(arr);

}
	
	static void swap(int x,int y,int[]arr) {
		int temp = arr[x];
		arr[x]=arr[y];
		arr[y]=temp;
	}
	
	static void print(int[]arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}	
	}
}

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
public class SelectionSortImproved {
	
	public static void sort(int[]arr) {
		for (int j = 0; j < arr.length/2; j++) {
			//一次遍历同时找出最大值和最小值并换位
			int minPos=j,maxPos=arr.length-1-j;
			for (int i = j; i <= arr.length-j-1; i++) {   
				minPos = arr[minPos]>arr[i] ? i:minPos;
				maxPos = arr[maxPos]<arr[i] ? i:maxPos;
			}
//			System.out.println("n"+"minPos:"+minPos+","+"maxPos:"+maxPos);
			if (minPos==arr.length-j-1) {   //排除临界状况
				swap(maxPos, minPos, arr);
				swap(maxPos, j, arr);	    //最大最小已换位，此时应把最大的换到最左
			}else if (maxPos==j) {
				swap(maxPos, minPos, arr);
				swap(minPos, arr.length-j-1, arr);  //最大最小已换位，此时应把最小的换到最右
			}else {
				swap(arr.length-1-j, maxPos, arr);    
				swap(j, minPos, arr);    //这里的第二次swap可能打乱原有排序
				
			}
//			System.out.println("经过第"+j+"次循环后，数组的内容为：");
//			print(arr);
			
		}
		
	}

	public static void main(String[] args) {
		int[]arr= {2,8,1,9,4,7,6,3,5};
		sort(arr);

		
	}
	
	static void swap(int x,int y,int[]arr) {
		int temp = arr[x];
		arr[x]=arr[y];
		arr[y]=temp;
	}
	
	static void print(int[]arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}	
	}
}

附上对数器的验证代码：

复制代码

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
public class DataChecker {
	static int [] generateRandomArray() {
		Random r = new Random();
		int[]arr=new int[10000];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=r.nextInt(10000);
		}
		return arr;
		
	}
	
	static void check() {
		int[]arr=generateRandomArray();
		int[]arr2=new int[arr.length];
		System.arraycopy(arr, 0, arr2, 0, arr.length);
		
		Arrays.sort(arr);
		SelectionSortImproved.sort(arr2);
		
		boolean same = true;
		for (int i = 0; i < arr2.length; i++) {
			if (arr[i]!=arr2[i]) {
				same=false;
			}
		}
		System.out.println(same==true?"right":"wrong");
	
		
	}
	
	public static void main(String[] args) {
		check();
	}
}