Sorting algorithm to achieve the Java strategy
- 2020-04-01 04:06:22
- OfStack
The Collections. The sort ()
The Java sort can be implemented using the collections.sort () sort function.
There are two ways to sort a list using the collections.sort method:
The first is that the object in the list implements the Comparable interface, as follows:
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());
}
}
Test it out:
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 and add user1 here
list.add(user2);
list.add(user1);
Collections.sort(list);
for(User u : list){
System.out.println(u.getName());
}
}
}
The output is as follows
a
b
The second method is implemented according to the collections.sort overload method, for example:
public class User { //There is no need to implement the Comparable interface
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;
}
}
The main class can be written like this:
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());
}
}
}
The output is as follows
a
b
The former is simple but can only be sorted by fixed attributes, while the latter is flexible and can specify sort items temporarily, but the code is not concise enough
Choose the best.
Common sorting algorithm
Here are some Java code practices for classic sorting algorithms:
Bubble sort
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];
}
}
}
}
Direct insertion sort
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;
}
}
Direct selection sort
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];
}
}
}
Heap sort
public static void heapSort(int A[], int n) {
int tmp;
//Build a large root heap
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);
}
}
private static void buildMaxHeap(int A[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapIfy(A, i, 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;
}
}
}
Quick sort
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) {
//Take the intermediate value as stand to prevent the order of the array from 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;
}
Merge sort
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];
}
}
The test program
To summarize the above algorithms:
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);
}
}
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];
}
}
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) {
//Take the intermediate value as stand to prevent the order of the array from 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 heapSort(int A[], int n) {
int tmp;
//Build a large root heap
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);
}
}
private static void buildMaxHeap(int A[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapIfy(A, i, 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 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];
}
}
}
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 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 printArr(int A[]) {
for (int i = 0; i < A.length; i++) {
if (i == A.length - 1) {
System.out.printf("%dn", A[i]);
} else {
System.out.printf("%d ", A[i]);
}
}
}
}