This is the 28th day of my participation in the First Challenge 2022

The basic concept

• Proficiency in quicksort and merge sort is usually required
• To master the advantages and disadvantages of various sorting algorithms, the ideas of various algorithms and the use of various algorithms, but also skilled analysis of the time complexity and space complexity between various algorithms
• Sort: Display a sequence of objects in the order of a certain keyword
• Terms related to sorting:
  • Stable: if a is in front of B and a=ba=ba=b, then a is still in front of B after sorting
  • Unstable: If a comes before B, and a=ba=ba=b, then a may come after B after sorting
  • Internal sort: All sort operations are done in memory
  • External sort: Due to the large amount of data, the data is stored in the external disk. All sort operations can be completed through data transfer between the disk and memory
  • Time complexity: The amount of time an algorithm takes to execute
  • Space complexity: The amount of memory required to run an algorithm implementation
• Comparison of sorting algorithms in data structure:

Sorting algorithm name	Average time complexity	The best situation	The worst	Spatial complexity	The sorting way	The stability of
Quick sort	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	$O(logn)$	Occupied constant memory	unstable
Merge sort	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	Take up extra memory	stable
Bubble sort	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	Occupied constant memory	stable
Selection sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	Occupied constant memory	unstable
Insertion sort	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	Occupied constant memory	stable
Hill sorting	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	Occupied constant memory	unstable
Heap sort	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	Occupied constant memory	unstable
Count sorting	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$	Take up extra memory	stable
Bucket sort	$O(n+k)$	$O(n+k)$	$O(n^2)$	$O(n+k)$	Take up extra memory	stable
Radix sort	$O(n*k)$	$O(n*k)$	$O(n*k)$	$O(n+k)$	Take up extra memory	stable

• N: Data scale
• K: The number of barrels

• Classification of sorting algorithms in data structures:
  • Internal sort:
    • Insert sort:
      • Direct insertion sort
      • Hill sorting
    • Selection sort:
      • Simple selection sort
      • Heap sort
    • Swap sort:
      • Bubble sort
      • Quick sort
    • Merge sort
    • Radix sort
  • External sorting

Comparative sort and non-comparative sort

Comparison sort

• Comparison sort:In the final result of sorting, the order of the elements depends on the comparison between the elements, and each number must be compared to the rest to determine its position
  • Quick sort
  • Merge sort
    • In quicksort and merge sort, the problem size is reduced to Nlognnlognnlogn times by dial-and-conquer, and NNN times need to be compared, so the average time complexity is O(nlogn)O(nlogn)O(nlogn) O(nlogn)O(nlogn)
  • Heap sort
  • Bubble sort
    • The problem size is NNN, and the average time complexity is O(n2)O(n^2)O(n2) because NNN times need to be compared.
• Comparison sorting features:
  • Applicable to all kinds of scale data, do not pay attention to the distribution of data, can be sorted
  • Comparison sort applies to everything that needs sorting

Noncomparative sort

• Non-comparative sort:Sort by determining how many elements should precede each element
  • Count sorting
  • Radix sort
  • Bucket sort
    • Uniquely determine Array[I] ‘s position in sorted Array based on the number of elements before Array[I]
• Non-comparison sorting only needs to determine the number of existing elements before each element, which can be solved by traversing it once. Therefore, the time complexity of the algorithm is O(n)O(n)O(n).
• Non-comparison sort features:
  • The time complexity of non-comparison sort is low
  • Since non-comparative sort takes up space to determine unique locations, there are certain requirements on data size and data distribution

Count sort and bucket sort and radix sort

• These three non-comparative sorting algorithms all use the concept of buckets, but buckets are used differently:
  • Counting sort: Each bucket stores a single key value
  • Bucket sort: Each bucket stores a range of values
  • Radix sort: Buckets are allocated based on the value in each bit of the key value

Quick sort

• QuickSort:
  • Partitioning separates the elements to be sorted into two separate parts
  • The keywords in some records are smaller than those in other records
  • Then sort the two independent parts separately for the purpose of sorting as a whole
• Quicksort algorithm:
  • Select an element from the sequence as the base pivot
  • Reorder the array using the partition operation, with all elements smaller than the base value before the base and all elements larger than the base sequence after the base. After a partitioning operation is complete, the base is just “in the middle” of the sequence
  • Recursively sort subsequences that are less than the benchmark and those that are greater than the benchmark
