Beginners learn common sorting algorithms of Java
- 2021-10-25 06:35:24
- OfStack
1. Bubble sorting
Sorting principle: Two adjacent elements are compared, and if the former is larger than the latter, the two elements are exchanged. Every time you execute it, you will determine a maximum value, and its position will be fixed, so you don't need to participate in sorting the next time.
Time complexity:
O(n^2)
Stability: Stability
Concrete realization:
public class Bubble {
/**
* Pair array a Sorts the elements in the
*/
public static void sort(Comparable[] a){
// Every bubble 1 The number of elements involved in bubble sorting is less 1 A
// The number of times to sort is the number of arrays minus the number of arrays 1
/*for (int i=a.length-1; i>0; i--){
for (int j=0; j<i; j++){
if (greater(a[j],a[j+1])){
exch(a, j,j+1);
}
}
}*/
for (int i=0; i<a.length-1; i++){
for (int j=0; j<a.length-i-1; j++){
if (greater(a[j],a[j+1])){
exch(a, j,j+1);
}
}
}
}
/**
* Comparison u Element is greater than v Element
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* Swap array subscript to i And j The location of the element of
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* Test
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6};
sort(a);
System.out.println(Arrays.toString(a));
}
}Optimization: You can add a flag bit, when bubbling 1 time is not implemented, it shows that it has been arranged, so there is no need to bubble again.
2. Select the sort
Sorting principle: Find the subscript of the minimum value from the array, and then exchange the minimum value to the front. Every time you execute, there will be a minimum position fixed before it, and then you no longer need to participate in finding the minimum.
Time complexity:
O(n^2)
Stability: Unstable
Concrete realization:
public class Selelction {
/**
* Sort an array
* @param a Array to be sorted
*/
public static void sort(Comparable[] a){
for (int i=0; i<a.length-1; i++){
// Find the smallest value
int minIndex = i;
// Note that there is no need to reduce here 1
for (int j=i+1; j<a.length; j++){
//Comparable Array You cannot compare sizes directly with subscripts
if (greater(a[minIndex],a[j])){
minIndex = j;
}
}
// Exchange
if (minIndex != i){
exch(a, minIndex, i);
}
}
}
/**
* Comparative number 1 Is the parameter greater than the 2 Parameters
* @param a
* @param b
* @return No. 1 1 Is the parameter greater than the 2 Parameters
*/
private static boolean greater(Comparable a, Comparable b){
return a.compareTo(b) > 0;
}
/**
* Swap two elements of an array
* @param a Array
* @param i Array subscript
* @param j Array subscript
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* Test method
* @param args
*/
public static void main(String[] args) {
Integer[] array = {1,6,7,3,2,5,7,8,4,0,5,3,7};
sort(array);
System.out.println(Arrays.toString(array));
}
3. Simple Insert Sort
Sorting principle: Divide the array into two groups, the left group is sorted, and the right group is unsorted. Then compare the unsorted first with the left one from back to front, and exchange it if it is smaller than the previous one until the previous value is smaller than it or equal to it.
Time complexity:
O(n^2)
Stability: Stability
Concrete realization:
public class Insertion {
/**
* Pair array a Sorts the elements in the
*/
public static void sort(Comparable[] a){
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--){
if (greater(a[j-1],a[j])){
exch(a, j-1, j);
}else {
break;
}
}
}
}
/**
* Comparison u Element is greater than v Element
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* Swap array subscript to i And j The location of the element of
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* Test
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}Optimization idea: The number that will be inserted is saved first, and then the exchanged code can be changed to overlay, which is equivalent to moving back, and then the value saved before is put in when finding a suitable position.
4. Hill sort
Sorting principle: It is an optimized version of insertion sorting. Insertion sorting can only be compared by one, while Hill sorting adds one growth amount, which can be compared across elements and relatively reduces the number of comparisons and exchanges.
Time complexity:
O(n^1.3)
Stability: Unstable
Concrete realization:
public class Shell {
/**
* Sort an array
* @param a Array to be sorted
* @return Ordered array
*/
public static void sort(Comparable[] a){
//1. Determine the amount of growth h Value of
int h=1;
while(h < a.length/2){
h = h*2+1;
}
//2. Sort
while(h>=1){
// Find the number to be sorted 1 Values
for (int i=h; i<a.length; i++){
for (int j=i; j>=h; j-=h){
if (greater(a[j-h],a[j])){
exch(a, j, j-h);
}else{
break;
}
}
}
//h Decrease
h/=2;
}
}
/**
* Comparison u Element is greater than v Element
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* Swap array subscript to i And j The location of the element of
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Test data
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8, 6, 7};
sort(a);
System.out.println(Arrays.toString(a));
}
}
5. Merge and sort
Sorting principle: The recursive idea is used. First, the array is recursively decomposed from the middle, then the left sub-array is sorted first, then the right sub-array is sorted again, and finally it is merged into an array. The core method is merge method.
Time complexity:
O(nlogn)
Stability: Stability
Concrete realization:
public class Merge {
/**
* Auxiliary array
*/
private static Comparable[] access;
/**
* Pair array a Sort
* @param a
*/
public static void sort(Comparable[] a){
//1. Initialize the auxiliary array
access = new Comparable[a.length];
//2. Define two subscript values
int lo = 0;
int hi = a.length -1;
//3. Call the grouping sort function
sort(a, lo, hi);
}
/**
* Pair array a In lo To hi Sort
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
// Protection
if (hi <= lo){
return;
}
//1. Get mid
int mid = lo + (hi-lo)/2;
//2. Grouping and sorting the left array
sort(a, lo, mid);
//3. Grouping and sorting right arrays
sort(a, mid+1, hi);
//4. Combine two numbers and
merge(a, lo, mid, hi);
}
/**
* Sorting and merging two arrays
* @param a
* @param lo
* @param mid
* @param hi
*/
private static void merge(Comparable[] a, int lo, int mid, int hi){
//1. Definition 3 Pointers
int i=lo;
int p1=lo;
int p2=mid+1;
//2. Traverse the two sub-arrays separately until there are 1 The array traversal is completed
while (p1 <= mid && p2 <= hi){
if (less(a[p1], a[p2])){
access[i++] = a[p1++];
}else{
access[i++] = a[p2++];
}
}
//3 . Will the rest 1 The remaining values of the arrays are put into the auxiliary array
while(p1 <= mid){
access[i++] = a[p1++];
}
while(p2 <= hi){
access[i++] = a[p2++];
}
//4 . Overwrite the values in the secondary array to the original array
for (int index=lo; index<=hi; index++){
a[index] = access[index];
}
}
/**
* Comparative number 1 Is the subscript value less than the 2 Subscript value
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) <= 0;
}
/**
* Test
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
6. Quick Sort
Sorting principle: The first value of the array is set to the middle value, which is smaller than the middle value to the left and larger than the middle value to the right. Then do the same operation on the left, and finally do the same operation on the right. The core method is the partition method, which moves the small number to the left, the large number to the right, and finally returns the subscript of the median value.
Time complexity:
O(nlogn)
Stability: Unstable
Concrete realization:
public class Quick {
/**
* Pair array a Sort
* @param a
*/
public static void sort(Comparable[] a){
int lo = 0;
int hi = a.length-1;
sort(a, lo, hi);
}
/**
* Pair array a In lo To hi Sort
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
// Protection
if (hi <= lo){
return;
}
// Get intermediate value
int mid = partition(a, lo, hi);
// Sort the left subarray
sort(a, lo, mid-1);
// Sort the right subarray
sort(a, mid+1, hi);
}
/**
* Will be compared with the first in the subarray 1 The smaller number is placed to the left, the larger number is placed to the right, and finally the subscript of the median value is returned
* @param a
* @param lo
* @param hi
* @return
*/
private static int partition(Comparable[] a, int lo, int hi){
//1. Define two pointers
int p1= lo;
int p2 = hi+1;
while (true){
//2. Move the right pointer to find the 1 Number less than the standard value
while(less(a[lo],a[--p2])){
if (p2 == lo){
break;
}
}
//3. Move the left pointer to find the 1 Number greater than the standard value
while(less(a[++p1],a[lo])){
if (p1 == hi){
break;
}
}
if (p1 >= p2){
//5. Exit loop
break;
}else {
//4. Exchange two values
exch(a, p1, p2);
}
}
//6. Finally, put the first of the subarray 1 The value is exchanged with the value indicated by the right pointer, and finally its subscript is returned
exch(a, lo, p2);
return p2;
}
/**
* Comparative number 1 Is the subscript value less than the 2 Subscript value
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) < 0;
}
/**
* Swap two subscript values in an array
* @param a
* @param i
* @param j
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* Test
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
Summarize
That's all for this article. I hope I can help you, and I hope you can pay more attention to more contents of this site!