冒泡排序与快速排序——Java语言描述

发表于 | 分类于 | 阅读次数

冒泡排序与快速排序都应用了交换排序基本思想。所谓交换排序就是两两比较待排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。

程序代码

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
import java.util.Arrays;

public class ExchangeSort {

	/**
	 * 冒泡排序：将待排序的数组看作从上到下排列，把关键字值较小的记录看作“较轻的”，关键字值较大的看作“较重的”，
	 *       较小的关键字值看记录好像水中的气泡一样，向上“浮”；较大关键字值的记录就如水中的石头向下沉，当所有
	 *     	   的气泡都浮到了相应的位置，并且所有的石块都沉到了水底，排序就结束了。
	 * 空间复杂度为O(1)
	 * 时间复杂度为O(n^2)
	 * 算法稳定性：冒泡排序是一种稳定的排序算法。
	 * */
	/**
	 * 主要步骤归纳：
	 * 	1.设置初值i=1;
	 * 	2.在无序序列{a[0],a[1],...a[n-1]}中，从头至尾依次比较相邻的两个记录
	 * 	  a[j]与a[j=1]（0<=j<=n-i-1）,若a[j].key>a[j+1].key,则交换位置。
	 * 	3.i=i+1;
	 * 	4.重复步骤2,3，直到在步骤2中未发生记录交换成i=n-1为止。
	 * 
	 * */	
	public static void BubbleSort(int bubble[]) {
		int temp;
		boolean flag=true;  //记录是否发生交换
		int i,j;
		for(i=1;i<bubble.length && flag;i++){ //有交换时再进行下一趟，最多n-1趟
			flag=false;
			for(j=0;j<bubble.length-i;j++){
				if(bubble[j]>bubble[j+1]){   //逆序时，相互交换位置
					temp=bubble[j];
					bubble[j]=bubble[j+1];
					bubble[j+1]=temp;
					flag=true;
				}
			}
			System.out.println("第"+i+"趟："+Arrays.toString(bubble));
		}
	}
	
	/**
	 * 快速排序：通过一趟排序将要排序的记录分隔成独立的两个部分，其中一部分的所有记录的关键字值都比
	 * 	               另一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个记录
	 * 		 过程可以递归进行，以此达到整个记录序列变成有序
	 * 空间复杂度为O(logn)
	 * 时间复杂度:最坏为O(n^2)，平均为O(nlogn)
	 * 算法稳定性：快速排序是一种不稳定的排序算法
	 * */
	/**
	 * 主要步骤：
	 * 	1.设置两个变量i,j，初始值分别为low和high，分别表示待排序序列的起始下标和终止下标；
	 * 	2.将第i个记录暂存在变量temp中，及temp=Q[i];
	 * 	3.从小标为j的位置开始由后向前以此搜索，当找到第一个比temp的关键字小的记录时，则将该
	 * 		记录向前移动到下标为i的位置上，然后i=i+1;
	 * 	4.从下标为i的位置开始由前向后依次搜索，当找到第一个比temp的关键字值大的记录时，则将
	 * 		该记录向后移动到下标为j的位置上，然后j=j-1;
	 * 	5.重复2,3,4步骤，直到i==j;
	 * 	6.Q[i]=temp.
	 * 
	 * */
	
	//一趟快速排序算法
	public static int Quick(int quick[],int i,int j) {
		int temp=quick[i];
		while(i<j){	//从表的两端交替向中间扫描
			while(i<j && temp<=quick[j]){
				j--;
			}
			if(i<j){
				quick[i]=quick[j];	//将比quick[i]的关键字值小的记录向前移动
				i++;
			}
			while(i<j && temp>quick[i]){
				i++;
			}
			if(i<j){
				quick[j]=quick[i];	//将比quick[i]的关键字值大的记录向后移动
				j--;
			}
		}
		quick[i]=temp;
		System.out.println(Arrays.toString(quick));
		return i;
	}
	//递归形式的快速排序算法
	public static void QuickSort(int quick[],int low,int high){
		if(low<high){
			int i=Quick(quick, low, high) ; //一趟排序将序列分为两部分
			QuickSort(quick,low,i-1);	//低子表递归排序
			QuickSort(quick, i+1, high);	//高子表递归排序
		}
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int bubble[]={52,24,76,9,50,64,17,39,47,15};
		int quick[]={52,39,67,95,70,8,25,52,45,19};
		BubbleSort(bubble);
		System.out.println("---------------------分割线--------------------");
		QuickSort(quick, 0, quick.length-1);
	}
}

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
第1趟：[24, 52, 9, 50, 64, 17, 39, 47, 15, 76]
第2趟：[24, 9, 50, 52, 17, 39, 47, 15, 64, 76]
第3趟：[9, 24, 50, 17, 39, 47, 15, 52, 64, 76]
第4趟：[9, 24, 17, 39, 47, 15, 50, 52, 64, 76]
第5趟：[9, 17, 24, 39, 15, 47, 50, 52, 64, 76]
第6趟：[9, 17, 24, 15, 39, 47, 50, 52, 64, 76]
第7趟：[9, 17, 15, 24, 39, 47, 50, 52, 64, 76]
第8趟：[9, 15, 17, 24, 39, 47, 50, 52, 64, 76]
第9趟：[9, 15, 17, 24, 39, 47, 50, 52, 64, 76]
---------------------分割线--------------------
[19, 39, 45, 25, 8, 52, 70, 52, 95, 67]
[8, 19, 45, 25, 39, 52, 70, 52, 95, 67]
[8, 19, 39, 25, 45, 52, 70, 52, 95, 67]
[8, 19, 25, 39, 45, 52, 70, 52, 95, 67]
[8, 19, 25, 39, 45, 52, 67, 52, 70, 95]
[8, 19, 25, 39, 45, 52, 52, 67, 70, 95]