# Data structure and sorting algorithm

2020-11-07 21:19:25 Long Tao

Sorting algorithm ：

1. Internal sorting ： It refers to loading all the data to be processed into internal memory for sorting

2. 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

3. 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 ：

1. A total of n-1 A large cycle （ Array has n Elements ）
2. The elements of each sort are gradually decreasing
3. 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 ：

1. from arr[0]--arr[n-1] Find the smallest number in , Then exchange arr[0] Swap positions with the minimum
2. from arr[1]--arr[n-1] Find the smallest number in , Then exchange arr[1] Swap positions with the minimum
3. ........
4. 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 ：

1. When inserting an ordered sequence, we use Exchange method
2. 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 ：

1. Let's say the array is arr, On the left left, The right side is right, Set the initial position of the selection to
2. 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
3. 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 ：

1. First, the array is divided into two parts , Split until there is only one element in each subarray
2. Then merge the same adjacent split parts , Merge in order , Until it's merged into a complete array
3. 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;
}
``````

1. 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
2. Cardinal sort belongs to stable sort , Cardinality sorting is a stable sorting method with high efficiency
3. Cardinal sort is Bucket sort Development of
4. 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 ：

1. Define a two-dimensional array , Express 10 A barrel , Every bucket is a one-dimensional array
2. In order to prevent data overflow when putting in input , Then every one-dimensional array （ bucket ）, Size to arr.length
3. Cardinal sort is a classical algorithm that uses space for time .
`````` /**
* @param arr
* @return
*/
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;
}
``````