Ten examples of JAVA sorting algorithms
- 2020-04-01 02:26:04
- OfStack
There are many sorting algorithms, so which one to use in a particular situation is important. To select the appropriate algorithm, consider the following criteria in the recommended order:
(1) execution time
(2) storage space
(3) programming work
For the case with a small amount of data, (1) (2) there is no big difference, and the main consideration is (3). For large data volume, (1) is the primary.
Bubble sort
Efficiency O (n²) , for sorting small lists.
Second, selection sort
Efficiency O (n²) , for sorting small lists.
Insert sort
O (n); Worst efficiency O (n²) Same as bubbling and selection, for sorting small lists
If the list is basically in order, insertion sort is more efficient than bubbling and selection.
For sorting small lists.
The efficiency estimates range from O (nlog2^n) to O (n^1.5), depending on the initial size of the increment. It is recommended to use the prime as the increment, because if the increment is a power of two, the same element is compared again in the next channel.
Shell sort improves insertion sort and reduces the number of comparisons. It's an unstable sort because the elements might jump back and forth during the sort process.
Efficiency O (nlogn), there is no difference between the best, average, and worst use case efficiency of merge.
For sorting large lists, based on divide and conquer.
O (nlogn), for sorting large lists.
The total time of this algorithm depends on the location of hub value. Selecting the first element as the hub may result in O (n²) Worst use case efficiency. If the number is basically in order, the efficiency is the worst. The middle of the options is the hub, and the efficiency is O (nlogn).
Based on divide and conquer.
Heap sort
Maximum heap: the keyword of any of the latter non-terminal nodes is greater than or equal to the keyword of its left and right children, and the node at the top of the heap has the largest keyword in the entire sequence.
Thought:
(1) set I =l, and set temp = kl;
(2) calculate the left child j of I =2i+1;
(3) if j< = n-1, then rotate (4), otherwise rotate (6);
(4) compare kj and kj+1, if kj+1> Kj, then let j = j+1, otherwise j is unchanged;
(5) compare temp and kj, if kj> Temp, then make ki equal to kj, and make I =j,j=2i+1, and rotate (3), otherwise rotate (6).
(6) let ki equal temp, end.
The heap sort time consists mainly of the overhead of building the initial heap and repeatedly rebuilding the heap, both of which are implemented by calling Heapify.
The worst time complexity of heap sort is O(NLGN). The average performance of heap sort is close to the worst. Because of the number of comparisons required to build the initial heap, heap sort is not suitable for files with fewer records. Heap sort is sort in place, auxiliary space O(1), It's an unstable sorting method.
Differences between heap sort and direct insertion sort:
In the direct selection sort, in order to select the record with the smallest keyword from R[1..n], n-1 comparisons must be made, and then n-2 comparisons must be made to select the record with the smallest keyword from R[2..n]. In fact, many of the later n-2 comparisons may have been done in the previous n-1 comparison, but because the comparison results were not preserved in the previous sort, the comparison was repeated in the next sort.
Heap sort can save some comparison results by tree structure, which can reduce the number of comparisons.
Eight, topological sort
Example: students' elective course arrangement sequence
Topological ordering: the process of arranging the vertices of a directed graph into a linear sequence in terms of their priority to each other.
Methods:
Select a vertex in a directed graph without a precursor and output
Delete the vertex and all arcs ending with it from the graph
Repeat these two steps until all the vertices have been output (topological sort is successful), or until there are no precursors in the graph (there are loops in the graph).
The time complexity of the algorithm is O (n+e).
Ix. Ranking of tournaments
The algorithm of tournament ranking is similar to that of sports.
Firstly, n data elements are divided into two groups and compared by keyword, so as to get the winner of n / 2 comparisons (the keyword is small), which is retained as the result of the first step comparison.
Then the n / 2 data elements are grouped in pairs and compared by keyword... , until the smallest data element of a keyword is selected.
X. radix sort
Radix sort is also known as bucket sort. Radix sort is markedly different from the sorting methods described earlier.
The sorting method introduced above is based on the comparison of data element keywords, so it can be called comparison based sorting;
Radix sort first "allocates" the data elements to be sorted to different buckets, and then "collects" the data elements from each bucket.
Radix sort enables sorting of multiple keywords by using this "allocate" and "collect" method of sorting multiple keywords.
Ex. :
Each card has two "keywords" : suit and face value. Its size order is:
Color: § < "< © The < & ordf;
Face value: 2 < 3 <...... < K < A
The size of playing CARDS according to the suit first comparison, the suit of the card is bigger than the suit of the card is bigger; CARDS of the same suit are then compared according to their face value. Therefore, the following sequence can be obtained if the playing CARDS are arranged from small to large:
§ 2,... § A, "2... , ¨ A, & copy; 2,... , & copy; A, & ordf; 2,... , & ordf; a.
This sort is equivalent to a sort with two keywords, and is generally implemented in two ways.
A: can be divided into four piles by suit (each pile of CARDS has the same suit), and then in each pile of CARDS according to the face value from small to large order order, and finally has sorted the four piles of CARDS according to suit from small to large order stack together to get the sorting result.
Second: to sort by value is divided into 13 heap (each pile of CARDS with the same face value), then the 13 heap at par stacked together, since the childhood order again the whole deck of CARDS in sequence according to the design and color is subdivided into four heap (each pile of card is according to the order of the face value since the childhood), finally will be the four pile card according to the design and color is growing up together to get the results sorted.
Implementation method:
Most Significant Digit first method (MSD method for short) : sort and group by k1 first, record in the same group, key code k1 is equal, then sort and group by k2 into subgroups, and then continue to sort and group the following key code until the sub-group is sorted by the Most Significant key code kd. Connect the groups and you get an ordered sequence.
The Least Significant Digit first method (LSD method for short) : first sort from kd, then sort from kd-1, repeat in turn, until k1 sort, then an ordered sequence is obtained.
Radix sort is a sort of stability, its time complexity is O (nlog(r)m), where r is the cardinality taken, and m is the number of heap, in some cases, the efficiency of radix sort is higher than other comparative sort.
(1) execution time
(2) storage space
(3) programming work
For the case with a small amount of data, (1) (2) there is no big difference, and the main consideration is (3). For large data volume, (1) is the primary.
Bubble sort
void BubbleSortArray()
{
for(int i=1;i<n;i++)
{
for(int j=0;i<n-i;j++)
{
if(a[j]>a[j+1])//Compare swapping adjacent elements
{
int temp;
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
}
}
}
}
Efficiency O (n²) , for sorting small lists.
Second, selection sort
void SelectSortArray()
{
int min_index;
for(int i=0;i<n-1;i++)
{
min_index=i;
for(int j=i+1;j<n;j++)//Select the smallest item per scan
if(arr[j]<arr[min_index]) min_index=j;
if(min_index!=i)//Find the smallest item swap to move the item to the correct position in the list
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
Efficiency O (n²) , for sorting small lists.
Insert sort
void InsertSortArray()
{
for(int i=1;i<n;i++)//The loop starts with the second array element because arr[0] is the original sorted part
{
int temp=arr[i];//Temp is marked as the first unsorted element
int j=i-1;
while (j>=0 && arr[j]>temp)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
}
O (n); Worst efficiency O (n²) Same as bubbling and selection, for sorting small lists
If the list is basically in order, insertion sort is more efficient than bubbling and selection.
void ShellSortArray()
{
for(int incr=3;incr<0;incr--)//Increment decrement, take increment 3,2,1
{
for(int L=0;L<(n-1)/incr;L++)//Each sublist divided by repetition
{
for(int i=L+incr;i<n;i+=incr)//Apply insertion sort to each sublist
{
int temp=arr[i];
int j=i-incr;
while(j>=0&&arr[j]>temp)
{
arr[j+incr]=arr[j];
j-=incr;
}
arr[j+incr]=temp;
}
}
}
}
For sorting small lists.
The efficiency estimates range from O (nlog2^n) to O (n^1.5), depending on the initial size of the increment. It is recommended to use the prime as the increment, because if the increment is a power of two, the same element is compared again in the next channel.
Shell sort improves insertion sort and reduces the number of comparisons. It's an unstable sort because the elements might jump back and forth during the sort process.
void MergeSort(int low,int high)
{
if(low>=high) return;//Stop when there is one element left in each sublist
else int mid=(low+high)/2;
MergeSort(low,mid);//The sublist is further divided
MergeSort(mid+1,high);
int [] B=new int [high-low+1];//Create a new array to hold the merged elements
for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)
{
if (arr[i]<=arr[j];)
{
B[k]=arr[i];
I++;
}
else
{ B[k]=arr[j]; j++; }
}
for( ;j<=high;j++,k++)//If there are still elements in the second sublist, append to the new list
B[k]=arr[j];
for( ;i<=mid;i++,k++)//If there is still an element in the first sublist, append to the new list
B[k]=arr[i];
for(int z=0;z<high-low+1;z++)//Copies all the elements of the sorted array B into the original array arr
arr[z]=B[z];
}
Efficiency O (nlogn), there is no difference between the best, average, and worst use case efficiency of merge.
For sorting large lists, based on divide and conquer.
void swap(int a,int b){int t;t =a ;a =b ;b =t ;}
int Partition(int [] arr,int low,int high)
{
int pivot=arr[low];//The first element of a subsequence is used as the pivot element
while (low < high)
{
//Look for the first element smaller than the pivot element in the back half
while (low < high && arr[high] >= pivot)
{
--high;
}
//Swap this element, which is smaller than the pivot element, into the front half
swap(arr[low], arr[high]);
//Look for the first element in the first half that is larger than the pivot element
while (low <high &&arr [low ]<=pivot )
{
++low ;
}
swap (arr [low ],arr [high ]);//Swap the larger elements of this pivot element into the second half
}
return low ;//Returns the location of the hub element
}
void QuickSort(int [] a,int low,int high)
{
if (low <high )
{
int n=Partition (a ,low ,high );
QuickSort (a ,low ,n );
QuickSort (a ,n +1,high );
}
}
O (nlogn), for sorting large lists.
The total time of this algorithm depends on the location of hub value. Selecting the first element as the hub may result in O (n²) Worst use case efficiency. If the number is basically in order, the efficiency is the worst. The middle of the options is the hub, and the efficiency is O (nlogn).
Based on divide and conquer.
Heap sort
Maximum heap: the keyword of any of the latter non-terminal nodes is greater than or equal to the keyword of its left and right children, and the node at the top of the heap has the largest keyword in the entire sequence.
Thought:
(1) set I =l, and set temp = kl;
(2) calculate the left child j of I =2i+1;
(3) if j< = n-1, then rotate (4), otherwise rotate (6);
(4) compare kj and kj+1, if kj+1> Kj, then let j = j+1, otherwise j is unchanged;
(5) compare temp and kj, if kj> Temp, then make ki equal to kj, and make I =j,j=2i+1, and rotate (3), otherwise rotate (6).
(6) let ki equal temp, end.
void HeapSort(SeqIAst R)
{
//For R[1..n] heap sort, R[0] may be used as the temporary CD element & PI;
int I; BuildHeap(R) ;
// will R[1-n] Built up initial reactor for(i=n;i>1 ; i--) // For the current unordered region R[1..i] Sort the heap and do it together n-1 Visit.
{
R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; // Swap the top of the heap with the last record in the heap Heapify(R,1,i-1); // will R[1..i-1] Readjust to heap, only R[1] Possible violation of heap properties
}
}
The heap sort time consists mainly of the overhead of building the initial heap and repeatedly rebuilding the heap, both of which are implemented by calling Heapify.
The worst time complexity of heap sort is O(NLGN). The average performance of heap sort is close to the worst. Because of the number of comparisons required to build the initial heap, heap sort is not suitable for files with fewer records. Heap sort is sort in place, auxiliary space O(1), It's an unstable sorting method.
Differences between heap sort and direct insertion sort:
In the direct selection sort, in order to select the record with the smallest keyword from R[1..n], n-1 comparisons must be made, and then n-2 comparisons must be made to select the record with the smallest keyword from R[2..n]. In fact, many of the later n-2 comparisons may have been done in the previous n-1 comparison, but because the comparison results were not preserved in the previous sort, the comparison was repeated in the next sort.
Heap sort can save some comparison results by tree structure, which can reduce the number of comparisons.
Eight, topological sort
Example: students' elective course arrangement sequence
Topological ordering: the process of arranging the vertices of a directed graph into a linear sequence in terms of their priority to each other.
Methods:
Select a vertex in a directed graph without a precursor and output
Delete the vertex and all arcs ending with it from the graph
Repeat these two steps until all the vertices have been output (topological sort is successful), or until there are no precursors in the graph (there are loops in the graph).
void TopologicalSort()
{
int indegree[M];
int i,k,j;
char n;
int count=0;
Stack thestack;
FindInDegree(G,indegree);//Enter each vertex in indegree[0... num]
InitStack(thestack);//Initialize the stack
for(i=0;i<G.num;i++)
Console.WriteLine(" node "+G.vertices[i].data+" For in degrees "+indegree[i]);
for(i=0;i<G.num;i++)
{
if(indegree[i]==0)
Push(thestack.vertices[i]);
}
Console.Write(" The output order of topological sort is: ");
while(thestack.Peek()!=null)
{
Pop(thestack.Peek());
j=locatevex(G,n);
if (j==-2)
{
Console.WriteLine(" An error occurred and the program ends. ");
exit();
}
Console.Write(G.vertices[j].data);
count++;
for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)
{
k=p.adjvex;
if (!(--indegree[k]))
Push(G.vertices[k]);
}
}
if (count<G.num)
Cosole.WriteLine(" The graph has a ring, an error occurred, unable to sort. ");
else
Console.WriteLine(" Sorted successfully. ");
}
The time complexity of the algorithm is O (n+e).
Ix. Ranking of tournaments
The algorithm of tournament ranking is similar to that of sports.
Firstly, n data elements are divided into two groups and compared by keyword, so as to get the winner of n / 2 comparisons (the keyword is small), which is retained as the result of the first step comparison.
Then the n / 2 data elements are grouped in pairs and compared by keyword... , until the smallest data element of a keyword is selected.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define SIZE 100000
#define MAX 1000000
struct node
{
long num;//The keyword
char str[10];
int lastwin;//The last one to win
int killer;//A defeated opponent
long times;//Number of games
}data[SIZE];
long CompareNum=0;
long ExchangeNum=0;
long Read(char name[])//Read the data in file a.txt and store it in the array data[]; Finally, the number of data is returned
{
FILE *fp;
long i=1;
fp=fopen(name,"rw");
fscanf(fp,"%d%s",&data[i].num,data[i].str);
while(!feof(fp))
{
i++;
fscanf(fp,"%d%s",&data[i].num,data[i].str);
}
return (i-1);
}
long Create(long num)//Creates a winner tree that returns the index of the champion (the smallest number) in the array data[]
{
int i,j1,j2,max,time=1;
long min;//Records the index of the current champion
for(i=1;pow(2,i-1)<num;i++)
max=pow(2,i-1);//Find the number of leaves
for(i=1;i<=max;i++)//Initializes the leaf node
{
data[i].killer=0;
data[i].lastwin=0;
data[i].times=0;
if(i>num)
data[i].num=MAX;
}
for(i=1;i<=max;i+=2)//First round
{
++CompareNum;
if(data[i].num <= data[i+1].num)
{
data[i].lastwin = i+1;
data[i+1].killer=i;
++data[i].times;
++data[i+1].times;
min=i;
}
else
{
data[i+1].lastwin=i;
data[i].killer=i+1;
++data[i].times;
++data[i+1].times;
min=i+1;
}
}
j1=j2=0;//Record the index of two consecutive uneliminated contestants
while(time <= (log(max)/log(2)))//Elimination matches will be held
{
for(i=1;i<=max;i++)
{
if(data[i].times==time && data[i].killer==0)//Find a contestant
{
j2=i;//The default is the later of the two players
if(j1==0)//If the first position is empty, the new player comes first
j1=j2;
else//Otherwise, the new players are the later ones, so the players have arrived to start the game
{
++CompareNum;
if(data[j1].num <= data[j2].num)//The first runner wins
{
data[j1].lastwin = j2;//The winner is j2
data[j2].killer=j1;//J2 was eliminated by j1
++data[j1].times;
++data[j2].times;//Each player adds 1& NBSP;
min=j1;//The minimum number is j1
j1=j2=0;//I'm going to set j1, j2 to 0
}
else//In the same way
{
data[j2].lastwin=j1;
data[j1].killer=j2;
++data[j1].times;
++data[j2].times;
min=j2;
j1=j2=0;
}
}
}
}
time++;//Round number 1
}
return min;//Returns the index of the champion
}
void TournamentSort(long num)//Tournament sorting
{
long tag=Create(num);//Returns the minimum index
FILE *fp1;
fp1=fopen("sort.txt","w+");//Create and open the file sort.txt for write
while(data[tag].num != MAX)//When the minimum is not infinite
{
printf("%d %sn",data[tag].num,data[tag].str);//The output data
fprintf(fp1,"%d %sn",data[tag].num,data[tag].str);//Write data
data[tag].num=MAX;//Replaces the current champion with infinity
tag=Create(num);//Returns the index & NBSP; of the next champion;
}
}
int main()
{
int num;
char name[10];
printf("Input name of the file:");
gets(name);
num=Read(name);//Read the file
TournamentSort(num);//Tournament sorting
printf("CompareNum=%dnExchangeNum=%dn",CompareNum,ExchangeNum);
return 0;
}
X. radix sort
Radix sort is also known as bucket sort. Radix sort is markedly different from the sorting methods described earlier.
The sorting method introduced above is based on the comparison of data element keywords, so it can be called comparison based sorting;
Radix sort first "allocates" the data elements to be sorted to different buckets, and then "collects" the data elements from each bucket.
Radix sort enables sorting of multiple keywords by using this "allocate" and "collect" method of sorting multiple keywords.
Ex. :
Each card has two "keywords" : suit and face value. Its size order is:
Color: § < "< © The < & ordf;
Face value: 2 < 3 <...... < K < A
The size of playing CARDS according to the suit first comparison, the suit of the card is bigger than the suit of the card is bigger; CARDS of the same suit are then compared according to their face value. Therefore, the following sequence can be obtained if the playing CARDS are arranged from small to large:
§ 2,... § A, "2... , ¨ A, & copy; 2,... , & copy; A, & ordf; 2,... , & ordf; a.
This sort is equivalent to a sort with two keywords, and is generally implemented in two ways.
A: can be divided into four piles by suit (each pile of CARDS has the same suit), and then in each pile of CARDS according to the face value from small to large order order, and finally has sorted the four piles of CARDS according to suit from small to large order stack together to get the sorting result.
Second: to sort by value is divided into 13 heap (each pile of CARDS with the same face value), then the 13 heap at par stacked together, since the childhood order again the whole deck of CARDS in sequence according to the design and color is subdivided into four heap (each pile of card is according to the order of the face value since the childhood), finally will be the four pile card according to the design and color is growing up together to get the results sorted.
Implementation method:
Most Significant Digit first method (MSD method for short) : sort and group by k1 first, record in the same group, key code k1 is equal, then sort and group by k2 into subgroups, and then continue to sort and group the following key code until the sub-group is sorted by the Most Significant key code kd. Connect the groups and you get an ordered sequence.
The Least Significant Digit first method (LSD method for short) : first sort from kd, then sort from kd-1, repeat in turn, until k1 sort, then an ordered sequence is obtained.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LearnSort
{
class Program
{
static void Main(string[] args)
{
int[] arr = CreateRandomArray(10);//Generate random Numbers
Print(arr);//The output array
RadixSort(ref arr);//The sorting
Print(arr);//Output sorted results
Console.ReadKey();
}
public static void RadixSort(ref int[] arr)
{
int iMaxLength = GetMaxLength(arr);
RadixSort(ref arr, iMaxLength);
}
private static void RadixSort(ref int[] arr, int iMaxLength)
{
List<int> list = new List<int>();//Store each sorted element
List<int>[] listArr = new List<int>[10];//Ten barrels
char currnetChar;//Holds the current character such as 2 in an element 123
string currentItem;//To hold the current element let's say an element 123
for (int i = 0; i < listArr.Length; i++)//Initialize the memory allocation for ten buckets.
listArr[i] = new List<int>();
for (int i = 0; i < iMaxLength; i++)//Execute iMaxLength a total of times. IMaxLength is the maximum number of bits of the element.
{
foreach (int number in arr)//Points barrels
{
currentItem = number.ToString();//Converts the current element to a string
try { currnetChar = currentItem[currentItem.Length-i-1]; }// We start in the ones place and go up Points barrels
catch { listArr[0].Add(number); continue; }//If an exception occurs, press the number into listArr[0]. For example, if 5 has no ten digits, the above operation will definitely result in an out-of-bounds exception, which is exactly the expected behavior. We think that the ten digit of 5 is 0, so we press it into the bucket of listArr[0].
switch (currnetChar)//From the value of currnetChar, determine which bucket it is pressed into.
{
case '0': listArr[0].Add(number); break;
case '1': listArr[1].Add(number); break;
case '2': listArr[2].Add(number); break;
case '3': listArr[3].Add(number); break;
case '4': listArr[4].Add(number); break;
case '5': listArr[5].Add(number); break;
case '6': listArr[6].Add(number); break;
case '7': listArr[7].Add(number); break;
case '8': listArr[8].Add(number); break;
case '9': listArr[9].Add(number); break;
default: throw new Exception("unknow error");
}
}
for (int j = 0; j < listArr.Length; j++)//Rearrange the data in ten buckets and press them into the list
foreach (int number in listArr[j].ToArray<int>())
{
list.Add(number);
listArr[j].Clear();//Empty each bucket
}
arr = list.ToArray<int>();//Arr points to the rearranged element
//Console.Write("{0} times:",i);
Print(arr);//Output the result of a permutation
list.Clear();//To empty the list
}
}
//I get the number of bits of the largest element
private static int GetMaxLength(int[] arr)
{
int iMaxNumber = Int32.MinValue;
foreach (int i in arr)//I'm going to get the maximum
{
if (i > iMaxNumber)
iMaxNumber = i;
}
return iMaxNumber.ToString().Length;//Isn't it a bit of an opportunism to get the largest number of elements...
}
//Output array element
public static void Print(int[] arr)
{
foreach (int i in arr)
System.Console.Write(i.ToString()+'t');
System.Console.WriteLine();
}
//Generate random Numbers. Random Numbers range from 0 to 1000. The parameter iLength refers to how many random Numbers are generated
public static int[] CreateRandomArray(int iLength)
{
int[] arr = new int[iLength];
Random random = new Random();
for (int i = 0; i < iLength; i++)
arr[i] = random.Next(0,1001);
return arr;
}
}
}
Radix sort is a sort of stability, its time complexity is O (nlog(r)m), where r is the cardinality taken, and m is the number of heap, in some cases, the efficiency of radix sort is higher than other comparative sort.