Bubble Sort
The principle of
Bubble sort only operates on two adjacent pieces of data. Each bubbling operation compares two adjacent elements to see if they meet the size relationship requirements. If you don’t, switch them. One bubble moves at least one element to its proper position, n times, and n numbers are sorted.
The illustration
Picture source network, infringement namely delete
performance
- Time complexity: O(n²)
- Best time complexity: O(n)
- Worst time complexity: O(n²)
- Average time complexity: O(n²)
- Space complexity: O(1)
code
public static void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// If there is no data exchange, exit early, exit the bubble loop flag bit early
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { / / exchange
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // Indicates data exchange}}if(! flag)break; // There is no data exchange, exit early}}Copy the codeInsertion Sort
The principle of
Insert sort like we play chess, every time we touch the card we will insert into the appropriate position, to ensure that our cards are in order, in this process we have a ratio of the size of the operation, insert sort is not as convenient as we manual, insert sort in addition to the size also need to move elements. For example, if a data a needs to be inserted into the sorted range, compare the size of a with the elements in the sorted range to find the appropriate insertion position. Once we find the insertion point, we also need to move the element after the insertion point one bit back in order to make room for element A.
The illustration
Picture source network, infringement namely delete
performance
- Time complexity: O(n²)
- Best time complexity: O(n)
- Worst time complexity: O(n²)
- Average time complexity: O(n²)
- Space complexity: O(1)
code
// Insert sort, a for array, n for array size
public static void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
// Find the insertion position
for (; j >= 0; --j) {
if (a[j] > value) {
a[j + 1] = a[j]; // Data movement
} else {
break;
}
}
a[j + 1] = value; // Insert data}}Copy the codeSelection Sort
The principle of
The idea is simple: start with the index I =0 and find the ratio of the smallest element to I after I +1. If the value of I +1 is less than the value of I, swap the two numbers. Then I ++ repeats the operation until the array is sorted.
The illustration
Picture source network, infringement namely delete
performance
- Time complexity: O(n²)
- Best time complexity: O(n²)
- Worst time complexity: O(n²)
- Average time complexity: O(n²)
- Space complexity: O(1)
code
public static void sort(int arr[],int n){
for( int i = 0; i < n ; i++ ){int min = i;// The index of the smallest element
for(int j = i + 1; j < n; j++ ){if(arr[j] < arr[min]){
min = j;// find the minimum value}}// Switch places
inttemp = arr[i]; arr[i] = arr[min]; arr[min] = temp; }}Copy the codeMerge Sort
The principle of
Merge sort is a divide-and-conquer idea. We split the sorted array in half, sort the two arrays separately, and merge the interfaces so that the whole data is sorted.
Merge sort, generally we adopt recursive way, will be split into the inseparable array, and then to sort an array of integral, around half of two groups were from the first one to start one by one more size, into the new temporary array, when about half the value of the same, on the left to the value of the first into the array, the final judgment on both sides if there is a surplus, Add the rest of the array to the temporary array. After the above operations, the entire array is ordered. Finally, copy the temporary array values back to the original array, and the whole merge sort is complete.
The illustration
Let’s use arrays 40, 2, 11, 5, 15, 6, 90, 10 to illustrate the merge sort process
performance
- Time complexity: O(nlogn)
- Best time complexity: O(nlogn)
- Worst time complexity: O(nlogn)
- Average time complexity: O(nlogn)
- Space complexity: O(n)
code
/** * Recursively splits the array into two halves and sorts the two halves separately **@param* nums array@paramThe left half of leftPtr begins with the subscript *@paramRightPtr right end subscript */
public static void merge_sort(int[] nums, int leftPtr, int rightPtr) {
if (leftPtr >= rightPtr) return;
// Split the array in half
int mid = leftPtr + (rightPtr - leftPtr) / 2;
// Sort the left half
merge_sort(nums, leftPtr, mid);
// Sort the right half
merge_sort(nums, mid + 1, rightPtr);
merge(nums, leftPtr, mid + 1, rightPtr);
}
/** * Merge two sorted arrays **@param nums
* @paramThe left half of leftPtr starts with subscript value *@paramRightPtr right half start subscript value *@paramRightBound left end value */
public static void merge(int[] nums, int leftPtr, int rightPtr, int rightBound) {
// Create a temporary sort array
int[] sortNums = new int[rightBound - leftPtr + 1];
// Find the median value
int mid = rightPtr - 1;
// Start subscript of the first half of the group
int i = leftPtr;
// Start subscript of the last half
int j = rightPtr;
// Temporarily sort the initial index of the array
int k = 0;
// Compare the left and right sides one by one, and store the small ones into a temporary array
while (i <= mid && j <= rightBound) {
sortNums[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
}
// Check the left half
while (i <= mid) sortNums[k++] = nums[i++];
// Check the left half
while (j <= rightBound) sortNums[k++] = nums[j++];
// copy the array back to nums
for (int m = 0; m < sortNums.length; m++) nums[leftPtr + m] = sortNums[m];
}
Copy the codeQuick Sort
The principle of
Quicksort is also called quicksort, and quicksort is the same divide-and-conquer idea as merge sort. Fast sorting is divided into single-axis fast sorting and double-axis fast sorting, because the efficiency of double-axis sorting is higher than that of single extraction sorting, so this article mainly talks about the double-axis sorting. Quick sort each time from A random selection of element in an array as the pivot, in general, the last element of an array of choice), and then from the first element of the array and partition value before begin to find an element, starting from the first element to find the score area value of the first number of A, since partition value in front of A number of forward lookup, Find the first score values area are small B, A and B will swap places, until the left to find the subscript is greater than the right began to find the index of the stop search, then partition value with the first number is greater than the partition value exchange position, this partition value all smaller than the number on the left side of the partition, the right of the number of all values greater than partition. Continue iterating through the left and right arrays until the entire array is sorted.
The illustration
We use arrays 40, 2, 11, 5, 15, 6, 90, 10 to illustrate the quicksort process
left
right
left
right
left
performance
- Time complexity: O(nlogn)
- Best time complexity: O(nlogn)
- Worst time complexity: O(n²)
- Average time complexity: O(nlogn)
- Space complexity: O(logn)
code
/ / recursion
public static void sort(int[] nums, int leftBound, int rightBound) {
if (leftBound >= rightBound) return;
// The subscript position of the partition value
int mid = partition(nums, leftBound, rightBound);
// Sort by left partition
sort(nums, leftBound, mid - 1);
// Sort by right partition
sort(nums, mid, rightBound);
}
/ / partition
public static int partition(int[] nums, int leftBound, int rightBound) {
// The value of the partition point
int piovt = nums[rightBound];
// Left subscript
int left = leftBound;
// Start right subscript
int right = rightBound - 1;
while (left <= right) {
// Find the first value greater than the partition value
while (left <= right && nums[left] <= piovt) left++;
// Find the first value less than the partition value
while (left <= right && nums[right] > piovt) right--;
// Swap the left and right values
if (left < right) swap(nums, left, right);
}
// Switch left and partition values
swap(nums, left, rightBound);
return left;
}
/** * Data exchange **@param nums
* @param i
* @param k
*/
public static void swap(int[] nums, int i, int k) {
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
Copy the codeBucket sort
The principle of
Bucket sorting, as the name implies, uses “buckets”. The core idea is that the data to be sorted is divided into several buckets according to the range, and the data in each bucket is sorted separately. After the bucket is sorted, the data in each bucket is taken out in sequence to form an orderly sequence.
The illustration
Let’s demonstrate bucket sorting using arrays 90,85,63,34,42,12,10
performance
- Time complexity: O(n)
- Best time complexity: O(n)
- Worst time complexity: O(nlogn)
- Average time complexity: O(n)
- Space complexity: O(n)
code
public static void sort(int[] nums) {
/ / Max
int maxValue = nums[0];
/ / the minimum
int minValue = nums[0];
int length = nums.length;
/** * find the maximum and minimum value */
for (int i = 1; i < length; i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
} else if(nums[i] < minValue) { minValue = nums[i]; }}// The difference between maximum and minimum,
int diff = maxValue - minValue;
// Initialize the bucket list
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for (int i = 0; i < length; i++) {
bucketList.add(new ArrayList<Integer>());
}
// The numerical spacing between buckets
float section = (float) diff / (float) (length - 1);
// Add data to bucket
for (int i = 0; i < length; i++) {
// Divide the current number by the range to get the location of the bucket
int num = (int) (nums[i] / section) - 1;
if (num < 0) {
num = 0;
}
bucketList.get(num).add(nums[i]);
}
// Sort within buckets
for (int i = 0; i < bucketList.size(); i++) {
// The built-in collection sorting framework in the JDK
Collections.sort(bucketList.get(i));
}
// Write to the original array
int index = 0;
for (ArrayList<Integer> arrayList : bucketList) {
for (intvalue : arrayList) { nums[index] = value; index++; }}}Copy the codeCounting sort
The principle of
Counting sort is actually a special case of bucket sort, so when we sort n items, if the range is not large, say k, we can divide the data into k buckets. The data values in each bucket are the same, saving the sorting time in the bucket. For example, Tencent interview questions, without data exchange, query your ranking? The full score is 750 and the minimum score is 0. This data range is very small, so we can divide it into 750 buckets with scores ranging from 0 to 750. Based on their scores, we divided those 500,000 into 750 buckets. The data in the bucket are all examinees with the same score, so there is no need to sort. We just need to scan each bucket in turn, output the examinees in the bucket in turn into an array, and achieve a sort of 500,000 examinees.
The illustration
We as an array of 5,8,9,7,8,4,5,6,9,3,0,2,1 counting to demonstrate the sorting process
performance
- Time complexity: O(n)
- Best time complexity: O(n)
- Worst time complexity: O(n)
- Average time complexity: O(n)
- Space complexity: O(n)
code
/** * count sort **@paramNums Array to be sorted *@paramRangeCount Number of array ranges *@paramMin Minimum number *@return* /
public static int[] countingSort(int[] nums, int rangeCount, int min) {
int[] result = new int[nums.length];
// Define count buckets
int[] count = new int[rangeCount + min];
// Add data to the bucket
for (int i = 0; i < nums.length; i++) {
count[nums[i]]++;
}
// Traversing the bucket writes data to the return array
for (int i = min, j = 0; i < count.length; i++) {
while (count[i]-- > 0) result[j++] = i;
}
return result;
}
Copy the codeRadix sort
The principle of
Radix sort is a kind of bucket sort, radix sort to sort of data is a requirement, can segment the independent “a” is needed to compare, and there is a progressive relationship between, if a data high than b, then the rest of the low need not more, in addition, each data range cannot too big, You can sort it using a linear sorting algorithm. For example, if we have 100,000 mobile phone numbers, we need to sort the phone numbers in order from smallest to largest. The preceding quicksort, bucket sort, and count sort can be quickly sorted, but the memory is limited, so you can use radix sort to solve the problem.
The illustration
We as an array of 2154589 6356201698412 to demonstrate the process of radix sort
performance
- Time complexity: O(n*k)
- Best time complexity: O(n*k)
- Worst time complexity: O(n*k)
- Average time complexity: O(n*k)
- Space complexity: O(n+ K)
code
public static void radixSort(int[] nums){
// Record the size of the array
int length = nums.length;
/ / Max
int numMax = nums[0];
for(int i = 0; i < length; i++){if(nums[i] > numMax){ numMax = nums[i]; }}// The current sort position
int location = 1;
// Bucket list A bucket can have multiple different elements
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
// Initialize an empty bucket
for(int i = 0; i < 10; i++){
bucketList.add(new ArrayList<Integer>());
}
while(true)
{
// Find the minimum value of each number
int min = (int)Math.pow(10,(location - 1));
// Check whether the maximum value is less than the minimum value of each number
if(numMax < min){
break;
}
// Iterate over the data and write it to the bucket
for(int i = 0; i < length; i++)
{
// Calculate the remainder and put it into the appropriate bucket
int number = ((nums[i] / min) % 10);
bucketList.get(number).add(nums[i]);
}
// Fetch the number from the bucket to form an array again
int k = 0;
for (int i=0; i<10; i++){int size = bucketList.get(i).size();
for(int j = 0; j < size; j ++){ nums[k++] = bucketList.get(i).get(j); }// Empty the bucket for the next sort
bucketList.get(i).clear();
}
// Add one digitlocation++; }}Copy the codeAbove is programming in the basic sorting algorithm, the basic sorting algorithm, in many components of internal use, if you understand the basic sorting, you read the source code is still some help, very feel you see here, I hope this article is helpful to you.
If you find mistakes in this article, please give me more advice. Welcome to pay attention to individual public number, exchange and study together.
The last
Play a small advertisement, welcome to scan the code to pay attention to the wechat public number: “The technical blog of the flathead brother”, progress together.
