Java implements code for several common sorting algorithms
- 2020-04-01 02:16:10
- OfStack
Stability (stability)
A sorting algorithm is stable, that is, when there are two keys R and S with equal records, and R appears before S in the original list, R will also be before S in the sorted list.
Sorting algorithm classification
Common examples are insert (insert sort/hill sort), swap (bubble sort/quicksort), select (select sort), merge (merge sort), etc.
I. insertion sort
Insertion Sort, which works by building ordered sequences and, for unsorted data, scanning backward and forward through the sorted sequence to find the location and insert. In the implementation of insertion sort, in-place sort is usually adopted (that is, the sort that only needs extra space of O(1)). Therefore, in the backward and forward scanning process, the sorted elements need to be moved backward repeatedly to provide insertion space for the latest elements.
Generally, insertion sort is implemented on an array using in-place. The specific algorithm is described as follows:
Start with the first element, which can be considered sorted.
Take the next element and scan backwards and forwards through the sorted sequence of elements.
If the element (sorted) is greater than the new element, move the element to the next position.
Repeat step 3 until you find the position where the sorted element is less than or equal to the new element.
After the new element is inserted into that location.
Repeat steps 2 to 5.
public static void insertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
Two. Hill sort
A Shell Sort is a type of insertion Sort. It is an improvement of direct insertion sort algorithm. This method, also known as reduced delta sort, got its name from dl.shell, which was proposed in 1959.
Hill sort proposes an improved method based on the following two properties of insertion sort:
Insertion sort is efficient in the operation of almost sorted data, that is, it can achieve the efficiency of linear sort.
But insertion sort is generally inefficient because it can only move the data one bit at a time.
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h)
Collections.swap(a, j, j-h);
}
Three. Bubble sort
Bubble Sort is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The task of visiting a sequence is repeated until there is no need to swap, that is, the sequence has been sorted. The algorithm got its name because smaller elements slowly "float" to the top of the list by swapping.
The bubble sort algorithm works as follows:
Compare adjacent elements, and if the first one is bigger than the second, swap them.
Do the same thing for each pair of adjacent elements, starting with the first pair and ending with the last pair, at which point the last element should be the largest number.
Repeat the above steps for all elements except the last one.
Keep repeating the above steps for fewer and fewer elements at a time until there are no pairs of Numbers to compare.
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
//If the exchange occurs in one of the inner loops, continue the comparison; If no exchange occurs in an inner loop, it is considered sorted.
if (!isSort)
break;
}
}
Quick sort
Quicksort is an improvement on bubble sort. Proposed by c. a. r. Hoare in 1962. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.
Quicksort USES a Divide and conquer strategy to Divide a list into two sub-lists.
Steps as follows:
Pick an element from the sequence, called pivot.
Reorder the sequence so that all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed after the base (the same number can go to either side). After the partition exits, the benchmark is in the middle of the sequence. This is called a partition operation.
Recursive is the recursive sorting of subseries of elements less than the base value and subseries greater than the base value.
/*
* more efficient implements for quicksort. <br />
* use left, center and right median value (@see #median()) for the pivot, and
* the more efficient inner loop for the core of the algorithm.
*/
public class Quicksort {
public static final int CUTOFF = 11;
/**
* quick sort algorithm. <br />
*
* @param arr an array of Comparable items. <br />
*/
public static <T extends Comparable<? super T>> void quicksort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* get the median of the left, center and right. <br />
* order these and hide the pivot by put it the end of of the array. <br />
*
* @param arr an array of Comparable items. <br />
* @param left the most-left index of the subarray. <br />
* @param right the most-right index of the subarray.<br />
* @return T
*/
public static <T extends Comparable<? super T>> T median(T[] arr, int left, int right) {
int center = (left + right) / 2;
if (arr[left].compareTo(arr[center]) > 0)
swapRef(arr, left, center);
if (arr[left].compareTo(arr[right]) > 0)
swapRef(arr, left, right);
if (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, center, right);
swapRef(arr, center, right - 1);
return arr[right - 1];
}
/**
* internal method to sort the array with quick sort algorithm. <br />
*
* @param arr an array of Comparable Items. <br />
* @param left the left-most index of the subarray. <br />
* @param right the right-most index of the subarray. <br />
*/
private static <T extends Comparable<? super T>> void quickSort(T[] arr, int left, int right) {
if (left + CUTOFF <= right) {
// find the pivot
T pivot = median(arr, left, right);
// start partitioning
int i = left, j = right - 1;
for (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
if (i < j)
swapRef(arr, i, j);
else
break;
}
// swap the pivot reference back to the small collection.
swapRef(arr, i, right - 1);
quickSort(arr, left, i - 1); // sort the small collection.
quickSort(arr, i + 1, right); // sort the large collection.
} else {
// if the total number is less than CUTOFF we use insertion sort
// instead (cause it much more efficient).
insertionSort(arr, left, right);
}
}
/**
* method to swap references in an array.<br />
*
* @param arr an array of Objects. <br />
* @param idx1 the index of the first element. <br />
* @param idx2 the index of the second element. <br />
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* method to sort an subarray from start to end with insertion sort
* algorithm. <br />
*
* @param arr an array of Comparable items. <br />
* @param start the begining position. <br />
* @param end the end position. <br />
*/
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int start, int end) {
int i;
for (int j = start + 1; j <= end; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Integer[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String[] args) {
Integer[] data = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(data);
quicksort(data);
printArray(data);
}
}
Select sort
Selection sort is a simple and intuitive sorting algorithm. Here's how it works. Find the smallest (large) element in the unsorted sequence, store it at the beginning of the sorted sequence, then continue to look for the smallest (large) element from the remaining unsorted elements, and place it at the end of the sorted sequence. And so on, until all the elements are sorted.
Since there is a sub-process of selecting the minimum value in each step of determining an element, it is figuratively called selection sort.
For example, sequence 5, 8, 5, 2, 9, we know that the first selection of the first element 5 will be swapped with the second, so the relative order of the original sequence of 2 5 will be destroyed, so selection sort is not a stable sorting algorithm.
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //The smallest index of an unordered data array
for (int j = i + 1; j < data.length; j++) { //Find the smallest data in the unordered area and save its array index
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { //If the minimum position of the non-unordered region is not the default first data, it is swapped.
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
Merge sort
Merge sort is an effective sorting algorithm based on Merge operation. This algorithm is a very typical application of Divide and Conquer.
The merge operation process is as follows:
Request a space whose size is the sum of two sorted sequences, which is used to store the merged sequences.
Set two Pointers to the starting position of the two sorted sequences.
Compare the elements to which the two Pointers point, select the relatively small element to put into the merge space, and move the pointer to the next location.
Repeat step 3 until a pointer reaches the end of the sequence.
Copies all the remaining elements of another sequence directly to the end of the merge sequence.
public static int[] mergeSort(int[] arr) {//Merge sort -- recursion
if (arr.length == 1) {
return arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Merge sort subroutine
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
break;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
return result;
}
Full code (except QuickSort)
package com.clzhang.sample.thinking;
import java.util.*;
public class CommonSort {
public static void insertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h)
Collections.swap(a, j, j-h);
}
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
//If the exchange occurs in one of the inner loops, continue the comparison; If no exchange occurs in an inner loop, it is considered sorted.
if (!isSort)
break;
}
}
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //The smallest index of an unordered data array
for (int j = i + 1; j < data.length; j++) { //Find the smallest data in the unordered area and save its array index
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { //If the minimum position of the non-unordered region is not the default first data, it is swapped.
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
public static int[] mergeSort(int[] arr) {//Merge sort -- recursion
if (arr.length == 1) {
return arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Merge sort subroutine
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
break;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
return result;
}
private static void printArray(int[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String []args){
int[] data = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.clone();
printArray(a);
bubbleSort(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
selectSort(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
insertionSort(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<data.length;i++)
list.add(data[i]);
System.out.println(list);
shellSort(list);
System.out.println(list);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}