Series collection:

A large collection of data structures

Algorithm – 1. Ten sorting algorithms

Algorithms – Ten classic Sorting Algorithms (GIF demo)

In computer science and mathematics, a Sorting algorithm is an algorithm that sorts a stream of data in a specific way. The most commonly used sorting methods are numeric and lexicographical. Sorting algorithms are also used to process textual data and produce human-readable output.

Basically, the output of the sorting algorithm must abide by the following two principles:

  1. The output is an increasing sequence (increasing in terms of the desired sort order)
  2. The output is a permutation or recombination of the original input

Basic introduction to algorithm

The ten sorting algorithms are generally divided into two categories:

  • Comparison sorting: to determine the relative order of elements by comparison, because its time complexity can not break O(Nlogn), so it is also called nonlinear time comparison sorting. (Bubble, select, Insert, merge, fast, Hill, heap sort)
  • Non-comparative sorting: it does not determine the relative order of elements by comparison. It can break through the lower bounds of time based on comparison sorting and operates in linear time. Therefore, it is also called linear time non-comparative sorting. (Count, base, barrel)

Ten sorting algorithm complexity overview:

  • N: Data scale
  • K: base quantity (eg: decimal k=1)
  • D: indicates the number of digits of the maximum value
  • M: The number of barrels

Noun explanation:

  • Stability: If the relative positions of two equal elements remain the same before and after sorting, this is called a stable sorting algorithm
  • In-place: not dependent on additional resources or on a small number of additional resources, relying only on the output to override the input
  • Time complexity: The amount of computation required to execute the algorithm. That is, the number of times the program needs to be executed
  • Space complexity: A measure of the amount of storage space temporarily occupied by an algorithm while it is running

baseCode

In order to facilitate the testing and implementation of other algorithms to make a base code can be ignored

class BaseSort: NSObject {
    var arrayList = [NSInteger] ()// The array to sort
    var swapCount = 0   // The number of swaps
    var cmpCount = 0    // The number of comparisons
    fileprivate func sort(array: [NSInteger]) {
        arrayList = array
        
        let startTime = CFAbsoluteTimeGetCurrent()
        sortAction()
        let endTime = CFAbsoluteTimeGetCurrent(a)let sortTitle = self.className
        print("" ""\(sortTitle)】 Execution time:\(endTime - startTime)Comparison times:\(cmpCount)Switching times:\(swapCount)-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - "" ")
        print(arrayList)
    }
    
    func sortAction(a){}/// compare the size of two elements equal to 0:v1=v2 < 0:v1
      
        0:v1>v2
      
    func cmpValue(_ v1: NSInteger._ v2: NSInteger) -> Int {
        return v1 - v2
    }
    func cmpIndex(_ index1: NSInteger._ index2: NSInteger) -> Int {
        let v1 = arrayList[index1]
        let v2 = arrayList[index2]
        cmpCount + = 1
        return cmpValue(v1, v2)
    }
    func swap(_ index1: NSInteger._ index2: NSInteger) {
        let temp = arrayList[index1]
        arrayList[index1] = arrayList[index2]
        arrayList[index2] = temp
        swapCount + = 1}}/// Create a random number group
func createRandom(count: NSInteger.min: NSInteger.max: NSInteger)- > [NSInteger] {var array = [NSInteger] ()for _ in 0..<count {
        let v = Int(arc4random_uniform(UInt32(max)))+min
        array.append(v)
    }
    return array
}

func testSorts(array: [NSInteger]._ objs:BaseSort...).{
    for obj in objs {
        obj.sort(array: array)
    }
}

Copy the code

1. Bubble Sort

Bubble sort, also known as bubble sort, is a simple sorting algorithm. It repeatedly visited to sort sequence, compare two elements at a time, if the order of their mistake the exchange of two elements, visit a work sequence is repeated until there is no need to exchange, that is to say, the series has been sequenced, the algorithm name because the smaller the element will slowly through the exchange of “float” to the top of the sequence.

Also known as bubble sort, is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name because smaller elements slowly “float” to the top of the list through swapping.

1.1 Algorithm Description

  1. Compare each pair of adjacent elements from the beginning, and if the first is larger than the second, swap their positions
    1. After a round, the last element is the largest element
  2. Ignore the largest element ever found in (1) and repeat step (1) until all elements are in order.

1.2 GIF demonstration

1.3 Code Implementation

  • Solution a:

