Sorting algorithm :
-
Internal sorting : It refers to loading all the data to be processed into internal memory for sorting
-
External sorting : When the amount of data is too large , Can't load all into memory , Sorting needs to be done with the help of external memory
-
Common algorithm classification :
5.1 Bubble sort
The basic idea : By treating sort Before and after ( Start with elements with small subscripts ), Compare the values of adjacent elements in turn , If it is found that the reverse order is found, it will be exchanged , Gradually move the higher value elements from the front to the back , It's like a start at the bottom of the water .
Summary rules :
- A total of n-1 A large cycle ( Array has n Elements )
- The elements of each sort are gradually decreasing
- If in the process of sorting , There was no exchange , It shows that the sorting has been completed
public static int[] bubbleSort(int[] arr) {
int temp = 0;
boolean flag = false;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j+1]){
flag = true;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(!flag){
break;
}else {
flag = false;
}
}
return arr;
}
5.2 Selection sort
Selection sort is also an internal sort , It is to select an element from the data to be sorted according to specified rules , Then according to the rules of exchange position to achieve the purpose of sorting .
The idea of sorting :
- from arr[0]--arr[n-1] Find the smallest number in , Then exchange arr[0] Swap positions with the minimum
- from arr[1]--arr[n-1] Find the smallest number in , Then exchange arr[1] Swap positions with the minimum
- ........
- Until all the data is exchanged
// Selection sort , Select the smallest element in the array with arr[0] swapping , Then continue to look for the next minimum and arr[1] In exchange for , Until all the data is sorted
public static int[] selectSort(int[] arr){
int temp = 0;
int index = 0;
for (int i = 0; i < arr.length-1; i++) {
index = i; // The index of the initial minimum value is i
for (int j = i+1; j < arr.length; j++) {
// If arr[j] Less than arr[index], be j Is the index of the minimum value
if(arr[j] < arr[index]){
index = j;
}
}
// Exchange the minimum and arr[i] The location of
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
return arr;
}
5.3 Insertion sort
Insertion sort belongs to internal sort method , It is to find the appropriate position of the element to be sorted by inserting .
Insert the idea of sorting : hold n Elements to be sorted Think of it as an ordered table and an unordered table , At first, the ordered table contains only one element , The unordered table contains n-1 Elements . In the process of sorting , Take the first element from the unordered table every time , Insert it in place in an ordered list , Make it a new ordered list .
Code implementation :
/**
* Insertion sort , Think of a list as an ordered table and an unordered table
* @param arr
* @return
*/
public static int[] insertSort(int[] arr){
int temp = 0;
int index = 0;
for (int i = 1; i < arr.length; i++) {
temp = arr[i];
index = i-1;
// Flashback judgment from i-1 To 0 Judge , If appear temp>arr[index], shows arr[index+1] The part to be inserted
while (index >= 0 && temp < arr[index]){
arr[index+1] = arr[index]; // Move the data in turn
index --;
}
// stay arr[index+1] Insert data
arr[index+1] = temp;
}
return arr;
}
5.4 Shell Sort ( Reduced delta sort )
The basic idea : Hill sort is to group records by a certain increment of subscript , Sort each group using the direct insertion sort algorithm ; As the increments decrease , Each group contains more and more keywords , When the increment is reduced to 1 when , The whole document is just a group , The algorithm terminates .
Step by step , Divide a certain amount of data into groups . Settings for each group The data increment is half of the last increment , Then increase the amount of data in each group , Array reduction , Until there's only one array left .
Hill sort method :
- When inserting an ordered sequence, we use Exchange method
- When inserting an ordered sequence, we use Mobile method
/**
* Hill exchange
* @param arr
* @return
*/
public static int[] shellSort(int[] arr){
int temp = 0;
int count = 0;
for(int gap = arr.length/2; gap > 0; gap /= 2){
for(int i=gap; i< arr.length; i++){
// Traverse all the data in the group ,gap Step length
for(int j=i-gap; j >= 0; j -= gap){
if(arr[j] > arr[j+gap]){
temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
}
return arr;
}
// Mobile location ( Combined with insertion sort )
public static int[] shellMoveSort(int[] arr){
for(int gap = arr.length/2; gap > 0; gap /= 2){
for(int i=gap; i < arr.length; i++){
int j = i;
int temp = arr[j];
if(arr[j] < arr[j-gap]){
while (j - gap >= 0 && temp < arr[j - gap]){
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
}
}
return arr;
}
5.5 Quick sort
The basic idea : Divide the data to be sorted into Two separate parts , All the data in one part is more than all the data in the other part All have to be small. , Then, the data distribution of the two parts is sorted in this way , The whole sorting part can be done recursively , So that the whole data becomes an ordered sequence .
Thought analysis :
- Let's say the array is arr, On the left left, The right side is right, Set the initial position of the selection to
- Find from left , Find greater than or equal to mid The value of , Start on the right side, too , Until we find less than or equal to mid Value
- Until I find
l<r
The location of , And then recursively do a quick sort .
/**
* Quick sort
*
* @param arr
* @param left
* @param right
* @return
*/
public static int[] quickSort(int[] arr, int left, int right) {
if (left >= right) return null;
// If the left And right Equal or left Greater than right, Then jump out of the program
int l = left;
int r = right;
int mid = arr[(l + r) / 2];
int temp = 0;
while (l < r) {
while (l < r && arr[l] < mid) {
l++;
}
while (r > l && arr[r] > mid) {
r--;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == mid){
r--;
}
if (arr[r] == mid) {
l++;
}
}
quickSort(arr, left, l - 1);
quickSort(arr, r + 1, right);
return arr;
}
5.6 Merge sort
Merge sort is a sort method realized by using the idea of merging , The algorithm uses the classic Divide and conquer strategy ( Divide and conquer will make the problem branch For some small problems and then recursively solve them , and Governance stage Then we will get the answers in different stages “ repair ” together , namely Divide and rule )
The basic method :
- First, the array is divided into two parts , Split until there is only one element in each subarray
- Then merge the same adjacent split parts , Merge in order , Until it's merged into a complete array
- It's best to do it recursively , The time complexity is
O(nlogn)
/**
* Merge sort
* @param arr
* @param left
* @param right
* @return
*/
public static int[] mergeSort(int[] arr, int left, int right){
// If left Greater than right, Only... In the array 1 Or no data , Then it will return empty directly
if(left >= right) return null;
int mid = (left + right)/2;
// Division
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
int i = left;
int j = mid+1;
int t = 0;
int[] temp = new int[(right - left + 1)];
while (i <= mid && j <= right){
if(arr[i] <= arr[j]){
temp[t] = arr[i];
t ++;
i ++;
}else {
temp[t] = arr[j];
t ++;
j ++;
}
}
// Fill in the rest with temp in
while (i <= mid){
temp[t] = arr[i];
t++;
i++;
}
// Put the rest right Fill in the content with temp in
while (j <= right){
temp[t] = arr[j];
t++;
j++;
}
// take temp Copy the data to arr in
for(int k=left; k<=right; k++){
arr[k] = temp[k-left];
}
System.out.println(" The sorted data is :" + Arrays.toString(temp));
return arr;
}
5.7 Radix sorting
- Cardinal sort belongs to “ Distributive sort ”, also called Barrel method , It is through the value of each bit of the key value , Assign the elements to be sorted to some “ bucket ” in , To achieve the function of sorting
- Cardinal sort belongs to stable sort , Cardinality sorting is a stable sorting method with high efficiency
- Cardinal sort is Bucket sort Development of
- The implementation of cardinality sort : Cut the whole number into different numbers according to the number of digits , And then compare... According to each bit .
Method of implementation :
- Define a two-dimensional array , Express 10 A barrel , Every bucket is a one-dimensional array
- In order to prevent data overflow when putting in input , Then every one-dimensional array ( bucket ), Size to arr.length
- Cardinal sort is a classical algorithm that uses space for time .
/**
* Radix sorting
* @param arr
* @return
*/
public static int[] radixSort(int[] arr){
int[][] bubble = new int[10][arr.length]; // Set the number of barrels , Each bucket holds the entire array at most
// Find the largest number in the array
int max = arr[0];
for(int i=1; i<arr.length; i++){
if(arr[i] > max){
max = arr[i];
}
}
int maxLength = (max + "").length();
// Determine how many cycles are required based on the number of digits of the largest data in the value
for (int i = 0; i < maxLength; i++) {
int[] bubbleLength = new int[10]; // The amount of data in the bucket
// Put the data according to bits 、 ten 、 Put the hundred in the bucket in turn
for (int j = 0; j < arr.length; j++) {
int size = arr[j] / (int)Math.pow(10, i) % 10;
bubble[size][bubbleLength[size]] = arr[j];
bubbleLength[size] ++;
}
// Take the data out in turn , And put it into the original array
int index = 0;
for(int j=0; j<bubble.length; j++){
if(bubbleLength[j] > 0){
for(int k=0; k<bubbleLength[j]; k++){
arr[index++] = bubble[j][k];
}
}
}
}
return arr;
}