Examples of Java 7 common sorting methods in detail
- 2020-07-21 07:50:27
- OfStack
Direct insertion sort
<code class="language-java hljs ">import java.util.HashMap;
public class InsertSort {
private static int contrastCount = 0;// Compare the number of
private static int swapCount = 0;// Switching frequency
public static void main(String[] args) {
System.out.println(" Direct insertion sort: \n Assuming the previous sequence is sorted, insert the unsorted Numbers into the sorted sequence , Time complexity O(n^2), Space complexity O(1) , stable sorting ");
HashMap<integer,integer> hashMap = new HashMap<integer,integer>();
init(hashMap);// Initialize the
System.out.println(" The initial sequence is: ");
print(hashMap, 0);// print
insert(hashMap);// The sorting
}
/**
* Initialization function
* @param hashMap
*/
private static void init(HashMap<integer, integer=""> hashMap) {
hashMap.put(0, null);// The first 1 Place empty
hashMap.put(1, 0);
hashMap.put(2, 5);
hashMap.put(3, 11);
hashMap.put(4, 12);
hashMap.put(5, 13);
hashMap.put(6, 4);
hashMap.put(7, 1);
hashMap.put(8, 5);
hashMap.put(9, 8);
hashMap.put(10, 6);
hashMap.put(11, 4);
hashMap.put(12, 8);
}
/**
* Insert sort
* @param hashMap The table to be sorted
*/
private static void insert(HashMap<integer, integer=""> hashMap){
System.out.println(" Start insertion sort: ");
int i,j;
// Sorting start time
long start = System.currentTimeMillis();
for(i=2; i<hashmap.size(); author="" code="" contrastcount="0;// Compare the number of " count="1;// Only count execution times " d="1, Time complexity o(n^1.3), Space complexity o(1) Unstable sort ");" end="System.currentTimeMillis();" h2="" hashmap="" hhf="" hillsort="" i="1;" id=" Hill sorting " import="" int="" integer="" j="" long="" n="" param="" pre="" private="" public="" start="System.currentTimeMillis();" static="" swapcount="0;// Switching frequency " void="" x="1;x<=d;x++){//1 A total of d group "></hashmap.size();></integer,></integer,></integer,integer></integer,integer></code>Bubble sort
<code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap;
/**
* Bubble sort
* @author HHF
* 2014 years 3 month 19 day
*/
public class BubbleSort {
private static int contrastCount = 0;// Compare the number of
private static int swapCount = 0;// Switching frequency
public static void main(String[] args) {
System.out.println(" Bubble sort: \n The first 1 The wheel precipitates the maximum value to the bottom, using the pairwise comparison method from scratch, if i Is greater than i++ Then switch, down 1 From the first time 1 I start the loop, and I subtract the number of comparisons 1 , and then repeat in turn ,"
+ "\n if 1 The second comparison is any exchange, can be terminated early, time complexity O(n^2), Space complexity O(1) , stable sorting ");
HashMap<integer,integer> hashMap = new HashMap<integer,integer>();
init(hashMap);// Initialize the
System.out.println(" The initial sequence is: ");
print(hashMap, 0);// print
bubble(hashMap);// The sorting
}
/**
* Initialization function
* @param hashMap
*/
private static void init(HashMap<integer, integer=""> hashMap) {
hashMap.put(0, null);// The first 1 Place empty
hashMap.put(1, 10);
hashMap.put(2, 5);
hashMap.put(3, 11);
hashMap.put(4, 12);
hashMap.put(5, 13);
hashMap.put(6, 4);
hashMap.put(7, 1);
hashMap.put(8, 5);
hashMap.put(9, 8);
hashMap.put(10, 6);
hashMap.put(11, 4);
hashMap.put(12, 8);
}
/**
* Do bubble sort
* @param hashMap The table to be sorted
*/
private static void bubble(HashMap<integer, integer=""> hashMap){
System.out.println(" Start bubbling sort: ");
// Sorting start time
long start = System.currentTimeMillis();
boolean swap = false;// Whether or not exchange occurs
int count = 1;// Just to count
for(int i=1; i<hashmap.size(); int="" j="1;" swap="false;">hashMap.get(j+1)){// You need to swap j and j+1
hashMap.put(0, hashMap.get(j));
hashMap.put(j, hashMap.get(j+1));
hashMap.put(j+1, hashMap.get(0));
swap = true;
contrastCount++;// happen 1 comparative
swapCount++;// happen 1 swaps
swapCount++;// happen 1 swaps
swapCount++;// happen 1 swaps
}
contrastCount++;// Jump out of the if There are 1 comparative
}
print(hashMap, count++);
if(!swap)
break;
}
// End of sorting time
long end = System.currentTimeMillis();
System.out.println(" The result is: ");
print(hashMap, 0);// Outputs the sequence at the end of the sort
hashMap.clear();// empty
System.out.print("1 A total of the "+contrastCount+" comparative \t");
System.out.print("1 A total of the "+swapCount+" swaps \t");
System.out.println(" Execution time is "+(end-start)+" ms ");
}
/**
* Prints the sorted elements
* @param hashMap Sorted tables
* @param j The first j Trip to sort
*/
private static void print(HashMap<integer, integer=""> hashMap, int j){
if(j != 0)
System.out.print(" The first "+j+" Trip: \t");
for(int i=1; i<hashmap.size(); code=""></hashmap.size();></integer,></hashmap.size();></integer,></integer,></integer,integer></integer,integer></code></code>Quick sort
<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap;
public class QuickSort {
private static int contrastCount = 0;// Compare the number of
private static int swapCount = 0;// Switching frequency
public static void main(String[] args) {
System.out.println(" Quicksort: \n take 1 The Numbers are the dividing line, the ones that are smaller are on the left, the ones that are larger are on the right, and then you recurse to the left and the right , Time complexity O(nLgn), Space complexity O(n) Unstable sort ");
HashMap<integer,integer> hashMap = new HashMap<integer,integer>();
init(hashMap);// Initialize the
System.out.println(" The initial sequence is: ");
print(hashMap, 0, 0);// print
System.out.println(" Start quicksort: ");
// Sorting start time
long start = System.currentTimeMillis();
quick(hashMap, 1, hashMap.size()-1);// The sorting
// End of sorting time
long end = System.currentTimeMillis();
System.out.println(" The result is: ");
print(hashMap, 0, 0);// Outputs the sequence at the end of the sort
hashMap.clear();// empty
System.out.print("1 A total of the "+contrastCount+" comparative \t");
System.out.print("1 A total of the "+swapCount+" swaps \t");
System.out.println(" Execution time is "+(end-start)+" ms ");
System.out.println("( Note: This output sequence is a sequence of code execution, I'm going to recurse on the left hand side again The right-hand side recursively, The recursive sequences in textbooks are often left and right at the same time, for the record )");
}
/**
* Initialization function
* @param hashMap
*/
private static void init(HashMap<integer, integer=""> hashMap) {
hashMap.put(0, null);// The first 1 Place empty
hashMap.put(1, 10);
hashMap.put(2, 5);
hashMap.put(3, 11);
hashMap.put(4, 12);
hashMap.put(5, 13);
hashMap.put(6, 4);
hashMap.put(7, 1);
hashMap.put(8, 5);
hashMap.put(9, 8);
hashMap.put(10, 6);
hashMap.put(11, 4);
hashMap.put(12, 8);
}
/**
* Do quick sort
* @param hashMap The table to be sorted
* @param low
* @param high
*/
static int count = 1;
private static void quick(HashMap<integer, integer=""> hashMap, int low, int high){
if(low<high){ hashmap="" high="" int="" integer="" k="quickOnePass(hashMap," low="" param="" private="" static=""> hashMap, int low, int high){
hashMap.put(0, hashMap.get(low));// choose 1 A boundary value At this time the first low Values in bit elements are no longer overwritten
swapCount++;// happen 1 swaps
while(low<high){ high="">hashMap.get(low)){// Start walking from left to right Until you have the wrong data or The end of the
low++;
contrastCount++;// happen 1 comparative
}
if(low<high){ hashmap="" integer="" j="" k="" param="" private="" return="" static="" void=""> hashMap, int j, int k){
if(j != 0)
System.out.print(" The first "+j+" Trip: ( Dividing line for "+k+")\t");
for(int i=1; i<hashmap.size(); code=""></hashmap.size();></high){></high){></high){></integer,></integer,></integer,integer></integer,integer></code></code></code>Direct selection sort
<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap;
public class SelectionSort {
private static int contrastCount = 0;// Compare the number of
private static int swapCount = 0;// Switching frequency
public static void main(String[] args) {
System.out.println(" Selection sort: \n Each time, select the smallest, and swap with the element at the corresponding location , Time complexity O(n^2), Space complexity O(1) Unstable sort ");
HashMap<integer,integer> hashMap = new HashMap<integer,integer>();
init(hashMap);// Initialize the
System.out.println(" The initial sequence is: ");
print(hashMap, 0, 0);// print
select(hashMap);// The sorting
}
/**
* Initialization function
* @param hashMap
*/
private static void init(HashMap<integer, integer=""> hashMap) {
hashMap.put(0, null);// The first 1 Place empty
hashMap.put(1, 10);
hashMap.put(2, 5);
hashMap.put(3, 11);
hashMap.put(4, 12);
hashMap.put(5, 13);
hashMap.put(6, 4);
hashMap.put(7, 1);
hashMap.put(8, 5);
hashMap.put(9, 8);
hashMap.put(10, 6);
hashMap.put(11, 4);
hashMap.put(12, 8);
}
/**
* Sort by selection
* @param hashMap The table to be sorted
*/
private static void select(HashMap<integer, integer=""> hashMap){
System.out.println(" Start sorting by selection: ");
// Sorting start time
long start = System.currentTimeMillis();
int count = 1;// Only count execution times
for(int i=hashMap.size()-1; i>1; i--){// The number of times you need to loop the query The last 1 I don't have to worry about the elements
int k = i;// Record the subscript of the maximum value of the search sequence The initial position is where the number should be placed
for(int j=1; j<i; code="" i="1;" int="" j=""></i;></integer,></integer,></integer,integer></integer,integer></code></code></code></code>Heap sort
<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap;
public class HeapSort {
private static int contrastCount = 0;// Compare the number of
private static int swapCount = 0;// Switching frequency
private static int printCount = 1;// Number of printings performed
public static void main(String[] args) {
System.out.println(" Heap sort: \n First of all to establish 1 A heap (by first arranging the sequences 2 Tree, then from the bottom up, from right to left so that each 1 The parent node in the child tree is larger than the child node, and then records piled into the sequence from top to bottom, left to right.) ,"
+ "\n Then take the root and bottom of the heap The child node swap, collate the heap, and then repeatedly swap, collate, time complexity O(nlgn), Space complexity O(1) Unstable sort ");
HashMap<integer,integer> hashMap = new HashMap<integer,integer>();
init(hashMap);// Initialize the
System.out.println(" The initial sequence is: ");
print(hashMap, 0);// print
heap(hashMap);// The sorting
}
/**
* Initialization function
* @param hashMap
*/
private static void init(HashMap<integer, integer=""> hashMap) {
hashMap.put(0, null);// The first 1 Place empty
hashMap.put(1, 10);
hashMap.put(2, 5);
hashMap.put(3, 11);
hashMap.put(4, 12);
hashMap.put(5, 13);
hashMap.put(6, 4);
hashMap.put(7, 1);
hashMap.put(8, 5);
hashMap.put(9, 8);
hashMap.put(10, 6);
hashMap.put(11, 4);
hashMap.put(12, 8);
}
/**
* Heap sort
* @param hashMap The table to be sorted
*/
private static void heap(HashMap<integer, integer=""> hashMap){
System.out.println(" Start building a heap: ");
// Sorting start time 87
long start = System.currentTimeMillis();
for(int i=(hashMap.size()-1)/2; i>=1; i--){// Start building heap
sift(hashMap, i, hashMap.size()-1);// All the nodes should be in good position
}
System.out.println(" Built and successfully ");
for(int j=hashMap.size()-1; j>=1; j--){// Put the number one every time 1 The element and the last 1 An unsorted swap Then adjust the regulation 1 One node is enough
hashMap.put(0, hashMap.get(1));
hashMap.put(1, hashMap.get(j));
hashMap.put(j, hashMap.get(0));
sift(hashMap, 1, j-1);// The place that's left to sort is j-1
swapCount++;// happen 1 swaps
swapCount++;// happen 1 swaps
swapCount++;// happen 1 swaps
}
// End of sorting time
long end = System.currentTimeMillis();
System.out.println(" The result is: ");
print(hashMap, 0);// Outputs the sequence at the end of the sort
hashMap.clear();// empty
System.out.print("1 A total of the "+contrastCount+" comparative \t");
System.out.print("1 A total of the "+swapCount+" swaps \t");
System.out.println(" Execution time is "+(end-start)+" ms ");
}
/**
* The first i Bit elements are moved to the appropriate position Compared to the maximum value of its children If there is an exchange Continue the comparison
* @param hashMap
* @param i The index of the number to be moved
* @param n Represents the scope to look for from 1 to n a
*/
private static void sift(HashMap<integer, integer=""> hashMap, int i, int n){
int j = 2*i;//j for i The left child
hashMap.put(0, hashMap.get(i));// The number currently to be sorted
while(j<=n){// If there are left children
if(hashMap.containsKey(j+1) && hashMap.get(j)<hashmap.get(j+1)){ else="" hashmap="" i="j;// Transfer root node subscript " integer="" j="" param="" private="" static="" void=""> hashMap, int j){
if(j != 0)
System.out.print(" The first "+j+" Trip: \t");
for(int i=1; i<hashmap.size(); code=""></hashmap.size();></hashmap.get(j+1)){></integer,></integer,></integer,></integer,integer></integer,integer></code></code></code></code></code>Merge sort
<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">import java.util.HashMap;
public class MergeSort {
private static int contrastCount = 0;// Compare the number of
private static int swapCount = 0;// Switching frequency
private static int printCount = 1;// Only count execution times
public static void main(String[] args) {
System.out.println(" Merge sort: \n So let's break down the data n Group, and then no two groups start merging, adjacent two merge as 1 New ordered queues, and repeat the merge until the whole queue is ordered , Time complexity O(nlgn), Space complexity O(n) , stable sorting ");
HashMap<integer,integer> hashMap = new HashMap<integer,integer>();// unsorted
HashMap<integer,integer> hashMapNew = new HashMap<integer,integer>();// sorted
hashMapNew.put(0, null);// The first 1 Place empty
init(hashMap);// Initialize the
System.out.println(" The initial sequence is: ");
print(hashMap, 0);// print
System.out.println(" Starting merge sort: ");
// Sorting start time
long start = System.currentTimeMillis();
merge(hashMap, hashMapNew, 1, hashMap.size()-1);// The sorting
// End of sorting time
long end = System.currentTimeMillis();
System.out.println(" The result is: ");
print(hashMapNew, 0);// Outputs the sequence at the end of the sort
hashMap.clear();// empty
System.out.print("1 A total of the "+contrastCount+" comparative \t");
System.out.print("1 A total of the "+swapCount+" swaps \t");
System.out.println(" Execution time is "+(end-start)+" ms ");
System.out.println("( Note: This output sequence is a sequence of code execution, I'm going to recurse on the left hand side again The right-hand side recursively, The recursive sequences in textbooks are often left and right at the same time, for the record )");
}
/**
* Initialization function
* @param hashMap
*/
private static void init(HashMap<integer, integer=""> hashMap) {
hashMap.put(0, null);// The first 1 Place empty
hashMap.put(1, 10);
hashMap.put(2, 5);
hashMap.put(3, 11);
hashMap.put(4, 12);
hashMap.put(5, 13);
hashMap.put(6, 4);
hashMap.put(7, 1);
hashMap.put(8, 5);
hashMap.put(9, 8);
hashMap.put(10, 6);
hashMap.put(11, 4);
hashMap.put(12, 8);
}
/**
* Merge sort
* @param hashMap The table to be sorted
* @param hashMapNew Sorted tables
*/
private static void merge(HashMap<integer, integer=""> hashMap, HashMap<integer, integer=""> hashMapNew, int low, int high){
if(low == high){
hashMapNew.put(low, hashMap.get(low));
swapCount++;// happen 1 swaps
}else{
int meddle = (int)((low+high)/2);// Will this 1 The median of the mean of a sequence number
merge(hashMap, hashMapNew, low, meddle);// Continue recursion on the left hand side of the sequence
merge(hashMap, hashMapNew, meddle+1, high);// Recurse the sequence on the right
mergeSort(hashMap, hashMapNew, low, meddle, high);// Combine adjacent sequences
for(int i=low; i<=high; i++){// Will already be sorted hashMapNew 【 low . high 】 covered hashMap 【 low . high In order to enter 1 Submerge recursively
hashMap.put(i, hashMapNew.get(i));
swapCount++;// happen 1 swaps
}
}
}
/**
* Merge sort The 【 low . meddle "And" meddle+1 . high And for 1 An orderly hashMapNew 【 low,high 】
* @param hashMap The table to be sorted
* @param hashMapNew Sorted tables
* @param low low
* @param meddle The median
* @param high high
*/
private static void mergeSort(HashMap<integer, integer=""> hashMap, HashMap<integer, integer=""> hashMapNew, int low, int meddle, int high){
int k = low;
int j = meddle+1;
while(low<=meddle && j<=high){// The two sequences are combined 1 A sequence of The order of arrival from childhood
if(hashMap.get(low) < hashMap.get(j)){
hashMapNew.put(k++, hashMap.get(low++));// Put it in place
}else{
hashMapNew.put(k++, hashMap.get(j++));// Put it in place
}
contrastCount++;// happen 1 comparative
swapCount++;// happen 1 swaps
}
// If you have 1 There are too many squares Then assign the value directly
while(low<=meddle){
hashMapNew.put(k++, hashMap.get(low++));// Put it in place
swapCount++;// happen 1 swaps
}
while(j<=high){
hashMapNew.put(k++, hashMap.get(j++));// Put it in place
swapCount++;// happen 1 swaps
}
print(hashMapNew, printCount++);
}
/**
* Prints the sorted elements
* @param hashMap Sorted tables
* @param j The first j Trip to sort
*/
private static void print(HashMap<integer, integer=""> hashMap, int j){
if(j != 0)
System.out.print(" The first "+j+" Trip: \t");
for(int i=1; i<hashmap.size(); code=""></hashmap.size();></integer,></integer,></integer,></integer,></integer,></integer,></integer,integer></integer,integer></integer,integer></integer,integer></code></code></code></code></code></code>Least-significant cardinality sort
<code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs "><code class="language-java hljs ">/**
* Least-significant cardinality sort
* @author HHF
*
*/
public class LSDSort {
private static int contrastCount = 0;// Compare the number of
private static int swapCount = 0;// Switching frequency
private static int printCount = 1;// Only count execution times
public static void main(String[] args) {
System.out.println(" Lowest priority radix sort: \n According to the bits, 10 Bit, hundreds sort, you don't have to compare, you just have to take the remainder of the logarithm and save it to the subscript 2 Dimension array, and then read in turn, each 1 The base system repeats in sequence , Time complexity O(d ( n+rd ) ), Space complexity O(n+rd) , stable sorting ");
int[] data = { 173, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100 };
System.out.println(" The initial sequence is: ");
print(data, 0);// print
LSD(data, 3);
}
public static void LSD(int[] number, int d) {// d How many bits are there in the largest number
int k = 0;//number The small scale
int n = 1;// When comparing 10 When a n=10 When you compare the hundreds place n=100 I'm going to lower the high to get the remainder
int m = 1;// Are comparing number The last digit of the data
int[][] temp = new int[10][number.length];// The first of an array of 1 The dimension represents the possible remainder 0-9 2 Dimensions, in turn, record the same number of the remainder
int[] order = new int[10];// An array of orderp[i] The remainder used to represent the bit is i The number of Numbers
// Sorting start time
long start = System.currentTimeMillis();
while (m <= d) {//d=5 Is more 5 time
for (int i = 0; i < number.length; i++) {// the number The remainder of the number inserted into temp in
int lsd = ((number[i] / n) % 10);// Find the remainder of the number
temp[lsd][order[lsd]] = number[i];// Save to the appropriate place
order[lsd]++;// This remainder has several Numbers
swapCount++;// happen 1 swaps
}
for (int i = 0; i < 10; i++) {// will temp The data is extracted sequentially
if (order[i] != 0)// If the remainder has no data, no consideration is required
for (int j = 0; j < order[i]; j++) {// A number that has a remainder 1 How many are there
number[k] = temp[i][j];//11 The assignment
k++;
swapCount++;// happen 1 swaps
}
order[i] = 0;// Set it to zero so we can go down 1 Time to use
}
n *= 10;// Into the system +1 Go forward
k = 0;// From the very beginning
m++;// Into the system +1
print(number, printCount++);
}
// End of sorting time
long end = System.currentTimeMillis();
System.out.println(" The result is: ");
print(number, 0);// Outputs the sequence at the end of the sort
System.out.print("1 A total of the "+contrastCount+" comparative \t");
System.out.print("1 A total of the "+swapCount+" swaps \t");
System.out.println(" Execution time is "+(end-start)+" ms ");
}
/**
* Prints the sorted elements
* @param data Sorted tables
* @param j The first j Trip to sort
*/
private static void print(int[] data, int j){
if(j != 0)
System.out.print(" The first "+j+" Trip: \t");
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
} </code></code></code></code></code></code></code>I hope this article has helped you