Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "what are the performance improvement methods of sorting algorithms". In the operation process of actual cases, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

bubble sort

This is the simplest sort algorithm. Simply compare each pair of adjacent elements and check if the elements are ordered, otherwise swap the two elements until all elements are sorted.

for(int i =0;i

arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } }

Source: Google

(1)Performance analysis:

Time Complexity:

Worst-case: O(n²)-Since the elements are iterated n times, n being the length of the array, bubble sort takes O(n²) time.

Best case: O(n²)-Even if the array is sorted, the algorithm checks every adjacent pair, so the time complexity in the best case will be the same as in the worst case.

Space complexity: O(1).

Since only arrays are entered and no additional data structures are used, the space complexity will be O(1).

(2)Improved Bubble Sort:

If you look at the code, you will see that in the sorting algorithm above, even if the array is sorted, the time complexity will be the same, that is, O(n²).

To overcome this problem, an improved algorithm is proposed. Create a flag to determine if the array is sorted, which checks whether swaps have occurred between all adjacent pairs. If you traverse the entire array without swapping, the array is fully sorted and you can jump out of the loop. This greatly reduces the time complexity of the algorithm.

for(int i =0;i

arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; isSwapped =true; } if(! isSwapped){ break; } } }

(3)Performance analysis:

Time Complexity:

Worst-case: O(n²)-Same algorithm as above.

Best case: O(n)-Since in this algorithm the loop is broken if the array is sorted, the time complexity in the best case becomes O(n).

Space complexity: O(1).

selection sort

Assume that the first element in the sorting algorithm is the smallest element, and then check the rest of the array for elements smaller than the assumed minimum. If so, swap the assumed minimum with the actual minimum, otherwise move on to the next element.

for(int i=0;i= right) { break; } int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } int temp = arr[left]; arr[left] = arr[high]; arr[high] = temp; return left; }

Performance analysis:

Time Complexity:

Best case: O(nlogn)-First recursively divide the array into two subarrays in O(logn) time. Each function call calls a partition function with O(n) time complexity, so the total time complexity is O(nlogn).

Worst-case: O(n²)-When the array is sorted in descending order or all elements in the array are identical, the time complexity jumps to O(n²) due to the high imbalance of subarrays.

Space complexity: O(n).

Because the quicksort function is called recursively, an internal stack is used to store these function calls. There are at most n calls in the stack, so the space complexity is O(n).

merge sort

Merge sort, like Quick Sort, uses the concept of divide and conquer. In merge sort, the main job is to merge subarrays, while in quick sort, the main job is to partition/divide the array, so quick sort is also called partition sort.

The following function recursively splits an array into two subarrays until each subarray has only one element.

publicvoid merge(int arr[], int l, int m, int r) { int n1 = m-l+1; int n2 = r-m; int[] L =new int[n1]; int[] R =new int[n2]; for(int i =0;i < n1; i++) { L[i] = arr[l+i]; } for(int i =0;i < n2; i++) { R[i] = arr[m+1+i]; } int i =0, j =0, k =l; while(i < n1 && j < n2) { if(L[i]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.