几种排序算法
下面的例子介绍了4种排序方法: 冒泡排序, 选择排序, 插入排序, 快速排序
package date201709.date20170915;
public class SortUtil {
private static int quickSortTimes = 1;
/**
* 冒泡排序:<br>
* 两层循环，每次循环比较前后两个元素，如果他们的顺序错误就把他们交换过来，一次循环后最终会把最大的数沉到数列的末端<br>
* 下次循环时,上次循环沉到数列的末端的数不用再参与到本次循环中来比较<br>
*/
// 第1次排序结果: 30 59 12 46 15 83 10 59 27 91
// 第2次排序结果: 30 12 46 15 59 10 59 27 83 91
// 第3次排序结果: 12 30 15 46 10 59 27 59 83 91
// 第4次排序结果: 12 15 30 10 46 27 59 59 83 91
// 第5次排序结果: 12 15 10 30 27 46 59 59 83 91
// 第6次排序结果: 12 10 15 27 30 46 59 59 83 91
// 第7次排序结果: 10 12 15 27 30 46 59 59 83 91
// 第8次排序结果: 10 12 15 27 30 46 59 59 83 91
// 第9次排序结果: 10 12 15 27 30 46 59 59 83 91
public static void bubbleSort(int[] nums) {
int temp = 0;
int size = nums.length;
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
printLog(nums, i + 1);
}
}
/**
* 选择排序:<br>
* 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环<br>
*/
// 第1次排序结果: 10 83 59 12 46 15 91 30 59 27
// 第2次排序结果: 10 12 59 83 46 15 91 30 59 27
// 第3次排序结果: 10 12 15 83 46 59 91 30 59 27
// 第4次排序结果: 10 12 15 27 46 59 91 30 59 83
// 第5次排序结果: 10 12 15 27 30 59 91 46 59 83
// 第6次排序结果: 10 12 15 27 30 46 91 59 59 83
// 第7次排序结果: 10 12 15 27 30 46 59 91 59 83
// 第8次排序结果: 10 12 15 27 30 46 59 59 91 83
// 第9次排序结果: 10 12 15 27 30 46 59 59 83 91
public static void selectSort(int[] nums) {
int temp = 0;
int size = nums.length;
for (int i = 0; i < size - 1; i++) {
// 记录每一次循环最小值的位置
int pos = i;
for (int j = i + 1; j < size; j++) {
if (nums[pos] > nums[j]) {
pos = j;
}
}
// 最小的数与第i个位置的数交换
temp = nums[i];
nums[i] = nums[pos];
nums[pos] = temp;
printLog(nums, i + 1);
}
}
/**
* 插入排序<br>
* 每步将一个待排序的记录，按其大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。<br>
*/
// 第1次排序结果: 30 83 59 12 46 15 91 10 59 27
// 第2次排序结果: 30 59 83 12 46 15 91 10 59 27
// 第3次排序结果: 12 30 59 83 46 15 91 10 59 27
// 第4次排序结果: 12 30 46 59 83 15 91 10 59 27
// 第5次排序结果: 12 15 30 46 59 83 91 10 59 27
// 第6次排序结果: 12 15 30 46 59 83 91 10 59 27
// 第7次排序结果: 10 12 15 30 46 59 83 91 59 27
// 第8次排序结果: 10 12 15 30 46 59 59 83 91 27
// 第9次排序结果: 10 12 15 27 30 46 59 59 83 91
private static void insertSort(int[] nums) {
int temp = 0;
int size = nums.length;
// 从第2个元素开始，第1个元素可以认为已经被排序
for (int i = 1; i < size; i++) {
// 取出下一个元素
temp = nums[i];
// 在已经排序的元素序列中从前向后扫描
for (int j = 0; j < i; j++) {
// 假如temp比前面的某个值小，则将这个值及之后的值后移
if (temp < nums[j]) {
for (int k = i; k > j; k--) {
nums[k] = nums[k - 1];
}
nums[j] = temp;
break;
}
}
printLog(nums, i);
}
}
/**
* 快速排序:<br>
* 选取当前数组段的第一个数作为中轴，和最后一个比，如果比它小交换，比它大(或相等)不做任何处理<br>
* 交换了以后再和小的那端比，比它小不交换，比他大交换<br>
* 这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再递归对左边和右边的数组排序<br>
*/
// 第1次排序结果: 27 10 15 12 30 46 91 59 59 83
// 第2次排序结果: 12 10 15 27 -- -- -- -- -- --
// 第3次排序结果: 10 12 15 -- -- -- -- -- -- --
// 第4次排序结果: -- -- -- -- -- 46 91 59 59 83
// 第5次排序结果: -- -- -- -- -- -- 83 59 59 91
// 第6次排序结果: -- -- -- -- -- -- 59 59 83 --
// 第7次排序结果: -- -- -- -- -- -- 59 59 -- --
public static void quickSort(int[] numbers) {
if (numbers.length > 1) {
quickSort(numbers, 0, numbers.length - 1);
}
}
private static void quickSort(int[] nums, int low, int high) {
if (low < high) {
// 选取中轴
int middle = getMiddle(nums, low, high);
printQuickSortLog(nums, low, high);
if (low < middle - 1) {
// 对低字段表进行递归排序
quickSort(nums, low, middle - 1);
}
if (middle + 1 < high) {
// 对高字段表进行递归排序
quickSort(nums, middle + 1, high);
}
}
}
private static int getMiddle(int[] nums, int low, int high) {
// 选取当前数组段的第一个数作为中轴
int temp = nums[low];
while (low < high) {
// 比中轴大(或相等)不做任何处理(high--)，直到找到比中轴小的
while (low < high && nums[high] >= temp) {
high--;
}
// 比中轴小的记录移到低端
nums[low] = nums[high];
// 比中轴小不做任何处理(low++)，直到找到比中轴大(或相等)的
while (low < high && nums[low] < temp) {
low++;
}
// 比中轴大(或相等)的记录移到高端
nums[high] = nums[low];
}
// 中轴记录到尾
nums[low] = temp;
// 返回中轴的位置
return low;
}
private static void printLog(int[] nums, int times) {
System.out.println("第" + times + "次排序结果:\t" + formatNums(nums));
}
private static void printQuickSortLog(int[] nums, int low, int high) {
System.out.println("第" + quickSortTimes++ + "次排序结果:\t" + formatNums(nums, low, high));
}
private static String formatNums(int[] nums) {
return formatNums(nums, 0, nums.length - 1);
}
private static String formatNums(int[] nums, int low, int high) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < low; i++) {
sb.append("-- ");
}
for (int i = low; i <= high; i++) {
sb.append(nums[i]).append(" ");
}
for (int i = high + 1; i < nums.length; i++) {
sb.append("-- ");
}
return sb.toString().trim();
}
public static void main(String[] args) {
// 10, 12, 15, 27, 30, 46, 59, 59, 83, 91
int[] nums = { 30, 83, 59, 12, 46, 15, 91, 10, 59, 27 };
// bubbleSort(nums);
// selectSort(nums);
// insertSort(nums);
// quickSort(nums);
}
}
Java实现排序的几种方式
(1) 需要排序的Bean实现Comparable<T>接口
package date201709.date20170915; import java.io.Serializable;
import java.util.ArrayList;
import java.util.List; public class User implements Serializable, Comparable<User> { private static final long serialVersionUID = 1L; private Integer id; private Integer age; private String name; public User(Integer id, Integer age, String name) {
super();
this.id = id;
this.age = age;
this.name = name;
} public Integer getId() {
return id;
} public Integer getAge() {
return age;
} public String getName() {
return name;
} @Override
public String toString() {
return "User [id=" + id + ", age=" + age + ", name=" + name + "]";
} @SuppressWarnings("serial")
public static List<User> init() {
return new ArrayList<User>() {
{
add(new User(5, 31, "Zhang San"));
add(new User(2, 28, "Li Si"));
add(new User(3, 26, "Wang Wu"));
add(new User(1, 23, "Zhao Liu"));
add(new User(4, 26, "Liu Qi"));
}
};
} // 比较ID从而对User排序
@Override
public int compareTo(User o) {
return this.getId().compareTo(o.getId());
}
}
package date201709.date20170915; import java.util.Collections;
import java.util.List; public class UserTest { public static void main(String[] args) {
// (1) Id升序
List<User> userList = User.init();
Collections.sort(userList);
printList(userList); // (2) Id降序
Collections.reverse(userList);
printList(userList);
} private static void printList(List<User> param) {
param.forEach(p -> {
System.out.println(p.toString());
});
}
}
(2) 使用内部类实现Comparator<T>接口
package date201709.date20170915; import java.util.Collections;
import java.util.Comparator;
import java.util.List; public class UserTest { public static void main(String[] args) {
// (1) Age升序
List<User> userList = User.init();
Collections.sort(userList, new AgeComparator());
printList(userList); // (2) Age降序
Collections.reverse(userList);
printList(userList);
} private static void printList(List<User> param) {
param.forEach(p -> {
System.out.println(p.toString());
});
} static class AgeComparator implements Comparator<User> {
@Override
public int compare(User o1, User o2) {
return o1.getAge().compareTo(o2.getAge());
}
}
}
(3) 使用匿名内部类实现Comparator<T>接口
package date201709.date20170915; import java.util.Collections;
import java.util.Comparator;
import java.util.List; public class UserTest { public static void main(String[] args) {
// (1) Age升序
List<User> userList = User.init();
Collections.sort(userList, new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
return o1.getAge().compareTo(o2.getAge());
}
});
printList(userList); // (2) Age降序
Collections.reverse(userList);
printList(userList);
} private static void printList(List<User> param) {
param.forEach(p -> {
System.out.println(p.toString());
});
}
}
(4) 使用lambda表达式
package date201709.date20170915; import java.util.Collections;
import java.util.List; public class UserTest { public static void main(String[] args) {
// (1) Age升序
List<User> userList = User.init();
Collections.sort(userList, (a, b) -> (a.getAge().compareTo(b.getAge())));
printList(userList); // (2) Age降序
Collections.reverse(userList);
printList(userList);
} private static void printList(List<User> param) {
param.forEach(p -> {
System.out.println(p.toString());
});
}
}
(5) 使用stream及::表达式
package date201709.date20170915; import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors; public class UserTest { public static void main(String[] args) {
// (1) Age升序
List<User> userList = User.init();
List<User> result1 = userList.stream().sorted((a, b) -> a.getAge().compareTo(b.getAge()))
.collect(Collectors.toList());
printList(result1); // (2) Age降序
List<User> result2 = userList.stream().sorted(Comparator.comparing(User::getAge).reversed())
.collect(Collectors.toList());
printList(result2);
} private static void printList(List<User> param) {
param.forEach(p -> {
System.out.println(p.toString());
});
}
}