Luckylau's Blog

阅读大话数据结构（8）

发表于 | 分类于 |

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解排序，代码均为自己实现。

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
直接插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定

排序的基本概念

​ 假设含有n个记录的序列为{r1,r2,……,rn}，其相应的关键字分别为{k1,k2,……,kn}，需确定1，2，……，n的一种排列p1,p2,……,pn，使其相应的关键字满足kp1≤kp2≤……≤kpn（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,……,rpn}，这样的操作就称为排序。假设ki=kj（1≤i≤n,1≤j≤n,i≠j），且在排序前的序列中ri领先于rj（即i<j）。如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。

​ 内排序与外排序：根据在排序过程中待排序的记录是否全部被放置在内存中。内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

对于内排序来说，排序算法的性能主要是受三个方面影响：时间性能；辅助空间；算法的复杂性。

排序的结构图如下：

交换排序

冒泡排序

实现一：

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
public class BubbleSort {
	
	public void bubbleSort(int[]nums){
		if(nums.length == 0){
			return;
		}
		for(int i = 1 ;i < nums.length; i++){
			for(int j = nums.length - 1 ; j >= i ; j--){
				if(nums[j] < nums[j - 1]){
					int tmp = nums[j];
					nums[j] = nums[j-1];
					nums[j-1]=tmp;
				}
			}
		}
	}
	public static void main(String[] args) {
		int[] nums = {1,2,7,4,9,8,5};
		System.out.println(Arrays.toString(nums));
		BubbleSort bubbleSort = new BubbleSort();
		bubbleSort.bubbleSort(nums);
		System.out.println(Arrays.toString(nums));
		
	}
}

实现二：

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
public class BubbleSort {
	
	public void bubbleSort(int[]nums){
		if(nums.length == 0){
			return;
		}
		boolean flag = true;
		for(int i = 1 ;i < nums.length && flag; i++){
			flag =false;
			for(int j = nums.length - 1 ; j >= i ; j--){
				if(nums[j] < nums[j - 1]){
					int tmp = nums[j];
					nums[j] = nums[j-1];
					nums[j-1]=tmp;
					flag = true;
				}
			}
		}
	}
	public static void main(String[] args) {
		int[] nums = {2,1,3,4,5,6,7,8,9};
		System.out.println(Arrays.toString(nums));
		BubbleSort bubbleSort = new BubbleSort();
		bubbleSort.bubbleSort(nums);
		System.out.println(Arrays.toString(nums));		
	}
}

快速排序

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
public class QuickSort {
	public void quickSort(int[] nums){
		if(nums.length == 0){
			return;
		}
		int low = 0;
		int high = nums.length - 1;
		helper(nums,low,high);
	}
	private void helper(int[]nums, int low ,int high){
		if(low < high){
			int pivot = Partition(nums ,low,high);
			helper(nums,0,pivot - 1);
			helper(nums,pivot + 1,high);
			
		}
	}
	private int Partition(int[] nums, int low ,int high){
		int tmp =nums[low];
		while(low < high){
			while(low < high && nums[high] >= tmp){
				high--;
			}
			nums[low] =nums[high];
			while(low < high && nums[low] <= tmp){
				low++;
			}
			nums[high]=nums[low];
		}
		nums[low] = tmp;
		return low;	
	}
	public static void main(String[] args) {
		int[] nums = {2,1,3,4,5,6,7,8,9};
		System.out.println(Arrays.toString(nums));
		QuickSort quickSort = new QuickSort();
		quickSort.quickSort(nums);
		System.out.println(Arrays.toString(nums));	
		}
}

插入排序

直接插入排序

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
public class InsertionSort {
	public void insertionSort(int[] nums) {
		if (nums.length == 0) {
			return;
		}
		int len = nums.length;
		for (int i = 1; i < len; i++) {
			for (int j = i; j > 0; j--) {
				if (nums[j] < nums[j - 1]) {
					int tmp = nums[j];
					nums[j] = nums[j - 1];
					nums[j - 1] = tmp;
				}
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 2, 1, 3, 4, 9, 6, 7, 8, 5 };
		System.out.println(Arrays.toString(nums));
		InsertionSort insertionSort = new InsertionSort();
		insertionSort.insertionSort(nums);
		System.out.println(Arrays.toString(nums));
	}
}

希尔排序

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
public class ShellSort {
	public void shellSort(int[] nums) {
		if (nums.length == 0) {
			return;
		}
		int len = nums.length;
		int increment = len / 2;
		while (increment >= 1) {
			for (int i = 0; i < len; i++) {
				for (int j = i; j < len - increment; j += increment) {
					if (nums[j] > nums[j + increment]) {
						int tmp = nums[j];
						nums[j] = nums[j + increment];
						nums[j + increment] = tmp;
					}
				}
			}
			increment = increment / 2;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 2, 1, 3, 4, 9, 6, 7, 8, 5 };
		System.out.println(Arrays.toString(nums));
		ShellSort shellSort = new ShellSort();
		shellSort.shellSort(nums);
		System.out.println(Arrays.toString(nums));
	}
}

选择排序

简单选择排序

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
public class SelectSort {
	public void selectSort(int[] nums) {
		if(nums.length == 0){
			return;
		}
		int len = nums.length;
		int min;
		for(int i = 0 ; i < len; i++){
			min = i;
			for(int j = min + 1; j < len ; j++){
				if(nums[j] < nums[min]){
					min = j;
				}
			}
			if( min != i){
				int tmp = nums[min];
				nums[min] = nums[i];
				nums[i] = tmp;
			}	
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 2, 1, 3, 4, 9, 6, 7, 8, 5 };
		System.out.println(Arrays.toString(nums));
		SelectSort selectSort = new SelectSort();
		selectSort.selectSort(nums);
		System.out.println(Arrays.toString(nums));
	}
}

堆排序

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
public class HeapSort {
	public void heapSort(int[] nums) {
		if (nums.length == 0) {
			return;
		}
		int len = nums.length;
		for (int i = len / 2; i >= 0; i--) {
			HeapAdjust(nums, i, len);
		}
		for (int i = len - 1; i >= 1; i--) {
			int tmp = nums[0];
			nums[0] = nums[i];
			nums[i] = tmp;
			HeapAdjust(nums, 0, i - 1);
		}
	}
	private void HeapAdjust(int[] nums, int index, int length) {
		int tmp = nums[index];
		for (int i = 2 * index + 1; i < length - 1; i = 2 * i + 1) {
			if (nums[i] < nums[i + 1]) {
				i++;
			}
			if (tmp >= nums[i]) {
				break;
			}
			nums[index] = nums[i];
			index = i;
		}
		nums[index] = tmp;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 2, 1, 3, 4, 9, 6, 7, 8, 5 };
		System.out.println(Arrays.toString(nums));
		HeapSort HeapSort = new HeapSort();
		HeapSort.heapSort(nums);
		System.out.println(Arrays.toString(nums));
	}
}

