Bubble sort
Bubble sort is one of the simplest sorts, and the general idea is to swap small numbers to the front by comparing and swapping them with neighboring elements. This process is similar to a blister rising, hence the name. Time complexity O(n ^ 2), stable sorting.
package com.yxx.algorithm.sort;
import static com.yxx.algorithm.sort.Util.*;
/** * Bubble sort * time complexity O(n ^ 2) */
public class BubbleSort {
/** * replaces the smallest element to the first */ by comparing it with the neighboring element
public static void bubbleSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
boolean flag;
for (int length = array.length, i = 0; i < length - 1; i++) {
flag = true;
for (int j = length - 1; j > i; j--) {
if (array[j - 1] > array[j]) {
swap(array, j, j - 1);
flag = false; }}if (flag) {
break; }}}public static void main(String[] args) { printArray(ARRAY); bubbleSort(ARRAY); printArray(ARRAY); }}Copy the codeSelection sort
The idea of selection sort is actually similar to bubble sort, but the process is different. Bubble sort is to compare and exchange with adjacent elements, selection sort is to traverse the whole, by comparing to obtain the smallest element for exchange. In fact, the selection sort can be regarded as the optimization of bubble sort, because its purpose is the same, but the selection sort can only be exchanged under the premise of determining the minimum number, greatly reducing the number of exchanges. The time complexity of selection sort is O(n^2).
package com.yxx.algorithm.sort;
/** * Select sort * time complexity O(n ^ 2) */
public class ChoseSort {
/** * swap each time with the smallest number */
public static void choseSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
for (int i = 0; i < array.length - 1; i++) {
int mixIndex = i;
for (int j = i + 1; j < array.length; j++) {
if(array[j] < array[mixIndex]) { mixIndex = j; } } Util.swap(array, mixIndex, i); }}public static void main(String[] args) { choseSort(Util.ARRAY); Util.printArray(Util.ARRAY); }}Copy the codeInsertion sort
Insert sort sort by finding the right place to insert. The insertion position is determined by constantly comparing the element to be inserted with the existing element. Be careful when inserting a number to make sure that the number in front of it is in order. Simple insertion sort also takes O(n^2).
package com.yxx.algorithm.sort;
/** * Insert sort * time complexity O (n ^ 2) */
public class InsertSort {
/** ** insert */ one by one
public static void insertSort(int[] array) {
if(! Util.isValidArray(array)) {return;
}
for (int i = 1; i < array.length; i++) { // Start with the second index
int target = array[i];
int j = i;
while (j > 0 && array[j - 1] > target) {
array[j] = array[j - 1]; // The element moves back
j--; // The pointer moves forward} array[j] = target; }}public static void main(String[] args) { insertSort(Util.ARRAY); Util.printArray(Util.ARRAY); }}Copy the codeQuick sort
Quicksort is the best sorting algorithm in practice. Quicksort by determining a reference number and the left and right Pointers, the left pointer to find the number greater than the reference number, the right pointer to find the number smaller than the reference number, and then swap, until the two Pointers meet, and then swap with the reference number, according to the encounter position of the left and right two sub-sequence recursive sort. Quicksort is unstable and its time average time complexity is O(NLGN).
package com.yxx.algorithm.sort;
import sun.net.www.protocol.http.AuthenticationInfo;
/** * quicksort * time complexity O(NLGN) * unstable * bubbling + binary + recursive divide and conquer ** /
public class QuickSort {
private static void quickSort(int[] array) {
int left = 0;
int right = array.length - 1;
quickSort(array, left, right);
}
private static void quickSort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int newLeft = partition(array,left,right);
quickSort(array, left, newLeft - 1);
quickSort(array, newLeft + 1, right);
}
private static int partition(int[] array,int left,int right) {
int pivotKey = array[left];
int pivotPoint = left;
while (left < right) {
// The right pointer finds a number smaller than the base
while (left < right && array[right] >= pivotKey) {
right--;
}
// The left pointer finds a number greater than the base
while (left < right && array[left] <= pivotKey) {
left++;
}
Util.swap(array, left, right);
}
// Swap the value of the base and the location found
Util.swap(array, left, pivotPoint);
array[left] = pivotKey;
return left;
}
public static void main(String[] args) { Util.printArray(Util.ARRAY); quickSort(Util.ARRAY); Util.printArray(Util.ARRAY); }}Copy the codeHill sorting
Hill sort is an efficient implementation of insertion sort, also known as reduced increment sort. Basic idea: firstly, divide the whole sequence of records to be arranged into several sub-sequences for direct insertion sort, and then perform a direct insertion sort for all records when the records in the whole sequence are basically in order. The analysis of Hill sort is complex, and the time complexity is a function of the increments taken, which involves some mathematical difficulties. However, based on a large number of experiments, the time complexity can reach O(n^1.3) when N is in a certain range.
Hill sort wiki
package com.yxx.algorithm.sort;
/** * Hill sort - Hill sort is an efficient implementation of insertion sort, also called reduced delta sort * * Hill delta */
public class ShellInsert {
public static void shellSort(int[] array) {
if(! Util.isValidArray(array)) {return;
}
int step = array.length / 2;
while (step >= 1) {
shellInsert(array, step);
step /= 2; }}private static void shellInsert(int[] array, int step) {
for (int i = step; i < array.length; i++) {
int target = array[i];
int j = i;
while(j >= step && array[j - step] > target) { array[j] = array[j - step]; j -= step; } array[j] = target; }}public static void main(String[] args) { Util.printArray(Util.ARRAY); shellSort(Util.ARRAY); Util.printArray(Util.ARRAY); }}Copy the codeMerge sort
Merge sort uses the idea of recursive divide and conquer. Second in speed to quicksort, stable sorting algorithm, generally used for the overall disorder, but the relative order of the subitems of the sequence. Average Time complexity: O(nlogn) Optimal time complexity: O(n) Worst time complexity: O(nlogn) Space complexity: O(n) Stability: Stable
package com.yxx.algorithm.sort;
/** * merge sort * time complexity O(NLGN) */
public class MergeSort {
public static void main(String[] args) {
Util.printArray(Util.ARRAY);
mergeSort(Util.ARRAY);
Util.printArray(Util.ARRAY);
}
public static void mergeSort(int[] array) {
int length = array.length;
int[] temp = new int[length];
merge_sort_recursive(array, temp, 0, length - 1);
}
// Merge sort (Java- recursive version)
static void merge_sort_recursive(int[] arr, int[] temp, int start, int end) {
if (start >= end) {
return;
}
int mid = (end - start) / 2 + start;// Middle position
merge_sort_recursive(arr, temp, start, mid);// Recursive left subsequence
merge_sort_recursive(arr, temp, mid + 1, end);// Recursive right subsequence
merge(arr, temp, start, mid, end);// merge sequence
}
private static void merge(int[] arr, int[] temp, int start, int mid, int end) {
int i = start;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else{ temp[t++] = arr[j++]; }}while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= end) {
temp[t++] = arr[j++];
}
for (int k = 0; k < t; k++) { arr[start++] = temp[k]; }}}Copy the code