stability (stability)
A sorting algorithm is stable, that is, when there are two equal records of the keys R and S, and R appears before S in the original list, R will also appear before S in the sorted list.
Sorting algorithm classification
Common ones include insertion (insertion sort/Hill sort), exchange (bubble sort/quick sort), selection (selection sort), merge (merge sort), etc.
1. Insertion sort
Insertion Sort (Insertion Sort) works by constructing an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence to find the corresponding position and insert it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.
Generally speaking, insertion sort is implemented on arrays using in-place. The specific algorithm is described as follows:
Starting from the first element, the elements can be considered to have been sorted.
Get the next element and scan from back to front in the sorted sequence of elements.
If the element (sorted) is larger than the new element, move the element to the next position.
Repeat step 3 until you find a position where the sorted element is less than or equal to the new element.
After inserting the new element at that position.
Repeat steps 2~5.
Copy the code code as follows:
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;
}
}
2. Hill sorting
Shell Sort is a type of insertion sort. It is an improvement on the direct insertion sort algorithm. This method is also called reducing incremental sorting, because DL. Shell was named after it was proposed in 1959.
Hill sorting proposes an improved method based on the following two properties of insertion sort:
Insertion sort is highly efficient when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting.
But insertion sort is generally inefficient because insertion sort can only move data one bit at a time.
Copy the code code as follows:
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(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
3. Bubble sorting
Bubble Sort (Bubble Sort, translated from Taiwan as: Bubble Sort or Bubble Sort) is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The work of visiting the array is repeated until no more exchanges are needed, which means that the array has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the array through swapping.
The bubble sort algorithm works as follows:
Compare adjacent elements, and if the first is greater than the second, swap them both.
Do the same 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 each time until there are no pairs of numbers left to compare.
Copy the code code as follows:
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 an exchange occurs in an inner loop, continue the comparison; if no exchange occurs in an inner loop, it is considered to have been sorted.
if (!isSort)
break;
}
}
4. Quick sort
Quicksort is an improvement on bubble sort. Proposed by CAR Hoare in 1962. Its basic idea is to divide the data to be sorted into two independent parts through one sorting. All the data in one part is smaller than all the data in the other part, and then use this method to quickly separate the two parts of the data. Sorting, the entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.
Quick sort uses the divide and conquer strategy to divide a list into two sub-lists.
The steps are:
Picking out an element from the sequence is called a "pivot".
Reorder the array 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 behind the base (the same number can go to either side). After this partition exits, the base is in the middle of the sequence. This is called a partition operation.
Recursively sort the subarray of elements less than the base value and the subarray of elements greater than the base value.
Copy the code code as follows:
/*
* 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).
Sort(arr, insertion 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 beginning 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);
}
}
5. Selection sorting
Selection sort is a simple and intuitive sorting algorithm. Here's how it works. First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.
Because each process of determining elements will have a sub-process of selecting the minimum value, people vividly call it selection sorting.
For example, in the sequence 5 8 5 2 9, we know that the first element 5 will be exchanged with 2 in the first pass. Then the relative order of the two 5s in the original sequence will be destroyed, so the selection sort is not stable. Sorting algorithm.
Copy the code code as follows:
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //The minimum data array index of the unordered area
for (int j = i + 1; j < data.length; j++) { // Find the smallest data in the unordered area and save its array subscript
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // If the minimum position of the unordered area is not the default first data, exchange it.
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
6. Merge sort
Merge sort is an effective sorting algorithm based on merge operations. This algorithm is a very typical application using the divide and conquer method (Divide and Conquer).
The process of merge operation is as follows:
Apply for space so that its size is the sum of the two sorted sequences. This space is used to store the merged sequence.
Set two pointers, the initial positions are the starting positions of the two sorted sequences.
Compare the elements pointed to by the two pointers, select the relatively small element and put it into the merge space, and move the pointer to the next position.
Repeat step 3 until a pointer reaches the end of the sequence.
Copies all remaining elements of the other sequence directly to the end of the merged sequence.
Copy the code code as follows:
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;
}
Complete code (except QuickSort)
Copy the code code as follows:
package com.clzhang.sample.thinking;
import java.util.*;
/**
* Java implementation of several common sorting algorithms
* @author acer
*
*/
public class CommonSort {
/**
* The specific algorithm of insertion sort is described as follows:
* 1. Starting from the first element, the element can be considered to have been sorted
* 2. Take out the next element and scan from back to front in the sorted element sequence
* 3. If the element (sorted) is larger than the new element, move the element to the next position
* 4. Repeat step 3 until you find the position where the sorted element is less than or equal to the new element
* 5. After inserting the new element into this position
* 6. Repeat steps 2~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;
}
}
/**
* Hill sorting, please refer to Wikipedia for algorithm implementation ideas; suitable for large number of sorting operations.
*/
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(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
/**
* The operation of the bubble sort algorithm is as follows:
* 1. Compare adjacent elements. If the first one is bigger than the second one, swap them both.
* 2. Do the same work for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the largest number.
* 3. Repeat the above steps for all elements except the last one.
* 4. Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare. [1]
*/
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 an exchange occurs in an inner loop, continue the comparison; if no exchange occurs in an inner loop, it is considered to have been sorted.
if (!isSort)
break;
}
}
/**
* The basic idea of selection sorting is:
* 1. During the process of traversing the array, if i represents the current sequence number that needs to be sorted, you need to find the minimum value among the remaining [i+1...n-1].
* 2.Then exchange the minimum value found with the value pointed to by i.
* Because each process of determining elements will have a sub-process of selecting the minimum value, people vividly call it selection sorting.
* @param data
*/
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //The minimum data array index of the unordered area
for (int j = i + 1; j < data.length; j++) { // Find the smallest data in the unordered area and save its array subscript
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // If the minimum position of the unordered area is not the default first data, exchange it.
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
/**
* The process of merge operation is as follows:
* 1. Apply for space so that its size is the sum of the two sorted sequences. This space is used to store the merged sequence.
* 2. Set two pointers, the initial positions are the starting positions of the two sorted sequences.
* 3. Compare the elements pointed to by the two pointers, select the relatively small element and put it into the merge space, and move the pointer to the next position
* 4. Repeat step 3 until a pointer reaches the end of the sequence
* 5. Copy all remaining elements of the other sequence directly to the end of the merged 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;
}
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));
}
}