上QQ阅读APP看书，第一时间看更新
1.4.2 排序
如何得到一个排好序的词表？首先看一下如何对整数数组排序，然后再看一下如何对字符串数组排序。
排序可以看成是减少逆序的过程。通过交换值来消除逆序。检查任意两个位置的元素，如果是逆序，就交换这两个位置中的值。
int[] scores = { 1, 6, 3, 8, 5 }; // 待排序的数组
// 比较任意两个数，将小数放在前面，大数放在后面
for (int i = 0; i < scores.length; i++) {
for (int j = 0; j < scores.length; j++) {
//如果是逆序，就交换这两个数
if (i<j && scores[i] > scores[j]) { //同时满足两个条件
int temp = scores[j];
scores[j] = scores[i];
scores[i] = temp;
}
}
}
这种随意消除逆序的方法并不能保证最后得到一个完全有序的数组。对于已经排好序的数组来说，最大的元素位于数组尾部。对于子数组来说，也是如此。也就是说，第二大的元素位于数组倒数第二的位置，第三大的元素位于数组倒数第三的位置，依次类推。冒泡排序正是基于这样的事实。
设想有一瓶汽水，溶解在水中的气体不断上浮，最后实现水气分离。每次让最重的一个元素沉到底。以后就不用再管它了。通过让轻的气泡不断上浮，从而达到有序。
将一个最重的元素沉底，顺便减少逆序。
int[] scores = { 1, 6, 3, 8, 5 }; //待排序的数组
for (int j = 0; j < scores.length -1 ; j++) {
//循环不变式是：scores[j]存储了数组从开始一直到j为止的最大的一个数
//比较相邻的两个数，将小数放在前面，大数放在后面
if (scores[j] > scores[j + 1]) {
int temp = scores[j];
scores[j] = scores[j + 1];
scores[j + 1] = temp;
}
}
完整的冒泡排序。
int[] scores = { 1, 6, 3, 8, 5 }; //待排序的数组
for (int i = 0; i < scores.length -1; i++) { //每次搞定一个最大的元素
// 最底下已经排好序，所以逐渐减少循环次数
for (int j = 0; j < scores.length -1- i; j++) {
//比较相邻的两个数，将小数放在前面，大数放在后面
if (scores[j] > scores[j + 1]) {
int temp = scores[j];
scores[j] = scores[j + 1];
scores[j + 1] = temp;
}
}
}
System.out.println("排序后的结果：");
for (int i = 0; i < scores.length; i++) {
System.out.println(scores[i]);
}
两层循环，内层循环执行一遍后，让1个数沉底。如果数组中有n 个元素，则外层循环执行n -1遍。也就是说通过n -1次循环让n -1个元素沉底。
想象在和很多人喝酒，要把这些人都招待好。i用来表示找每个人喝，j表示这个人每次要喝很多杯才能喝好。
首先看一下如何比较两个字符串的大小，然后再看一下如何对字符串数组排序。比较两个对象用compareTo()方法。字符串也是对象，所以也可以用compareTo()方法比较两个字符串的大小。
String a = "北京";
String b = "广州";
System.out.print(a.compareTo(b)); //因为a小于b，所以返回负数
对字符串数组排序。
String[] words = {"北京", "广州", "上海"};
for (int i = 0; i < words.length -1; i++) {
// 最底下已经排好序，所以逐渐减少循环次数
for (int j = 0; j < words.length -1- i; j++) {
if (words[j].compareTo(words[j + 1])>0) {
String temp = words[j];
words[j] = words[j + 1];
words[j + 1] = temp;
}
}
}
如果数组中的元素很多，则快速排序更快。所要搜索的词往往很多，所以应该使用快速排序。