• Example data structure quicksort algorithm
• Algorithm analysis:
  • Best case: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)
  • Worst case: T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)
  • Average: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)

Merge sort

• MergeSort:
  • Merge sort is a data sorting algorithm based on merge operation. It is a stable sorting algorithm using divide-and-conquer
  • Merge sort divides and divides the sequences that need to be sorted first, makes the sub-sequences orderly first, then makes the sub-sequence segments orderly, and then merges the already ordered sub-sequences to get a completely ordered sequence
  • Merge sort performance is not affected by the input data, it is always O(nlogn),O(nlogn),O(nlogn), but requires additional memory space
• Merge sort algorithm:
  • Divide the sequence to be sorted into two subsequences of the same length
  • Merge sort the two subsequences separately
  • Combine two sorted subsequences into one sorted sequence
• Example data structure merge sort algorithm
• Algorithm analysis:
  • Best case: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)
  • Worst case: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)
  • Average: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)

Bubble sort

• BubbleSort BubbleSort:
  • Bubble sort is a simple sorting algorithm called bubble sort because smaller elements float to the top by swapping
  • Repeat visits to compare the ordered sequence, comparing two elements at a time, and swapping the elements if they are out of order
  • The purpose of accessing the comparison sequence is to repeat the comparison until there are no more sequences to swap, indicating that the sequence has been sorted
• Bubble sort algorithm:
  • Compare two adjacent elements and, if the first is larger than the second, swap the order of the two elements
  • Do the same for each pair of adjacent elements, starting from the first pair to the last pair, so that at the end of each round of comparison, the last element is the largest element
  • Do this for all sequences of elements up to the last element in each round until the sorting is complete
• Example data structure bubble sort algorithm
• Algorithm analysis:
  • Best case: T(n)=O(n)T(n)=O(n)T(n)=O(n)
  • Worst case: T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)
  • T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)

Selection sort

• SelectionSort:
  • Selection sort is the most common sorting algorithm. The time complexity of the selection sort algorithm is O(n2).o (n^2).o (n2). Therefore, when using selective sort, the smaller the data size, the better
  • The only advantage of selecting the sort algorithm is that it doesn’t take up any extra memory
  • Selection sort algorithm principle:
    • First find the smallest element in the unsorted sequence and store it at the beginning of the sorted sequence
    • It then continues to find the smallest element from the remaining elements and places it at the end of the sorted sequence
    • Repeat this method until all elements are sorted
• Selection sort algorithm: nOne record passedn-1Round selection sort gives ordered results
  • Initially, the disordered region is R[1…n] and the ordered region is empty
  • At the beginning of round I sorting, the current ordered region is R[1…i-1], and the unordered region is R[I +1…n]. In this round of sorting, the record R[k] with the smallest keyword is selected from the current unordered region, and this element is exchanged with the first record in the unordered region, so that the ordered region R[1…i-1] and the unordered region R[I…n] become a new ordered region with 1 more records and a new unordered region with 1 less records, respectively
  • After the n-1 round, the array is ordered
• Data structure selection sort algorithm example
• Algorithm analysis:
  • T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)
  • Worst case: T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)
  • T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)

Insertion sort

• InsertionSort:
  • By building an ordered sequence, unordered data is scanned from back to front in the sorted sequence to find the corresponding position and insert
  • In the process of scanning from back to front, the sorted elements need to be moved one bit backward repeatedly to provide insertion space for the latest sorted elements
  • The insertion sort algorithm is usually implemented with in-Palce occupying constant memory, which only needs to use O(1)O(1)O(1) extra space
• Insert sort algorithm:
  • The first element is sorted by default, and the next element is taken from the first, scanning back to front in the sorted sequence
  • If the scanned element is larger than the retrieved element, the scanned element in the sequence is moved back one position until the scanned element is found to be less than or equal to the retrieved new element
  • Insert the fetched element into this position
  • Until the entire sequence has done this, the entire sequence is ordered
• Example data structure insertion sort algorithm
• Algorithm analysis:
  • Best case: T(n)=O(n)T(n)=O(n)T(n)=O(n)
  • Worst case: T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)
  • T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)

Hill sorting

