一遍单向扫描法和双向扫描法_操作系统双向扫描算法规则

	2020.2.20
	  17:00
1
2

在java中调用sort()方法的时候，会自动地排序好数组元素，而sort()中使用的排序是快速排序。
快速排序有两种实现的方式
①：单向扫描法
②：双向扫描法

单向扫描法

思路&过程

 思路：用两个指针将数组分成成三部分，左边的扫描指针，右边在数组末尾再定义一个指针，
 主元默认定义为数组的第一个元素，如果扫描指针指到的元素小于主元，那么元素的位置不
 动，将扫描指针继续往右边移动，如果扫到了比主元大的元素，先将此元素和右边指针指到的
 元素进行交换，再将右边的元素指针往左边移动，最终在循环结束后，右边的指针一定指向的
 是最后一个小于等于主元的元素，所以，将完成循环后的最右边的主元进行交换，再返回它，
 就得到了主元。
1
2
3
4
5
6

代码：

package LanQiaoKnowledge;

import java.util.Arrays;

public class 一遍单向扫描法快速排序 {
		//一次单向扫描法
		static void quick_sort(int arr[],int p,int r) {  //p为开始，r为末尾
					if(p<r) {
				int center=partion(arr,p,r);
				quick_sort(arr,p,center-1);
				quick_sort(arr,center+1,r);
			}
		}
		public static int partion(int arr[],int p,int r) {
		
			//头指针
			int sp=p;
			//尾指针
			int bigger=r;
			//设置头元素为主元
			int pivot=arr[p];
			while(sp<=bigger) {
				if(arr[sp]<=pivot) {		//当数组的元素小于主元的时候，sp指针往下移动，元素不动
					sp++;						//sp指针向右移动
				}else {
				swap(arr,sp,bigger);			
					//遇到数组中的元素比主元大的情况时，sp指针停止，将当前元素和末尾bigger指针指向的元素交换位置，并且bigger指针缩小，再去进行比较
					bigger--;
				}
			}
			swap(arr,p,bigger);
			return bigger;
		}
		public	static void swap(int[]arr,int a,int b) {
			
			int temp = arr[a];
			arr[a]=arr[b];
			arr[b]=temp;
								}
		
	public static void main(String[] args) {
				int []arr= {5,2,7,4,6,9,12,21};
				Arrays.sort(arr);
				System.out.println("工具类当中的快速排序：");
				for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i]+" ");
					}
				System.out.println();
				System.out.println("自己写的快速排序：");
				quick_sort(arr,0,arr.length-1);
				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
50
51
52
53
54
55
56
57
58

双向扫描法

思路&过程

过程：在数组的开始定义一个主元，位置为p，左边定义一个扫描指针，位置为p+1，右边定义
一个指针，位置为r。				左边的指针往右边扫描，遇到比主元小的元素继续往右边扫描，
遇到比主元大的元素停止，右边的指针，从数组的末尾开始往左边扫描，扫到比主元大的元素
继续往左走，遇到小的停止。两个数调换位置   最终在最后一次交换的时候，左边的指针一定是
指向第一个大于主元的数，右边的指针指向的一定是最后一个小于等于主元的数。   所以，在最
外层的循环结束的时候，交换一下主元和右边指针指向的位置，并且，返回右边的指针，这就
是定下来的主元。
1
2
3
4
5
6
7

代码：

package LanQiaoKnowledge;

public class 双向扫描法快速排序 {
				//快速排序算法
		static void quicksort(int []arr,int p,int r) {
				if(p>=r) {
					return;
				}
				int pivot=partition(arr,p,r);
				quicksort(arr,p,pivot-1);
				quicksort(arr,pivot+1,r);
		} 
		//双向扫描法确定pivot
		public static int partition(int []arr,int p,int r) {
			int pivot=arr[p];
			int left=p+1;						//左边指针
			int right=r;						//右边指针
			while(left<right) {						//最外层循环的条件
				while(arr[pivot]>arr[left]&&left<right) {	//扫到比主元小的元素继续往右移动
					left++;
				}
				while(arr[right]>arr[pivot]&&left<right) {			//扫到比主元大的继续往左边扫
					right--;
				}
				if(left<right) {
					swap(arr,left,right);				//交换最终的两个左边和右边的数
					
				}
					}
			swap(arr,p,right);							//最终的右边的指针指向的是最后一个小于等于主元的数
			return arr[right];							//返回主元
		}
				//交换函数
		public static void swap(int []arr,int left,int right) {
			int temp=arr[left];
			arr[left]=arr[right];
			arr[right]=temp;
			
		}
				public static void main(String[] args) {
					int arr[]= {5,2,1,5,8,7,9,6,53};
					quicksort(arr,0,arr.length-1);
					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

（这个双向扫描法在实现的时候好像出了点问题，思路就是这个思路，不知道代码哪里错了）
1