    class BubbleSort01: BaseSort {
    override func sortAction(a) {
	      if arrayList.count < = 1 { return }
        let end = arrayList.count
        for j in 0..<end {
            for i in 1..<end-j {
                if cmpIndex(i, i-1) < 0 {
                   swap(i, i-1)}}}}}Copy the code

  • Optimization scheme:

    Think about:

    If no swap occurs after an inner for loop is executed once,

    Then you can prove that the data is sorted, and you can terminate the for loop.

    This operation is more obvious the closer the data is to being ordered.

    class BubbleSort02: BaseSort {
    override func sortAction(a) {
	      if arrayList.count < = 1 { return }
        let end = arrayList.count
        for j in 0..<end {
            var exchanged = true
            for i in 1..<end-j {
                if cmpIndex(i, i-1) < 0 {
                    swap(i, i-1)
                    exchanged = false // No exchange indicates that the remaining data is already in order}}if exchanged { break}}}}Copy the code

  • Scheme comparison Results

    var sortArray = createRandom(count: 1000, min: 0, max: 10000)
testSorts(array: sortArray,
          BubbleSort01(),
          BubbleSort02() Results:【Algorithm.BubbleSort01】Execution time:0.6306749582290649Comparison times:499500Switching times:240953
---------------------------------------------------------------------------------
【Algorithm.BubbleSort02】Execution time:0.6284579038619995Comparison times:498870Switching times:240953
---------------------------------------------------------------------------------It can be seen that the number of comparison after optimization is relatively small, the number of exchange is unchanged, and the overall time is slightly different.
Copy the code

2. Selection sort

Selection sort is a simple and intuitive sorting algorithm. Here’s how it works. First, find the largest (small) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, find the largest (small) element from the remaining unsorted elements, and place it at the end of the sorted sequence until all elements are sorted.

The main advantage of selection sort has to do with data movement; if an element is in the correct final position, it will not move. Selection sort Each time a pair of elements are swapped, at least one of them will be moved to its final position, so sorting a list of n elements does at most (n-1) swaps. Of all the sorting methods that rely on swapping to move elements, selective sorting is the best one.

2.1 Algorithm Description

  1. The first element in the sequence is,
  2. Compare the rest of the elements one by one, find the smallest element in the queue and swap with the first element
  3. After a loop you get the smallest value out front
  4. Ignore the elements already found, and loop through steps 2 or 3

2.2 GIF demonstration

1.3 Code Implementation

  • Scheme: Normal in situ algorithm

    override func sortAction(a) {
    if arrayList.count < = 1 { return }
    let end = arrayList.count
    for i in 0..<end {
        var min = i
        for begin in i..<end-1 {
            if cmpIndex(min, begin+1) > 0 {
                min = begin+1}}swap(i, min)
    }
}
Copy the code

  • Scheme comparison Results

    Copy the code

3. Heapsort

Heap sort is a sort algorithm designed by using heap data structure. A heap is a nearly complete binary tree structure that also satisfies the heap property: the key value or index of a child node is always smaller than (or greater than) its parent node

Heap sort can also be regarded as an optimization of selection sort

To learn more about data structures such as binary tree heap, please go to ~

1.1 Algorithm Description

involvesIn situ build mowBasic formula and concept of

  1. The parent nodeiPosition of the left child node of: 2i+1
  2. The parent nodeiPosition of the right child node of: 2i+2
  3. Child nodesiThe location of the parent node of: (i-1)/2
  4. Position of the first non-leaf node in a complete binary tree: number of elements /2

Algorithm description

  1. In situ build mow
  2. Swap top heap elements and tail elements
  3. The number of elements that are right goes down by 1
  4. Perform a siftDown on position 0
  5. Repeat steps 2, 3, and 4

1.2 GIF demonstration

1.3 Code Implementation

  • plan

    / / / heap sort
class HeapSort: BaseSort {
    var heapSize = 0
    override func sortAction(a) {
        heapSize = arrayList.count
        var i = heapSize >> 1 - 1
        while i > = 0 {
            siftDown(i)
            i- =1
        }
        while heapSize > = 1 {
						heapSize- =1   // Ignore swapped values
            swap(0, heapSize)  // Swap tail and top elements
            siftDown(0)   // Restore heap properties}}// Build the heap in place
    func siftDown(_ downIndex: Int) {
        let half = heapSize >> 1
        let value = arrayList[downIndex]
        var index = downIndex
        while index < half { // Index must be a non-leaf node
            var childIndex = (index << 1)+1
            var child = arrayList[childIndex]
            let rightIndex  = childIndex + 1
            if rightIndex < heapSize && (cmpValue(arrayList[rightIndex], child) > 0){
                childIndex = rightIndex
                child = arrayList[rightIndex]
            }
            if cmpValue(value, child) > = 0 { break }
            arrayList[index] = child
            index = childIndex
        }
        arrayList[index] = value
    }
}

Copy the code

  • Scheme comparison Results

    Copy the code

1. Insertion Sort

Insertion sort is a simple and intuitive sorting algorithm. It works by building an ordered sequence and, for unordered data, scanning back to front in the sorted sequence, finding the location of the response and inserting it. Insertion sort is usually implemented by in-place sort (that is, only O(1) extra space is needed). Therefore, In the process of scanning from back to front, the sorted elements need to be moved backwards repeatedly to provide insertion space for the latest element.

Insert sort similar to poker sort can be based on the thinking of daily poker to think

4.1 Algorithm Description

  1. Starting with the first element, the default is that the first element is already sorted
  2. Takes the next element and scans back to front in the sorted sequence
  3. If the element is larger than the element taken out, move it back
  4. Repeat step 3 until you find a position in the sorted sequence that is less than or equal to the fetched element
  5. Insert the extracted element into the position with the element
  6. Repeat steps 2 to 5

4.2 GIF demonstration

4.3 Code Implementation

  • Solution:

    override func sortAction(a) {
  for i in 1..<arrayList.count {
    var begin = i
    let value = arrayList[begin]
    while begin > 0 && cmpValue(arrayList[begin-1], value) > 0 {
      arrayList[begin] = arrayList[begin-1]
      begin - = 1
    }
    arrayList[begin] = value
  }
}	
Copy the code

5. Merge sort

Merge sort is an efficient sorting algorithm based on merge operation, with an efficiency of O(nlogn). It was first proposed by John von neumann in 1945. This algorithm is a very typical application of divide-and-conquer, and each layer branch recursion can be carried out simultaneously.

Merge operation: Refers to the operation that merges two sorted sequences into a single sequence. Merge sort algorithm depends on merge operation

5.1 Algorithm Description

  1. Continuously splits the current sequence into two subsequences

    • Until it can’t be split (only one element in a sequence)

  2. Continuously merge 2 subsequences into one ordered sequence

    • Merge requires temporary variables:

      • Li: Left sequence start position LE: left sequence end position
      • Ri: start position of the right sequence re: end position of the right sequence
      • Ai: Current insertion position

    • Take the left sequence out ahead of time and loop through the current left sequence

    • Compare the values of the left and right sequences and then overwrite them at [ai].

  3. Until finally there’s only one sequence left

5.2 GIF demonstration

5.3 Code Implementation

  • plan

    // merge sort
class MergeSort: BaseSort {
    var leftArray = [NSInteger] ()override func sortAction(a) {
        leftArray = [NSInteger](repeating: 0, count: arrayList.count >> 1)
        divide(0, arrayList.count)
    }
    / / segmentation
    func divide(_ begin: NSInteger._ end: NSInteger){
        if end - begin < 2 { return }
        let mid = (begin+end) >> 1
        divide(begin, mid)
        divide(mid, end)
        merge(begin, mid, end)
    }
    / / merge
    func merge(_ begin: NSInteger._ mid: NSInteger._ end: NSInteger){
        var li = 0, le = mid-begin
        var ri = mid, re = end
        var ai = begin
        for i in li..<le {
            leftArray[i] = arrayList[begin+i]
        }
        while li<le {
            if ri<re && cmpValue(arrayList[ri], leftArray[li])<0 {
                arrayList[ai] = arrayList[ri]
                ai+ =1; ri+ =1
            }else{
                arrayList[ai] = leftArray[li]
                ai+ =1; li+ =1}}}}Copy the code

6. Quicksort

Quicksort, also known as partition swap sort, or quicksort for short, is a sorting algorithm, first proposed by Tony Hall. In the average case, sorting n items requires O(nlogn) comparisons, and in the best case, O(n^2) comparisons, but this is not common. In fact, quicksort O(nlogn) is usually significantly faster than other algorithms because its inner loop can be achieved efficiently on most architectures.

Quicksort uses a divide-and-conquer strategy to divide a sequence into smaller and larger subsequences, and then recursively sort the two subsequences

5.1 Algorithm Description

  1. Select a reference value from the sequence (Pivot)
    1. Assume that the element in position 0 is selected each time as the base value
  2. Using pivot, the sequence is divided into 2 subsequences
    1. Swap a random reference value with the 0th position (to avoid the worst time complexity)
    2. Place the element less than pivot in front of pivot (left)
    3. Place the element greater than pivot behind pivot (right)
    4. You can put anything equal to pivot there
  3. Operations 1 and 2 are performed on subsequences
    1. Until no longer in split position (there is only 1 element left in the self-column element)

5.2 GIF demonstration

5.3 Code Implementation

  • plan

    class QuickSort: BaseSort {
    override func sortAction(a) {
        sort(0, arrayList.count)
    }
    func sort(_ begin: NSInteger._ end: NSInteger) {
        if end-begin < 2 { return }
        // Determine the base value of the element
        let mid = pivotIndex(begin, end-1)
        sort(begin, mid)
        sort(mid+1, end)
    }
    func pivotIndex(_ begin: NSInteger._ end: NSInteger) -> NSInteger {
        // Swap a random reference element with the first one
        let random = Int(arc4random_uniform(UInt32(end-begin)))+begin
        swap(begin, random)
        let pivotValue = arrayList[begin]
        var beginIndex = begin
        var endIndex = end
        while beginIndex < endIndex {
            while beginIndex < endIndex {
                if cmpValue(pivotValue, arrayList[endIndex]) < 0 {
                    endIndex- =1
                }else{
                    arrayList[beginIndex] = arrayList[endIndex]
                    beginIndex+ =1
                    break}}while beginIndex < endIndex {
                if cmpValue(pivotValue, arrayList[beginIndex]) > 0 {
                    beginIndex+ =1
                }else{
                    arrayList[endIndex] = arrayList[beginIndex]
                    endIndex- =1
                    break
                }
            }
        }
        arrayList[beginIndex] = pivotValue
        return beginIndex
    }
}

Copy the code

7. Shellsort

Hill sort, also known as descending incremental sort algorithm, is an efficient and improved version of insertion sort, hill sort is very stable sorting algorithm

Hill sort is an improved method based on the following two properties of insertion sort:

  • Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort
  • But insert sort is generally inefficient because it can only move data one bit at a time

Step sequence

Step size selection is an important part of Hill sorting. Any sequence of steps will work as long as the final step is 1. The algorithm starts by sorting by a certain step size. It then continues to sort at a certain step size, and eventually the algorithm sorts at a step size of 1. When the step size is 1, the algorithm changes to ordinary insertion sort, which guarantees that the data will always be sorted.

Donald Shell initially suggested choosing a step size of n/2 and taking half the step size until it reached 1. Although this can be better than the O(n^2) algorithm (insertion sort), there is still room to reduce the average and worst times

The best known step size sequence is proposed by Sedgewick (1, 5, 19, 41, 109…). .

7.1 Algorithm Description

Hill sort, right? A sequence is viewed as a matrix, divided into m columns, sorted column by column

  • M decreases from some integer to 1
  • When m is 1 the whole sequence is completely ordered

The number of columns in the matrix depends on the step size sequence

  • If the step size sequence is [1,5,19,41,109… , which means 109 columns, 41 columns, 19 columns, 5 columns, and 1 column at a time
  • The execution efficiency of different step – size sequences is also different

concept

  1. Assume the element is in the col column, row 1, and step (total number of columns) is step

    • The index of this element in the array col+row*step
    • For example, 9 is in the second column of the sequence, row 0, 2 plus 0 times 5 is 2

7.2 GIF demonstration

7.3 Code Implementation

  • plan

    class ShellSort: BaseSort {
    override func sortAction(a) {
        let stepSequence = sedgewickStepSequence() // Step size sequence
        for step in stepSequence {
            sort(step)
        }
    }
    func sort(_ step:NSInteger){
        for col in 0..<step {
            var begin = col + step
            while begin < arrayList.count {
                var cur = begin
                let value = arrayList[begin]
                while cur > col && cmpValue(value,arrayList[cur-step]) < 0 {
                    arrayList[cur] = arrayList[cur-step]
                    cur - = step
                }
                arrayList[cur] = value
                begin + = step
            }
        }
    }
  
    
    /// step size sequence implementation
    / / / - Returns:,5,19,41,109... [1]
    func sedgewickStepSequence(a)- > [NSInteger] {
        var stepSequence = [NSInteger] ()var k = 0, step = 0
        while true {
            if k % 2 = = 0 {
                let powNum:Int = Int(pow(CGFloat(2), CGFloat(k>>1)))
                step = 1+9*(powNum * powNum - powNum)
            }else{
                let powNum1:Int = Int(pow(CGFloat(2), CGFloat((k-1)>>1)))
                let powNum2:Int = Int(pow(CGFloat(2), CGFloat((k+1)>>1)))
                step = 1 + 8 * powNum1 * powNum2 - 6 * powNum2
            }
            if step > = arrayList.count { break }
            stepSequence.insert(step, at: 0)
            k+ =1
        }
        return stepSequence
    }
}
Copy the code

8. Counting sort

Counting sort is a stable linear time sort algorithm. The algorithm was proposed by Harold H. Seward in 1954. Counting sort uses an extra array C, where the ith element is the number of elements in array A whose value is equal to I. We then arrange the elements in A into the correct position according to array C.

Since the length of the array C used to count depends on the range of data in the array to be sorted (equal to the difference between the maximum and minimum value of the array to be sorted plus 1), counting sort takes a lot of time and memory for arrays with a large range of data. For example, counting sort is the best algorithm for sorting numbers between 0 and 100, but it is not suitable for sorting names alphabetically. However, counting sort can be used in radix sort algorithms to more efficiently sort large arrays of data.

8.1 Algorithm Description

  • Find the largest and smallest elements in the array to be sorted;
  • Count the number of occurrences of each element of value I in the array and store it in the i-th entry of array C;
  • Add up all the counts (starting with the first element in C, adding each term to the previous one);
  • Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element.

8.2 Animation Demonstration

8.3 Code Implementation

  • way

    class CountingSort: BaseSort {
    override func sortAction(a) {
        guard arrayList.count > 0 else { return }
        let maxElement = arrayList.max() ?? 0
        var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
        for element in arrayList {
            countArray[element] += 1
        }
        for index in 1 ..< countArray.count {
            let sum = countArray[index] + countArray[index - 1]
            countArray[index] = sum
        }
        / / output
        for element in arrayList {
            countArray[element] -= 1
            arrayList[countArray[element]] = element
        }
    }
}

Copy the code

9. Radix sort

Radix sort is a kind of non-comparative integer sort algorithm. Its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers.

It is implemented by unifying all values to be compared (positive integers) into the same digit length, with the shorter digit preceded by zeros. Then, sort the order one by one, starting with the lowest order. So from the lowest order to the highest order, the sequence becomes an ordered sequence.

The radix sort can be LSD (Least Significant Digital) or MSD (Most Significant Digital). LSD sorts from the right of the key, while MSD sorts from the left of the key.

9.1 Algorithm Description

  1. A single digit, ten digit, hundreds digit, thousands digit… Sort (from lowest to highest)
  2. The ones digit tens digit hundreds range from 0 to 9, and can be sorted by counting sort

9.2 GIF demonstration

9.3 Code Implementation

  • way

    
class RadixStor: BaseSort {
    override func sortAction(a) {
        var tempArray = [Int] ()var maxValue = 0
        var maxDigit = 0
        var level = 0
        repeat {
            var buckets = [[Int]] ()for _ in 0..<10 {
                buckets.append([Int]())
            }
            for i in 0..<arrayList.count {
                let elementValue = arrayList[i]
                let num = pow(10.0.Double(level))
                let divident = level < 1 ? 1 : NSDecimalNumber(decimal:Decimal(num)).intValue
                let mod = elementValue / divident % 10
                buckets[mod].append(elementValue)
                if maxDigit = = 0 {
                    if elementValue > maxValue {
                        maxValue = elementValue
                    }
                }
            }
            tempArray.removeAll()
            for element in buckets {
                tempArray.append(contentsOf: element)
            }
            if maxDigit = = 0 {
                while maxValue > 0 {
                    maxValue = maxValue / 10
                    maxDigit + = 1
                }
            }
            arrayList = tempArray
            level + = 1
            
        } while (level < maxDigit)
    }
}

Copy the code

10. Bucket sort

Bucket sort, or box sort, is a sorting algorithm that works by sorting an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sort recursively). Bucket sort is a kind of induction result of pigeon nest sort. Bucket sort, however, is not comparison sort, and it is not affected by the lower bound O(nlogn).

10.1 Algorithm Description

  1. Create a number of buckets (such as an array linked list)
  2. According to certain rules (different types of data, different rules), the elements in the sequence are evenly distributed to the corresponding buckets
  3. Sort each bucket individually
  4. Merges all non-empty bucket elements into an ordered sequence

10.2 GIF demonstration

10.3 Code Implementation

  • plan

    override func sortAction(a) {
    let maxNum = arrayList.max()
    var bucket:[Int] = Array.init(repeatElement(0, count: maxNum! + 1))
    var newNum:[Int] = Array.init(a)for index in arrayList {
        let numId = index
        bucket[numId] + = 1
    }
    for index in bucket.indices {
        while bucket[index] > 0 {
            newNum.append(index)
            bucket[index] - = 1
        }
    }
    arrayList = newNum
}
Copy the code

Efficiency comparison:

Non-comparison class:

var sortArray = createRandom(count: 10000, min: 0, max: 100000)
testSorts(array: sortArray,
          CountingSort(), // Count sort
          RadixStor(),    // Base sort
          BucketSort(a)/ / bucket sorting
				)

【Algorithm.CountingSort】Execution time:0.09470701217651367     
---------------------------------------------------------------------------------
【Algorithm.RadixStor】Execution time:0.07344508171081543    
---------------------------------------------------------------------------------
【Algorithm.BucketSort】Execution time:0.168626070022583     
---------------------------------------------------------------------------------
Copy the code

Counting sort takes up a lot of space and is only suitable for concentrated data. Such as [0 100], [10000 19999] such data.

Bucket sorting data can be used in the maximum minimum value is large, such as [9012197, 02398, 67689, 57835, 56102, 456]. However, bucket sorting requires that data be evenly distributed; otherwise, data may be concentrated in one bucket. For example, [104,150,123,132,20000] would cause the first four numbers to be clustered in the same bucket. The bucket sorting fails.

Radix sort is generally used for arrays of elements of the same length. Radix sort can be thought of as doing multiple bucket sorts. Each significant number is between 0 and 9, which is good for bucket sorting, and it’s easy to build 10 buckets

Comparison algorithms:

  • Bubble sort 01, bubble sort 02, select sort, insert sort because it takes a long time

  • Data size 1000

    var sortArray = createRandom(count: 1000, min: 0, max: 10000)
testSorts(array: sortArray,
          BubbleSort01(),
          BubbleSort02(),
          SelectSort01(),
          InsertionSort01())【Algorithm.BubbleSort01】Execution time:0.6120259761810303Comparison times:499500Switching times:248498
---------------------------------------------------------------------------------
【Algorithm.BubbleSort02】Execution time:0.6053379774093628Comparison times:499500Switching times:248498
---------------------------------------------------------------------------------
【Algorithm.SelectSort01】Execution time:0.4609769582748413Comparison times:499500Switching times:1000
---------------------------------------------------------------------------------
【Algorithm.InsertionSort01】Execution time:0.12423503398895264Comparison times:249485Switching times:0
---------------------------------------------------------------------------------
Copy the code

  • ** Heap sort, merge sort. Quick sort, Hill sort **

  • The data size is 10,000

    var sortArray = createRandom(count: 10000, min: 0, max: 100000)
testSorts(array: sortArray,
          HeapSort(),
          MergeSort(),
          QuickSort(),
          ShellSort())【Algorithm.HeapSort】Execution time:0.13575303554534912Comparison times:235379Switching times:10000
---------------------------------------------------------------------------------
【Algorithm.MergeSort】Execution time:0.2747499942779541Comparison times:120561Switching times:0
---------------------------------------------------------------------------------
【Algorithm.QuickSort】Execution time:0.1792229413986206Comparison times:150138Switching times:6625
---------------------------------------------------------------------------------
【Algorithm.ShellSort】Execution time:0.3527510166168213Comparison times:196090Switching times:0
---------------------------------------------------------------------------------
Copy the code

Finally, you can choose this picture according to your needs ~~

END~

Reference:

  • wikipedia
  • Love data structures and algorithms
  • www.jianshu.com/p/bd6860146…
  • www.cnblogs.com/onepixel/p/…
  • Blog.csdn.net/donghuabian…
  • www.cnblogs.com/jiangfan95/…