• ShellSort:
  • Hill sort is also an insertion sort, a more efficient version of simple insertion sort, also known as reduced incremental sort, which was one of the first algorithms to break through O(n2)O(n^2)O(n2)
  • Hill sort differs from insertion sort in that hill sort compares distant elements first, so hill sort is called reduced increment sort
  • Hill sort is to group the elements to be sorted in increments, and then sort the elements of each group using the direct insert sort algorithm. As the increment decreases, each group contains more and more elements. When the increment decreases to 1, the whole file is divided into exactly one group, and the algorithm is finished
• Hill sorting algorithm:The whole sequence to be sorted is divided into several sub-sequences for direct insertion sorting
  • Select an incremental sequence, more than T1, T2… ,tk.t1, t2, … , tk.t1,t2,… , tk. Ti > tj, tk ti = 1 > tj, tk = 1 ti > tj, tk = 1
  • For the sequence with KKK increments, the KKK sequence is sorted
  • In each sequence, according to the corresponding increment ti,ti,ti, the sequence to be sorted is divided into several sub-sequences with the length of MMM, and the direct insertion sort is carried out for each sub-sequence. Only when the increment factor is 1, the whole sequence is sorted as a whole sequence

• Example of hill sort algorithm for data structures
• Algorithm analysis:The time complexity of hill sorting algorithm is located atO (n ^ ^ (1.3-2)),To reachO(n^2^)
  • Best case: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)
  • Worst case: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)
  • Average: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)

Heap sort

• Heap sort HeapSort:
  • The heap is a nearly complete binary tree structure. Always a complete tree, that is, all nodes except the lowest level are filled with elements, and the lowest level is filled as far from left to right as possible
  • The parent node of the heap is always greater or less than the value of the child node
    • A heap whose parent is greater than its child is called a large top heap
    • A heap whose parent is less than the child is called a small top heap
• Heap sort algorithm:
  • Put the initial keyword sequence R to be sorted1,R2. ,RnIt’s built into the big top heap, and this heap is the original unordered region
  • Take the top element R of the heap1And the last element, RnSwap, and you get a new unordered region R1,R2. ,Rn-1And a new ordered region RnAnd satisfies R1,R2. ,Rn-1They’re all less than or equal to Rn
  • Because the new heaptop element R of the swapped heap1May not conform to the properties of the heap top, so it is necessary for the new unordered region R1,R2. ,Rn-1Adjust to the new big top heap, and once again place the new unordered region of the heap top element R1And the last element in the unordered region Rn-1Swap, and you get a new unordered region R1,R2. ,Rn-2And a new ordered region Rn-1,Rn
  • Repeat this process until the entire sequence to be sorted is sorted
• Example heapsort algorithm for data structures
• Algorithm analysis:
  • Best case: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)
  • Worst case: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)
  • Average: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)

Count sorting

• Count sort CountingSort:
  • The core of counting sort is to convert the input data values into key values and store them in an extra array space
  • Counting sort is a kind of linear time complexity sort, which requires that the input data must be integers with a definite range
  • Counting sort is a stable sort algorithm:
    • Counting sort uses an extra counting array, where the index position is the number of elements in the array to be sorted whose value is equal to the index value
    • It then arranges the elements in the array to be sorted into the correct position according to the count array
    • Counting sort can only sort integers
• Counting sort algorithm:
  • Find the largest and smallest element of the array to be sorted
  • Count the number of occurrences of each element with offset I in the array to be sorted, stored at index position I in the count array
  • The value of each index position in the count array is accumulated to get the storage position of each value in the array to be sorted
  • Populates the sorted count array with the sorted values
• Example of counting sort algorithm for data structures
• Algorithm analysis:
  • When sorting NNN integers between 000 and KKK, the time complexity of counting sort algorithm is O(n+ K)O(n+ K)O(n+ K)
  • Counting sort is not comparison sort, so the time complexity of the algorithm is better than any comparison sort algorithm
  • Because the length of the array you create to count depends on the range of integers in the array to be sorted, the difference between the maximum and minimum plus 1, counting sort requires a lot of memory for arrays with large data ranges
  • Best case: T(n)=O(n+k)T(n)=O(n+k)T(n)=O(n+k)
  • Worst case: T(n)=O(n+k)T(n)=O(n+k)T(n)=O(n+k)
  • T(n)=O(n+k)T(n)=O(n+k)T(n)=O(n+k)

