©2020-2024 ioDraw All rights reserved
<> The importance of learning data structure
program ＝ data structure + algorithm , Algorithms are important , Data structure is also important , Only master the two , We are equal to master the ability to write programs , Is a qualified programmer .
<> Comparison of algorithm complexity
A summary on the Internet , This one needs to be memorized .
<> Key points of data structure ： Comparison of sorting algorithms
This is a summary when I study data structure ：
<> Why comprehensive comparison
See the figure below , This is an interview question of sorting algorithm （ requirement ： stable , fast ）, When I do this problem , According to what I summed up , The algorithm was quickly locked in , first , The algorithm requires a stable algorithm , Fast algorithm , We can decide to choose between cardinal sort and two-way merge sort , I chose radix sort , The example of quick sort is recalled , So I quickly worked out this problem .
<> Insert sort
basic thought ：
The idea of insertion sort is similar to the arrangement of playing cards
The original array is the unsorted hand to be played
You don't have to tidy up the first card , Start with the second one
Compare with the cards in your hand , Insert into the hand
realization ：
public static int[] insertSort(int[] sourceArray) { int s; int temp; for (int
i = 1; i < sourceArray.length; i++) { temp = sourceArray[i]; s = i; while (s >
0 && temp < sourceArray[s - 1]) { sourceArray[s] = sourceArray[s - 1]; s = s -
1; } sourceArray[s] = temp; } return sourceArray; }
<> Exchange sort
<> Bubble sort
basic thought ：
Execute from left to right n second ： Compare the sizes of adjacent elements , Who put who on the right
realization ：
private static int[] bubbleSort(int[] sourceArray) { for (int i = 0; i <
sourceArray.length; i++) { for (int j = 0; j < sourceArray.length - 1; j++) {
sortMaxAndPutItRight(sourceArray, j, j+1); } } return sourceArray; } private
static void sortMaxAndPutItRight(int[] sourceArray, int left, int right) { if
(sourceArray[left] > sourceArray[right]) { int temp = sourceArray[right];
sourceArray[right] = sourceArray[left]; sourceArray[left] = temp; } } <> Quick sort
basic thought ：
Execute from left to right n second ：
Select reference element （ For example, the first element ）,
Go left and right in the middle , The one on the left finds the one bigger than him , The one on the right finds the one smaller than him
Every time we find the order to exchange them , Until the left and right come together
When we get together , Select an element to exchange with the benchmark element
——
Then repeat the process on the left side of this position , On the right, too
realization ：
public static int[] quickSort(int[] sourceArray, int start, int end) { if
(start < end) { int index = sortAndFindIndex(sourceArray, start, end);
quickSort(sourceArray, start, index - 1); quickSort(sourceArray, index + 1,
end); } return sourceArray; } private static int sortAndFindIndex(int[]
sourceArray, int start, int end) { int temp = sourceArray[start]; while (start
< end) { while ((sourceArray[end] >= temp) && (start < end)) { end --; }
sourceArray[start] = sourceArray[end]; while ((sourceArray[start] <= temp) &&
(start < end)) { start ++; } sourceArray[end] = sourceArray[start]; }
sourceArray[start] = temp; return start; }
<> Select sort
<> Simple selection sort
basic thought ：
The sorting of choices is similar to the playing stage in a poker hand
Play the smallest card in your hand
After that , The cards found are in order
realization ：
public static int[] selectionSort(int[] sourceArray) { for (int i = 0; i <
sourceArray.length - 1; i++) { int min = i; for (int j = i + 1; j <
sourceArray.length; j++) { min = sourceArray[j] < sourceArray[min] ? j : min; }
swap(sourceArray, i, min); } return sourceArray; } private static void
swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] =
temp; } <> Heap sort
basic thought ： To be written
realization ： To be written
<> Cardinal sort
basic thought
Set last, set first （ for example 352 Of 2）, The penultimate is the second
Sort the numbers first
Sort the numbers by the second digit
The same number keeps the same position
realization
public static int getNumInPos(int num, int pos) { int tmp = 1; for (int i = 0;
i < pos - 1; i++) { tmp *= 10; } return (num / tmp) % 10; } public static int
getMaxDigit(int[] a) { int max = a[0]; for (int i = 0; i < a.length; i++) { if
(a[i] > max) { max = a[i]; } } int tmp = 1, d = 1; while (true) { tmp *= 10; if
(max / tmp != 0) { d++; } else { break; } } return d; } public static void
radixSort(int[] a, int d) { int[][] array = new int[10][a.length + 1]; for (int
i = 0; i < 10; i++) { array[i][0] = 0; } for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < a.length; i++) { int row = getNumInPos(a[i], pos); int col
= ++array[row][0]; array[row][col] = a[i]; } for (int row = 0, i = 0; row < 10;
row++) { for (int col = 1; col <= array[row][0]; col++) { a[i++] =
array[row][col]; } array[row][0] = 0; } } }
<> Count sort
basic thought
Find the maximum value of the array l, Create a length of l New array for
Take the value of the original array as the subscript of the new array , There are several , What is the number of subscripts
Traverse the new array from left to right , Assign value to original array
realization
private static int[] countSort(int[] array) { int maxVal =
Arrays.stream(array).max().getAsInt(); int[] sortList = new int[maxVal + 1];
for (int i : array) { sortList[i]++; } int sortedIndex = 0; for (int i = 0; i <
(maxVal + 1); i++) { while (sortList[i] > 0) { array[sortedIndex++] = i;
sortList[i]--; } } return array; }
<> Merge sort
<> merge sort
basic thought ： To be written
realization ： To be written
<> Recommended books
《 Data structure tutorial ( Third Edition )》
Technology