排序算法的Java实现全攻略

网友投稿 184 2023-07-30


排序算法的Java实现全攻略

Collections.sort()

java的排序可以用Collections.sort() 排序函数实现。

用Collections.sort方法对list排序有两种方法:

第一种是list中的对象实现Comparable接口,如下http://:

/**

* 根据order对User排序

*/

public class User implements 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 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 list = new ArrayList();

//此处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 list = new ArrayList();

list.add(user2);

list.add(user1);

Collections.sort(list,new Comparator(){

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] ohRvORp> 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]);

}

}

}

}


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:进一步理解Java中的多态概念
下一篇:Java的Socket通讯基础编程完全指南
相关文章

 发表评论

暂时没有评论,来抢沙发吧~