Bucket sort

• Bucket sort BucketSort:
  • Working principle:If the input data is uniformly distributed, that is, the elements to be sorted are equally likely to fall within equally spaced values, the data is sorted into a finite number of buckets, and then each bucket is reassigned and sorted. You can sort using the rest of the algorithms, or you can recursively sort using the bucket sort algorithm
    • One of lengthNWhen the array is sorted using buckets:
      • We need an auxiliary array of length N
      • Evenly spaced intervals are called buckets, and each bucket contains the elements of the array to be sorted
    • The more uniform the elements in the array to be sorted, the higher the efficiency of bucket sorting, that is, the number of elements in the bucket is roughly the same, so that the efficiency of bucket sorting is optimal
  • Bucket sort is to sort the elements in sorted array by using the mapping relation of functions. The key of bucket sort algorithm is to determine the mapping function efficiently
  • Bucket sort mapping function:Creates a functional mapping of the bucket position to the elements of the array to be sorted
    • The optimal efficiency of bucket sorting can be ensured by dividing elements into buckets as many as possible through proper mapping
    • 
      $index = f(v):$
      • Indexindexindex Indicates the index of the bucket array
      • VVV is the element in the array to be sorted
      • Make sure that if v1
• Bucket sorting algorithm:
  • We first initialize the set of array lengths to be sorted as the bucket range in bucket sorting
  • Iterate over the array to be sorted, and divide the elements in the array to be sorted into the corresponding bucket according to the bucket sort mapping function
  • For sorting non-empty buckets, other sorting algorithms can be used, and comparison sort, such as quicksort, merge sort, heap sort, and bubble sort, is recommended. You can also recursively use bucket sorting
  • The sorted elements in the non-empty bucket are joined together to complete the sorted array
• Example bucket sorting algorithm for data structures
• Algorithm analysis:
  • The time complexity of bucket sorting algorithm is divided into two parts:
    • Loops through the index of the bucket mapping function for each element to be sorted. The algorithm for this is O(n)O(n)O(n)
    • Sort the data in buckets, which is the decisive factor to improve the efficiency of bucket sorting algorithm:
      • One is to ensure that the bucket sort mapping function can evenly distribute the elements in the array to be sorted into buckets
      • The second is to increase the number of barrels as much as possible
  • The time complexity of bucket sorting algorithm is O(n),O(n),O(n). The time complexity of bucket sorting algorithm depends on the time complexity of sorting data in each bucket. The time complexity of other algorithms is O(n).o (n).o (n). Thus, the smaller the bucket is divided, the less data in the bucket is, and the time complexity of bucket sorting algorithm is smaller, but the corresponding space complexity is increased
  • Best case: T(n)=O(n+k)T(n)=O(n+k)T(n)=O(n+k)
  • Worst case: T(n)=O(n2)T(n)=O(n^2)T(n)=O(n2)
  • T(n)=O(n+k)T(n)=O(n+k)T(n)=O(n+k)

Radix sort

• Sort RadixSort:
  • Radix sort is a non – comparison sort algorithm. The time complexity of the algorithm depends on the maximum number of digits of the elements in the array to be sorted
  • Radix sort is sorted by low order and then collected. And then they sort it in order, and then they collect it again. Until the highest bit is sorted and collected. The number of digits here can also be different priorities
  • Radix sort is based on the difference sort of elements to be sorted, based on difference collection. So it’s a stable sort
  • Radix sort is suitable for sorting a small range of numbers
• Radix sort algorithm:
  • Gets the largest number of elements in the array to be sorted, and calculates the number of digits
  • Sort the elements in a sorted array by the digit at the specified bit, starting at the lowest digit
  • Each round completes the sorting of one digit until all digits are sorted and the entire array to be sorted is sorted
• Example of radix sort algorithm for data structure
• Algorithm analysis:
  • There are two ways to sort radix:
    • LSD: Sort from the lowest level
    • MSD: Sort from high
    • LSD is usually used to sort from the lowest
  • Best case: T(n)=O(n∗k)T(n)=O(n*k)T(n)=O(n∗k)
  • Worst case: T(n)=O(n∗k)T(n)=O(n*k)T(n)=O(n∗k)
  • T(n)=O(n∗k)T(n)=O(n*k)T(n)=O(n∗k)