Swapping sort

Posted on | Edited on | Views: 
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
//swapping sort including:
//1. bubble_sort
//2. quick_sort

public class Swapping_sort {
	// ---------------------------------------------bubble sorting
	// Time Complexity: O(n^2)
	// Space Complexity: O(1)
	static void bubbleSort(int[] arr) {
		int len = arr.length;
		for (int i = 1; i < len; i++) { // i: 排序次数
			for (int j = 0; j < len - i; j++) { // j: 比较的位置
				if (arr[j] > arr[j + 1]) { // 相邻元素两两对比
					int temp = arr[j + 1]; // 元素交换
					arr[j + 1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}

	// ---------------------------------------------bubble sorting with optimization
	// Worst Case Time Complexity [ Big-O ]: O(n^2)
	// Best Case Time Complexity [Big-omega]: O(n)
	// Average Time Complexity [Big-theta]: O(n^2)
	// Space Complexity: O(1)
	static void bubbleSort_optimizaion(int[] arr) {
		int n = arr.length;
		for (int i = 1; i < n; i++) {
			boolean swapped = false;
			for (int j = 0; j < n - i; j++) {
				if (arr[j] > arr[j + 1]) {
					// swap arr[j] and arr[j+1]
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					swapped = true;
				}
			}
			// IF no two elements were
			// swapped by inner loop, then break
			if (swapped == false)
				break;
		}
	}

	// ---------------------------------------------quick sorting
	public static void quicksort(int[] nums) {
		sort(nums, 0, nums.length - 1);
	}

	public static void sort(int[] nums, int l, int r) {
		if (l < r) {
			// 一趟快排，并返回交换后基数的下标
			int index = patition(nums, l, r);
			// 递归排序基数左边的数组
			sort(nums, l, index - 1);
			// 递归排序基数右边的数组
			sort(nums, index + 1, r);
		}
	}

	public static int patition(int[] nums, int l, int r) {
		// p为基数，即待排序数组的第一个数
		int p = nums[l];
		int i = l;
		int j = r;
		while (i < j) {
			// 从右往左找第一个小于基数的数
			while (nums[j] >= p && i < j) j--;
			// 从左往右找第一个大于基数的数
			while (nums[i] <= p && i < j) i++;
			// 找到后交换两个数
			if (i < j) {
				int tmp = nums[i];
				nums[i] = nums[j];
				nums[j] = tmp;
			}
		}
		// 使划分好的数分布在基数两侧
		nums[l]=nums[i];
		nums[i]=p;
		
		return i;
	}

	// *********************************************
	// main function
	public static void main(String[] args) {
		int[][] new_array = { { 1, 5, 8, 3, 2 }, { 9, 8, 1, 5, 2 } };
		// for(int i=0;i<2;i++){
		// for (int j=0;j<10;j++) {
		// new_array[i][j]=(int)(Math.random()*9+1);
		// }
		// }
		// bubble sorting test
		System.out.print("the original array is: ");
		for (int i : new_array[0])
			System.out.print(i);

		System.out.println();
		System.out.print("after bubble sorting: ");
		bubbleSort_optimizaion(new_array[0]);
		for (int i : new_array[0])
			System.out.print(i);
		System.out.println();

		// quick sorting test
		System.out.println();
		System.out.print("the original array is: ");
		for (int i : new_array[1])
			System.out.print(i);
		System.out.println();
		System.out.print("after quick sorting: ");
		quicksort(new_array[1]);
		for (int i : new_array[1])
			System.out.print(i);
		System.out.println();
	}
}

QuickSort iteration version

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
class Demo{
	public static void quickSort(int[] arr, int left, int right) {   
		if (left > right)  return;  
		int pivot = arr[left]; // pivot中存的就是基准数  
		int i = left;       // 设置两个哨兵  
		int j = right;  	// 设置两个哨兵
		while (i != j) {  
			// 顺序很重要，要先从右边开始找  
			while (arr[j] >= pivot && i < j)  j--;  
			// 再找左边的  
			while (arr[i] <= pivot && i < j)  i++;  
			// 交换两个数在数组中的位置  
			if (i < j) {  
				int temp = arr[i];  
				arr[i] = arr[j];  
				arr[j] = temp;  
			}  
		}  
		// 最终将基准数归位  
		arr[left] = arr[i];  
		arr[i] = pivot;  
	  
		quickSort(arr, left, i - 1);// 继续处理左边的，这里是一个递归的过程  
		quickSort(arr, i + 1, right);// 继续处理右边的 ，这里是一个递归的过程  
	}  

	//*********************************************
	public static void main(String[] args){
		int[] array = new int[9];
		for (int i=0;i<9;i++) {
			array[i]=(int)(Math.random()*9+1);
			System.out.print(array[i]+" ");
		}
		System.out.println();
		
		quickSort(array,0,8);
		for(int i=0;i<array.length;i++)
			System.out.print(array[i]+" ");
	}
	
}

0%