1. Time complexity and space complexity of sorting algorithm
|
Sort Algorithm |
Average time complexity |
Worst time complexity |
Best time complexity |
Space complexity |
Stability |
|
Bubble sort |
O(n2) |
O(n2) |
O(n) |
O(1) |
? |
|
Direct selection sort |
O(n2) |
O(n2) |
O(n2) |
O(1) |
? |
|
Direct insertion sort |
O(n2) |
O(n2) |
O(n) |
O(1) |
? |
|
Quick sort |
O(nlogn) |
O(n2) |
O(nlogn) |
O(nlogn) |
? |
|
Heap sort |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
? |
|
Merge sort |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
? |
|
Hill sort |
O(nlogn) |
O(n2) | O(nlogn) |
O(1) |
? |
|
Counting sort |
O(n + k) |
O(n + k) |
O(n + k) |
O(n + k) |
? |
|
Radix sort |
O(N*M) |
O(N*M) |
O(N*M) |
O(M) |
? |
Note:
1 Merge sort can reduce the space complexity to O(1) through the hand algorithm, but the time complexity will increase.
2 The time complexity of radix sorting is O(N*M), where N is the number of data and M is the number of data bits.
1.1 Complexity Assisted Memory
- Bubble, selection, direct sorting requires two for loops, focusing on only one element at a time, and the average time complexity is O(n2)) (finding the element O(n) once, and finding the position O(n) once)
- Fast, merge, Hill, and heap are based on the dichotomy idea, log is based on 2, and the average time complexity is O(nlogn) (finding the element in one pass is O(n), and finding the position in one pass is O(logn))
1.2 Stability Auxiliary Memory
- Stability memory – “Quickly choose heap” (quickly sacrifices stability)
- Stability of the sorting algorithm: If the relative positions of the same elements before and after sorting remain unchanged, the sorting algorithm is said to be stable; otherwise, the sorting algorithm is unstable.
2. Understand the time complexity
2.1 Constant order O(1)
int i = 1; int j = 2; + + i; j + + ; int m = i + j;
2.2 Logarithmic order O(logN)
int i = 1;
while(i<n)
{
i = i * 2;
}
2.3 Linear order O(n)
for(i=0; i<=n; i + + )
{
System.out.println("hello");
}
2.4 Linear logarithmic order O(n)
for(m=1; m<n; m + + )
{
i = 1;
while(i<n)
{
i = i * 2;
}
}
2.5 square order O(n)
for(x=1; i<=n; x + + )
{
for(i=1; i<=n; i + + )
{
System.out.println("hello");
}
}
2.6 K-th power order O(n)
for(i=0; i<=n; i + + )
{
for(j=0; i<=n; i + + )
{
for(k=0; i<=n; i + + )
{
System.out.println("hello");
}
}
}
// k = 3 , n ^ 3
The time complexity of the above sequence from top to bottom is getting larger and larger, and the execution efficiency is getting lower and lower.
3. Space Complexity
3.1 Constant order O(1) – in-place sorting
Only an auxiliary space like temp is used
The in-place sorting algorithm is an algorithm with a space complexity of O(1) and does not involve obtaining additional space~
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
2.2 Logarithmic order O(logN)
2.3 Linear order O(n)
int[] newArray = new int[nums.length];
for (int i = 0; i < nums.length; i + + ) {
newArray[i] = nums[i];
}
4. Sorting algorithm
4.1 Bubble sort
(Idea: put the big ones at the back)
4.1.1 code
private static void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length; i + + ) {
for (int j = 0; j < nums.length - 1 - i; j + + ) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
}
4.1.2 Complexity
Time complexity: N^2
Space complexity:1
Optimum time complexity: N^2 (Because even if your inner loop only compares and does not exchange elements, it is still N)
Stability: Stable (only exchange if it is greater than, do not exchange if it is less than or equal to)
// { 0,1,2,3,4}
private static void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length; i + + ) {
boolean isChange = false;
for (int j = 0; j < nums.length - 1 - i; j + + ) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
isChange = true;
}
}
if(!isChange){
return;
}
}
}
Improved code, optimal time complexity: N (Because if there is no element exchange in the first round of comparison, you can exit directly, that is, there is only one outer loop)
4.2 Selection Sorting
(Idea: Put the smallest one first)
4.2.1 code
private static void selectSort(int[] nums) {
for (int i = 0; i < nums.length; i + + ) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j + + ) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums,minIndex,i);
}
}
4.2.2 Complexity
Time complexity: N^2
Space complexity:1
Best time complexity: N^2
Stability: Unstable
4.3 Direct insertion sort
(Idea: Find the appropriate position to insert into the sorted array)
4.3.1 code
private static void insertSort(int[] nums) {
for (int i = 1; i < nums.length; i + + ) {
int temp = nums[i];
int j = i - 1;
for (; j >= 0 & amp; & amp; temp < nums[j]; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = temp;
}
}
4.3.2 Complexity
Time complexity: N^2
Space complexity:1
Optimal time complexity: N (because you don’t enter the inner loop. [1,2,3,4,5])
Stability: Stable
4.4 Quick Sort
(Idea: Use the digital target to cut the array into two sides. The left side is larger than the target and the back side is smaller than the target)
4.4.1 code
/**
*Quick sort algorithm
* @param nums array to be sorted
* @param beginIndex sorting starting index
* @param endIndex sorting end index
*/
private static void quickSort(int[] nums, int beginIndex, int endIndex) {
if (beginIndex >= endIndex) {
return; // Recursion termination condition: when the start index is greater than or equal to the end index, it means that sorting has been completed
}
int mid = getMid(nums, beginIndex, endIndex); // Get the middle index, used to split the array
quickSort(nums, beginIndex, mid - 1); // Quick sort the array to the left of the middle index
quickSort(nums, mid + 1, endIndex); // Quick sort the array to the right of the middle index
}
/**
* Get the index of the middle element in the partition
* @param nums array to be sorted
* @param beginIndex The starting index of the partition
* @param endIndex The end index of the partition
* @return the index of the middle element
*/
private static int getMid(int[] nums, int beginIndex, int endIndex) {
int target = nums[beginIndex]; // Use the starting element of the array as the base value
int left = beginIndex;
int right = endIndex;
boolean right2left = true; // Flag bit, indicating that the current search is from right to left
while (right > left) {
if (right2left) {
while (right > left & amp; & nums[right] > target) {
right--;
}
if (right > left) {
nums[left] = nums[right]; // When the right element is larger, move the right element to the insertion position
right2left = false; // Switch to search from left to right
}
} else {
while (right > left & amp; & amp; nums[left] < target) {
left + + ;
}
if (right > left) {
nums[right] = nums[left]; // When the left element is smaller, move the left element to the insertion position
right2left = true; // Switch to search from right to left
}
}
}
nums[left] = target; // Put the reference value into the insertion position to complete a round of exchange
return left;
}
4.4.2 Complexity
Time complexity: N Log N (it takes LogN time to find the middle position of each element, and N elements are NLogN)
Space complexity: N Log N (recursive call, requires stack space)
Worst time complexity: N ^ 2 (such as positive sequence array [1,2,3,4,5])
Stability: Unstable
4.4.3 Related interview questions
1. Odd and even segmentation
Give you an array, with odd numbers on the left and even numbers on the right. Sorting is not required.
public static void main(String[] args) {
// Question, put odd numbers on the left and occasionally on the right
// Idea: Quick sort, exchange elements
int[] array = {13, 100, 17, 12, 25, 0,1,6};
quickSort(array, 0, array.length - 1);
System.out.println(JSON.toJSONString(array));
}
private static void quickSort(int[] array, int beginIndex, int endIndex) {
if (beginIndex >= endIndex) {
return;
}
int mid = getMid(array, beginIndex, endIndex);
}
private static int getMid(int[] array, int beginIndex, int endIndex) {
int left = beginIndex;
int right = endIndex;
int temp = array[beginIndex];
boolean right2Left = true;
while (left < right) {
if (right2Left) {
// if it is an even number
if (array[right] % 2 == 0) {
right--;
} else {
array[left + + ] = array[right];
right2Left = false;
}
} else {
// if it is an odd number
if (array[left] % 2 != 0) {
left + + ;
} else {
array[right--] = array[left];
right2Left = true;
}
}
}
array[left] = temp;
return left;
}
Thetime complexity of this method is O(N), the space complexity is O(1), and it is unstable
The time complexity of the following method is O(N), the space complexity is O(N), and it is stable
public static void main(String[] args) {
// Question, put odd numbers on the left and occasionally on the right
// Idea: Quick sort, exchange elements
int[] array = {13, 100, 17, 12, 25, 0, 1, 6, 5, 5};
int[] arrayNew = new int[array.length];
int oddCount = 0;
for (int i = 0; i < array.length; i + + ) {
if (array[i] % 2 != 0) {
oddCount + + ;
}
}
System.out.println(oddCount);
// Odd subscripts
int oddIndex = 0;
// even number subscript
int evenIndex = oddCount;
for (int i = 0; i < array.length; i + + ) {
if (array[i] % 2 != 0) {
arrayNew[oddIndex + + ] = array[i];
}else {
arrayNew[evenIndex + + ] = array[i];
}
}
System.out.println(JSON.toJSONString(arrayNew));
}
4.5 Heap Sort
(Idea: put the largest element on top, then exchange it with the last element, and continue building the heap)
4.5.1 code
/**
* Heap sort algorithm
* @param nums array to be sorted
* @param beginIndex The starting index of sorting
* @param endIndex The end index of sorting
*/
private static void heapSort(int[] nums, int beginIndex, int endIndex) {
if (beginIndex >= endIndex) {
return; // When the start index is greater than or equal to the end index, sorting is completed
}
for (int i = endIndex; i >= beginIndex; i--) {
createHeap(nums, i); // Build the maximum heap
swap(nums, 0, i); // Move the largest element to the end of the array
}
}
/**
* Build the largest heap
* @param nums array to be constructed
* @param endIndex The end index of the current heap
*/
private static void createHeap(int[] nums, int endIndex) {
int lastFatherIndex = (endIndex - 1) / 2;
for (int i = lastFatherIndex; i >= 0; i--) {
int biggestIndex = i;
int leftChildIndex = i * 2 + 1;
int rightChildIndex = i * 2 + 2;
if (leftChildIndex <= endIndex) {
biggestIndex = nums[biggestIndex] > nums[leftChildIndex] ? biggestIndex : leftChildIndex;
}
if (rightChildIndex <= endIndex) {
biggestIndex = nums[biggestIndex] > nums[rightChildIndex] ? biggestIndex : rightChildIndex;
}
swap(nums, biggestIndex, i); // Adjust the heap to ensure that the largest element is at the top of the heap
}
}
/**
* Swap the positions of two elements in the array
* @param nums array
* @param i index 1
* @param j index 2
*/
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
4.5.2 Complexity
Time complexity: N Log N (each element needs to build a heap once, which requires LogN time. N elements are NLogN, which is the same under any circumstances)
Space complexity: 1 (sort in place)
Worst time complexity: N ^ 2 (such as positive sequence array [1,2,3,4,5])
Stability: Unstable
4.6 Merge Sort
Recursive thinking, if the left and right sides are sorted, it is already sorted
4.6.1 code
//The main method of merge sort
private static void mergeSort(int[] nums, int beginIndex, int endIndex) {
// If the starting index is greater than or equal to the ending index, it means there is only one element or no elements, and no sorting is required.
if (beginIndex >= endIndex) {
return;
}
// Calculate the middle index of the array
int mid = beginIndex + (endIndex - beginIndex) / 2;
// Sort the left half recursively
mergeSort(nums, beginIndex, mid);
// Sort the right half recursively
mergeSort(nums, mid + 1, endIndex);
// Merge the left and right parts
merge(nums, beginIndex, mid, endIndex);
}
// Merge function, used to merge the left and right parts into an ordered array
private static void merge(int[] nums, int beginIndex, int mid, int endIndex) {
int left = beginIndex;
int right = mid + 1;
int[] newArrays = new int[endIndex - beginIndex + 1];
int newArraysIndex = 0;
// Compare the elements in the left and right parts and put the smaller element into the new array
while (left <= mid & amp; & amp; right <= endIndex) {
newArrays[newArraysIndex + + ] = nums[left] <= nums[right] ? nums[left + + ] : nums[right + + ];
}
//Copy the remaining left half elements to the new array
while (left <= mid) {
newArrays[newArraysIndex + + ] = nums[left + + ];
}
//Copy the remaining right half elements to the new array
while (right <= endIndex) {
newArrays[newArraysIndex + + ] = nums[right + + ];
}
//Copy the merged new array back to the original array
for (int i = 0; i < newArrays.length; i + + ) {
nums[beginIndex + i] = newArrays[i];
}
}
4.6.2 Complexity
Time complexity: N Log N (each element must be recursive, requiring LogN time, N elements are NLogN, the same in any case)
Space complexity:N
Stability: Stable
4.7 Hill Sorting
Idea: An upgraded version of direct insertion sort (segmented insertion sort)
4.7.1 code
private static void quickSort(int[] nums) {
// int gap = nums.length / 2;
// while (gap > 0) {
for (int i = 1; i < nums.length; i + + ) {
int temp = nums[i];
int j;
for (j = i - 1; j >= 0 & amp; & amp; temp < nums[j]; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = temp;
}
// gap = gap / 2;
// }
}
// To change the above quick sort to shell sort, just change the interval 1 to gap
private static void shellSort(int[] nums) {
int gap = nums.length / 2;
while (gap > 0) {
for (int i = gap; i < nums.length; i + + ) {
int temp = nums[i];
int j;
for (j = i - gap; j >= 0 & amp; & amp; temp < nums[j]; j = j - gap) {
nums[j + gap] = nums[j]; // If the current element is larger than the element to be inserted, move the current element backward
}
nums[j + gap] = temp; // Because when j=j-gap exits above, j has been cut once and may be less than 0
}
gap = gap / 2;
}
}
4.7.2 Complexity
Time complexity: N Log N
Space complexity:1
Stability: Unstable
4.8 Counting Sort
Prerequisite:
1. The size of the array is not large, such as counting the number of people of various ages in China (because the age is at most 0-150 years old)
4.8.2 code
public static void main(String[] args) {
int[] nums = {10, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 2, 8, 3, 4, 1, 2, 3, 4};
int[] ageCount = new int[200];
for (int i = 0; i < nums.length; i + + ) {
ageCount[nums[i]] + + ;
}
for (int i = 1; i < ageCount.length; i + + ) {
int count = ageCount[i];
for (int j = 0; j < count; j + + ) {
System.out.print(i + ",");
}
}
}
4.8.2 Complexity
Time complexity: N (N is the length of the array)
Space complexity:K
Stability: Stable
4.9 Radix Sort
4.9.1 code
How to get the number at the specified position?
public static void main(String[] args) {
int number = 1234;
// How to get the single digit 4 of 1234, 1234 % 10 = 4, 4/1 = 4
// 1234 How to get the tens digit 3, 1234 % 100 = 34, 34/10 = 3
// How to get the hundreds digit 2 of 1234, 1234 % 1000 = 234, 234/100 = 2
// How to get the thousands digit of 1234 1, 1234 % 10000 = 1234, 234/1000 = 1
for (int i = 0; i < getDigitLength(number); i + + ) {
int num = (int) (number % Math.pow(10, i + 1) / Math.pow(10, i));
System.out.println(num);
}
}
// 1 is 1 digit
// 10 is a 2-digit number
// 100 is a 3-digit number
// 1000 is 4 digits
public static int getDigitLength(int number) {
int length = 1;
while (number / 10 > 0) { // 100
length + + ;
number = number / 10;
}
return length;
}
Radix sort algorithm:
public static void main(String[] args) {
int[] array = {13, 100, 17, 12, 25};
Map<Integer, List<Integer>> bucketMap = new HashMap<>();
for (int i = 0; i < 10; i + + ) {
bucketMap.put(i, new ArrayList<>());
}
int maxDigitLength = 0;
for (int i = 0; i < array.length; i + + ) {
maxDigitLength = getDigitLength(array[i]) > maxDigitLength ? getDigitLength(array[i]) : maxDigitLength;
}
for (int i = 0; i < maxDigitLength; i + + ) { // Take the value from back to front
for (int j = 0; j < array.length; j + + ) {
int iValue = (int) (array[j] % Math.pow(10, i + 1) / Math.pow(10, i));
bucketMap.get(iValue).add(array[j]); // bucket
}
int arrayIndex = 0;
for (int j = 0; j < 10; j + + ) {
List<Integer> bucketList = bucketMap.get(j);
for (Integer num: bucketList) {
array[arrayIndex + + ] = num; //Pour it out
}
bucketMap.put(j,new ArrayList<>()); // Clear the bucket
}
System.out.println(JSON.toJSONString(array));
}
}
// 1 is 1 digit
// 10 is a 2-digit number
// 100 is a 3-digit number
// 1000 is 4 digits
public static int getDigitLength(int number) {
int length = 1;
while (number / 10 > 0) { // 100
length + + ;
number = number / 10;
}
return length;
}
4.9.2 Complexity
Time complexity: N * d (N is the length of the array, d is the maximum number of digits, for integer sorting, d = log N levels, so the whole is N Log N)
Space complexity:N
Stability: Stable
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57421 people are learning the system