Recently, I feel that I have no progress in programming, and I want to practice my internal skills, so I began to review and learn data structures and algorithms. In fact, programmers probably know that “program is equal to algorithm + data structure”, understanding and selection of appropriate data structure, as well as algorithms, is the premise of writing excellent programs. In the JAVA JDK, the importance of data structure algorithms can also be seen. For example, in HashMap, array + linked list is used to improve the efficiency of searching and inserting. I also want to improve learning efficiency by summarizing the way of writing articles, so I have this article. To push myself, I decided to write a blog post every week (not necessarily about data structures and algorithms). Due to my limited level, coupled with poor literary talent, but also rarely write blog, I hope to see the article you can put forward views, suggestions.
Bubble sort
1, description,
Bubble sort, each bubble compares the size of two adjacent numbers, the size relationship is not correct, then swap. In the figure below, when the first bubble comes down, the largest value will be placed in the correct position, and there may be other numbers in the correct position. So at least one of the largest ones is in the correct position (9 in the figure below).
After the second run, the largest 8 of the remaining numbers after the first run will be in the correct position again (see figure below).
This will bubble up n minus 1 times at most, and it will be an ordered sequence
2. The JAVA code is implemented as follows
Public static void sort(int numArray[]) {public static void sort(int numArray[]) {if (numArray == null || numArray.length == 0) {
return; } int arrayLength = numArray.length; int tmp; // If there is no swap, the array is already in order and does not need to bubble. boolean flag =false; // Outer layer: need length-1 loop comparison, need n-1 bubblefor(int i= 0; i < arrayLength - 1; i++) {
flag = false;
for(int j=0; j < arrayLength -i-1; J++) {// inner: the number of pairwise comparisons required for each loop. After each comparison, the current largest number is put in the last positionif(numArray[j] > numArray[j+1]) {
tmp = numArray[j];
numArray[j] = numArray[j+1];
numArray[j+1] = tmp;
flag = true; }}if(! Flag) // There is no swap, the array is already in orderbreak; }}Copy the codeSecond, selection sort
1, description,
Select sort as shown below, find the smallest remaining value each time, and place that minimum value in the correct position
2. The JAVA code is implemented as follows
public static void selectSort(int numArray[]) { int length = numArray.length; int min,pos; // Each time the loop finds the smallest number remaining and places it in the correct positionfor(int i= 0; i < length-1; i++) { min = numArray[i]; pos = i; // Find the smallest number remainingfor(int j = i+1; j < length; j++) {
if(numArray[j] < min) { min = numArray[j]; pos = j; }}if(pos ! = i) { numArray[pos] = numArray[i]; numArray[i] = min; }}}Copy the codeInsert sort
1, description,
Insert sort is the same as when we play poker to sort the cards, each time draw a card, insert into the hand already ordered cards. In the following example, we start with the second number and insert it in front. As shown below, the second time, the 6 needs to be inserted between the first 5 and 8, so move the 8 back and then insert the 6.
2. The JAVA code is implemented as follows
public static void insertSort(int intList[]) {
int j = 1;
int i;
for(; j < intList.length; j++) {
i = j-1;
int key = intList[j];
while(i > -1 && intList[i] > key) { intList[i+1] = intList[i]; i--; } intList[i+1] = key; } // Time complexity is O(n^2), best case time complexity is O(n), average time complexity is O(n^2)}Copy the codeQuicksort
1, description,
Quicksort uses the idea of divide-and-conquer, the general idea is to take a number as the base value, and put all the elements smaller than it in front of it, and put the elements larger than it behind it, and then the base value will be in the correct position, and sort the two arrays before and after the base value respectively, and finally it will be ordered. Quicksort can be implemented in a number of ways, but the following is done using the left and right Pointers.
2,The JAVA code implementation is as follows
public static void quickSort(int numArray[],int _left, int _right) {
int left = _left;
int right = _right;
int temp = 0;
if(left <= right){temp = numArray[left]; // The first element to be sorted is the base elementwhile(left ! = right){// Scan alternately from left to right until left = rightwhile(right > left && numArray[right] >= temp) right --; NumArray [left] = numArray[right]; // Find arr[right] and swap with arr[left]while(left < right && numArray[left] <= temp) left ++; NumArray [right] = numArray[left]; NumArray [right] = temp; arr[left] = temp; QuickSort (numArray,_left,left-1); QuickSort (numArray, right+1,_right); // Sort the base element recursively}}Copy the codeMerge sort
1, description,
Merge sort is also divide-and-conquer. All elements are separated and sorted step by step, as shown in the following figure
2,The JAVA code implementation is as follows
public static int[] sort(int [] a) {
if (a.length <= 1) {
return a;
}
int num = a.length >> 1;
int[] left = Arrays.copyOfRange(a, 0, num);
int[] right = Arrays.copyOfRange(a, num, a.length);
returnmergeTwoArray(sort(left), sort(right)); } public static int[] mergeTwoArray(int[] a, int[] b) { int i = 0, j = 0, k = 0; int[] result = new int[a.length + b.length]; // Request extra space to store the merged datawhile(I < a.length &&j < b.length) {// Take the smaller value of the two sequences and put it into a new arrayif (a[i] <= b[j]) {
result[k++] = a[i++];
} else{ result[k++] = b[j++]; }}while(I < a. ength) {/ / sequence is a result of superfluous elements into the new array [k++] = [i++] a; }while(j < b.l ength) {/ / redundant elements in sequence b moved into the new array result [k++] [j++] = b; } System.out.println(Arrays.toString(result));return result;
}
Copy the code