collections.sort()
java的排序可以用collections.sort() 排序函数实现。
用collections.sort方法对list排序有两种方法：
第一种是list中的对象实现comparable接口，如下：
我要评论
/**
* 根据order对user排序
*/
public class user implements comparable<user>{
private string name;
private integer order;
public string getname() {
return name;
}
public void setname(string name) {
this.name = name;
}
public integer getorder() {
return order;
}
public void setorder(integer order) {
this.order = order;
}
public int compareto(user arg0) {
return this.getorder().compareto(arg0.getorder());
}
}
测试一下：
public class test{
public static void main(string[] args) {
user user1 = new user();
user1.setname("a");
user1.setorder(1);
user user2 = new user();
user2.setname("b");
user2.setorder(2);
list<user> list = new arraylist<user>();
//此处add user2再add user1
list.add(user2);
list.add(user1);
collections.sort(list);
for(user u : list){
system.out.println(u.getname());
}
}
}
输出结果如下
a b
第二种方法是根据collections.sort重载方法来实现，例如：
/**
* 根据order对user排序
*/
public class user { //此处无需实现comparable接口
private string name;
private integer order;
public string getname() {
return name;
}
public void setname(string name) {
this.name = name;
}
public integer getorder() {
return order;
}
public void setorder(integer order) {
this.order = order;
}
}
主类中这样写即可：
public class test{
public static void main(string[] args) {
user user1 = new user();
user1.setname("a");
user1.setorder(1);
user user2 = new user();
user2.setname("b");
user2.setorder(2);
list<user> list = new arraylist<user>();
list.add(user2);
list.add(user1);
collections.sort(list,new comparator<user>(){
public int compare(user arg0, user arg1) {
return arg0.getorder().compareto(arg1.getorder());
}
});
for(user u : list){
system.out.println(u.getname());
}
}
}
输出结果如下
a b
前者代码结构简单，但是只能根据固定的属性排序，后者灵活，可以临时指定排序项，但是代码不够简洁
择优用之。
常用排序算法
下面来看几种经典排序算法的java代码实践：
冒泡排序
public static void bubblesort(int a[], int n) {
int i, j;
for (i = 0; i < n - 1; i ++) {
for (j = 0; j < n - i - 1; j ++) {
if (a[j] > a[j + 1]) {
a[j] = a[j] ^ a[j + 1];
a[j + 1] = a[j] ^ a[j + 1];
a[j] = a[j] ^ a[j + 1];
}
}
}
}
直接插入排序
public static void insertsort(int a[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = a[i];
for (j = i - 1; j >= 0; j--) {
if (a[j] > tmp) {
a[j + 1] = a[j];
} else {
break;
}
}
a[j + 1] = tmp;
}
}
直接选择排序
public static void selectsort(int a[], int n) {
int i, j, loc;
for (i = 0; i < n; i++) {
loc = i;
for (j = i + 1; j < n; j++) {
if (a[j] < a[loc]) {
loc = j;
}
}
if (loc != i) {
a[i] = a[i] ^ a[loc];
a[loc] = a[i] ^ a[loc];
a[i] = a[i] ^ a[loc];
}
}
}
堆排序
/**
* 堆排序（从小到大）
*
* @param a
* @param n
*/
public static void heapsort(int a[], int n) {
int tmp;
// 构建大根堆
buildmaxheap(a, n);
for (int j = n - 1; j >= 1; j--) {
tmp = a[0];
a[0] = a[j];
a[j] = tmp;
maxheapify(a, 0, j);
}
}
/**
* 构建大根堆
*
* @param a
* @param n
*/
private static void buildmaxheap(int a[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapify(a, i, n);
}
}
/**
* 维护从下标i开始的最大堆
*
* @param a
* @param i
* @param n
*/
private static void maxheapify(int a[], int i, int n) {
int left, right, loc;
while (i < n) {
left = 2 * i + 1;
right = 2 * i + 2;
loc = i;
if (left < n && a[left] > a[i]) {
i = left;
}
if (right < n && a[right] > a[i]) {
i = right;
}
if (loc != i) {
a[i] = a[loc] ^ a[i];
a[loc] = a[loc] ^ a[i];
a[i] = a[loc] ^ a[i];
} else {
break;
}
}
}
快速排序
public static void quicksort(int a[], int bt, int ed) {
if (bt < ed) {
int pivot = pivotpartition(a, bt, ed);
quicksort(a, bt, pivot - 1);
quicksort(a, pivot + 1, ed);
}
}
private static void swapvar(int a[], int bt, int ed) {
int mid = bt + (ed - bt) / 2;
if (mid != bt) {
a[bt] = a[bt] ^ a[mid];
a[mid] = a[bt] ^ a[mid];
a[bt] = a[bt] ^ a[mid];
}
}
private static int pivotpartition(int a[], int bt, int ed) {
// 取中间值作为stand，防止数组有序出现o(n^2)情况
swapvar(a, bt, ed);
int stand = a[bt];
while (bt < ed) {
while (bt < ed && a[ed] >= stand) {
ed--;
}
if (bt < ed) {
a[bt++] = a[ed];
}
while (bt < ed && a[bt] <= stand) {
bt++;
}
if (bt < ed) {
a[ed--] = a[bt];
}
}
a[bt] = stand;
return bt;
}
归并排序
public static void mergesort(int a[], int bt, int ed) {
if (bt < ed) {
int mid = bt + (ed - bt) / 2;
mergesort(a, bt, mid);
mergesort(a, mid + 1, ed);
mergearray(a, bt, mid, ed);
}
}
private static void mergearray(int a[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (a[i] <= a[j]) {
tmp[k] = a[i++];
} else {
tmp[k] = a[j++];
}
}
while (i <= mid) {
tmp[k++] = a[i++];
}
while (j <= ed) {
tmp[k++] = a[j++];
}
for (i = 0; i < k; i++) {
a[bt + i] = tmp[i];
}
}
测试程序
来将以上算法归纳总结一下：
import java.util.scanner;
public class javasort {
public static void main(string args[]) {
scanner cin = new scanner(system.in);
int a[], n;
while (cin.hasnext()) {
n = cin.nextint();
a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = cin.nextint();
}
// bubblesort(a, n);
// insertsort(a, n);
// selectsort(a, n);
// heapsort(a, n);
// quicksort(a, 0, n - 1);
mergesort(a, 0, n - 1);
printarr(a);
}
}
/**
* 归并排序
*
* @param a
* @param bt
* @param ed
*/
public static void mergesort(int a[], int bt, int ed) {
if (bt < ed) {
int mid = bt + (ed - bt) / 2;
mergesort(a, bt, mid);
mergesort(a, mid + 1, ed);
mergearray(a, bt, mid, ed);
}
}
/**
* 合并数组
*
* @param a
* @param bt
* @param mid
* @param ed
*/
private static void mergearray(int a[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (a[i] <= a[j]) {
tmp[k] = a[i++];
} else {
tmp[k] = a[j++];
}
}
while (i <= mid) {
tmp[k++] = a[i++];
}
while (j <= ed) {
tmp[k++] = a[j++];
}
for (i = 0; i < k; i++) {
a[bt + i] = tmp[i];
}
}
/**
* 快速排序
*
* @param a
* @param bt
* @param ed
*/
public static void quicksort(int a[], int bt, int ed) {
if (bt < ed) {
int pivot = pivotpartition(a, bt, ed);
quicksort(a, bt, pivot - 1);
quicksort(a, pivot + 1, ed);
}
}
private static void swapvar(int a[], int bt, int ed) {
int mid = bt + (ed - bt) / 2;
if (mid != bt) {
a[bt] = a[bt] ^ a[mid];
a[mid] = a[bt] ^ a[mid];
a[bt] = a[bt] ^ a[mid];
}
}
/**
* 快排寻找基准点位置
*
* @param a
* @param bt
* @param ed
* @return
*/
private static int pivotpartition(int a[], int bt, int ed) {
// 取中间值作为stand，防止数组有序出现o(n^2)情况
swapvar(a, bt, ed);
int stand = a[bt];
while (bt < ed) {
while (bt < ed && a[ed] >= stand) {
ed--;
}
if (bt < ed) {
a[bt++] = a[ed];
}
while (bt < ed && a[bt] <= stand) {
bt++;
}
if (bt < ed) {
a[ed--] = a[bt];
}
}
a[bt] = stand;
return bt;
}
/**
* 堆排序（从小到大）
*
* @param a
* @param n
*/
public static void heapsort(int a[], int n) {
int tmp;
// 构建大根堆
buildmaxheap(a, n);
for (int j = n - 1; j >= 1; j--) {
tmp = a[0];
a[0] = a[j];
a[j] = tmp;
maxheapify(a, 0, j);
}
}
/**
* 构建大根堆
*
* @param a
* @param n
*/
private static void buildmaxheap(int a[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapify(a, i, n);
}
}
/**
* 维护从下标i开始的最大堆
*
* @param a
* @param i
* @param n
*/
private static void maxheapify(int a[], int i, int n) {
int left, right, loc;
while (i < n) {
left = 2 * i + 1;
right = 2 * i + 2;
loc = i;
if (left < n && a[left] > a[i]) {
i = left;
}
if (right < n && a[right] > a[i]) {
i = right;
}
if (loc != i) {
a[i] = a[loc] ^ a[i];
a[loc] = a[loc] ^ a[i];
a[i] = a[loc] ^ a[i];
} else {
break;
}
}
}
/**
* 直接选择排序
*
* @param a
* @param n
*/
public static void selectsort(int a[], int n) {
int i, j, loc;
for (i = 0; i < n; i++) {
loc = i;
for (j = i + 1; j < n; j++) {
if (a[j] < a[loc]) {
loc = j;
}
}
if (loc != i) {
a[i] = a[i] ^ a[loc];
a[loc] = a[i] ^ a[loc];
a[i] = a[i] ^ a[loc];
}
}
}
/**
* 直接插入排序
*
* @param a
* @param n
*/
public static void insertsort(int a[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = a[i];
for (j = i - 1; j >= 0; j--) {
if (a[j] > tmp) {
a[j + 1] = a[j];
} else {
break;
}
}
a[j + 1] = tmp;
}
}
/**
* 冒泡排序
*
* @param a
* @param n
*/
public static void bubblesort(int a[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
a[j] = a[j] ^ a[j + 1];
a[j + 1] = a[j] ^ a[j + 1];
a[j] = a[j] ^ a[j + 1];
}
}
}
}
/**
* 打印数组
*
* @param a
*/
public static void printarr(int a[]) {
for (int i = 0; i < a.length; i++) {
if (i == a.length - 1) {
system.out.printf("%d\n", a[i]);
} else {
system.out.printf("%d ", a[i]);
}
}
}
}
如对本文有疑问， 点击进行留言回复！！
荐 嵌入式linux开发环境搭建（Docker版，基于iTop 4412开发板）
SpringBoot项目部署到服务器之 Liunx环境安装jdk详细步骤
网友评论