归并排序

递归实现：

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
public class MergeSort {
	public void mergeSort(int[] nums) {
		if (nums.length == 0) {
			return;
		}
		int len = nums.length;
		helper(nums, 0, len - 1);
	}
	private void helper(int[] nums, int left, int right) {
		if (left < right) {
			int mid = left + (right - left) / 2;
			helper(nums, left, mid);
			helper(nums, mid + 1, right);
			merge(nums, left, mid, right);
		}
	}
	private void merge(int[] nums, int left,int mid, int right) {
		int i = left;
		int j = mid + 1;
		int count = 0;
		int[] tmp = new int[right - left + 1];
		while (i <= mid && j <= right) {
			if (nums[i] < nums[j]) {
				tmp[count++] = nums[i++];
			} else {
				tmp[count++] = nums[j++];
			}
		}
		while (i <= mid) {
			tmp[count++] = nums[i++];
		}
		while (j <= right) {
			tmp[count++] = nums[j++];
		}
		count = 0;
		while (left <= right) {
			nums[left++] = tmp[count++];
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 2, 1, 3, 4, 9, 6, 7, 8, 5 };
		System.out.println(Arrays.toString(nums));
		MergeSort MergeSort = new MergeSort();
		MergeSort.mergeSort(nums);
		System.out.println(Arrays.toString(nums));
	}
}

非递归实现：

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 MergeSort {
	public void mergeSort(int[] nums) {
		if (nums.length == 0) {
			return;
		}
		int sublen = 1;
		int length = nums.length;
		while (sublen < length) {
			for (int i = 0; i < length; i += 2 * sublen) {
				merge(nums, i, sublen);
			}
			sublen *= 2;
		}
	}
	private void merge(int[] nums, int i, int sublen) {
		int start = i;
		int count = 0;
		int[] tmp = new int[2 * sublen];
		int frontlen = nums.length > (i + sublen) ? (i + sublen) : nums.length;
		int j = i + sublen;
		int rearlen = nums.length > (j + sublen) ? (j + sublen) : nums.length;
		while (i < frontlen && j < rearlen) {
			if (nums[i] < nums[j]) {
				tmp[count++] = nums[i++];
			} else {
				tmp[count++] = nums[j++];
			}
		}
		while (i < frontlen) {
			tmp[count++] = nums[i++];
		}
		while (j < rearlen) {
			tmp[count++] = nums[j++];
		}
		for (int k = 0; k < count; k++) {
			nums[start++] = tmp[k];
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 2, 1, 3, 4, 9, 6, 7, 8, 5, 10, 5, 6 };
		System.out.println(Arrays.toString(nums));
		MergeSort MergeSort = new MergeSort();
		MergeSort.mergeSort(nums);
		System.out.println(Arrays.toString(nums));
}

基数排序

基于两种不同的排序顺序，我们将基数排序分为LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。注意一点：LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。

http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html

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
public class RadixSort {
	
	public void radixSort(int[]nums ,int radix , int digit){
		if(nums.length == 0){
			return;
		}
		int[] tmp = new int[nums.length];
		int[] buckets = new int[radix];
		for( int i = 0 , rate = 1; i <= digit; i++){
			Arrays.fill(buckets, 0);
			System.arraycopy(nums, 0, tmp, 0, nums.length);
			
			for( int j = 0 ; j < nums.length; j++){
				int subKey = (nums[j]/rate)%radix;
				buckets[subKey]++;
			}
			for (int j =1 ; j < radix ; j++){
				buckets[j] = buckets[j] + buckets[j - 1];
			}
			
			for (int k = nums.length - 1; k >=0 ;k--){
				int subKey =(tmp[k]/rate)%radix;
				nums[--buckets[subKey]] = tmp[k];
			}
			rate *=radix;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 200, 1, 3, 42, 9, 64, 7, 81, 5, 10, 52, 61 };
		System.out.println(Arrays.toString(nums));
		RadixSort RadixSort = new RadixSort();
		RadixSort.radixSort(nums, 10, 3);
		System.out.println(Arrays.toString(nums));
	}
}
Luckylau wechat
如果对您有价值,看官可以打赏的！