This paper adopts array implementation.

Direct insertion sort

Idea: Insert the first record of the unordered region into the appropriate position of the ordered region by keyword each time, and increase the length of the ordered region by 1.

func insertSort(array: inout [Int]) -> Void {
    guard array.count > 1 else {
        return
    }
    
    for i in0.. <(array.count-1) {ifArray [I + 1] < array[I]letTemp = array[I + 1] // Save the value that will be replaced by the ordered region. Var j = I + 1// Ordered region number repeat {// data move, J -= 1 array[j + 1] = array[j]}while(j - 1 > = 0) && (array [1] > temp) / / also need to move/insert/array [j] = temp}}}Copy the code

Hill sorting

Also known as reduced increment sort, is an improvement on direct insert sort.

A shell sort is an array of elements sorted into parts. Sort a few small pieces of the elements so that they have a rough order, and then use insert sort for the whole thing. Usually the last sort is the same as the direct insert sort above.

Func shellInsert(array: inout [Int], dk: Int) -> Void {for i in0.. <(array.count-dk) {ifArray [I + dk] < array[I]letTemp = array[I + dk]// Save the value to be replaced by the ordered region back var j = I + dk// ordered region number repeat {// J -= dk array[j + dk] = array[j]}while(j-dk >= 0) && (array[j-dk] > temp)// Insert array[j] = temp}}} func shellSort(array: inout [Int], dk: [Int]) -> Void { guard array.count > 1else {
        return} // Hill sort array by delta d[]for dkItem in dk {
        shellInsert(array: &array, dk: dkItem)
    }
}
Copy the code

Bubble sort

Idea: It iterates through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if they are in the wrong order (e.g., from largest to smallest, starting with A to Z). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element has been sorted.

func bubbleSort(array:inout [Int]) -> Void {
    guard array.count > 1 else {
        return
    }

    for i in0.. <(array.count -1) {// The outer loop is array length -1for j in0.. <(array.count -1 -i) {// The inner loop is the outer loop -iifArray [j] > array[j + 1] {// Bubble array.swapat (j, j + 1)}}}}Copy the code

Selection sort

Each time, select the smallest (or largest) element from the data elements to be sorted and store it at the beginning of the sequence. Then, continue to search for the smallest (or largest) element from the remaining unsorted elements and place it at the end of the sorted sequence. And so on, until all the data elements to be sorted are sorted. Selection sort is an unstable sort method.

func selectSort(array:inout [Int]) -> Void {
    guard array.count > 1 else {
        return
    }
    
    for i in0.. <(array.count - 1) {var min = I // the last position in the ordered regionfor j in(i + 1)... (array.count-1) {// Notice the boundary, which is traversed to the last oneifarray[min] > array[j] { min = j; // Find the minimum subscript in the unordered region}}ifi ! = min {array.swapat (min, I)}}}Copy the code

Merge sort

Merging means combining two or more ordered sequences into a new ordered sequence. Merge sort refers to the process of recursive decomposition of disordered sequences to be sorted into several ordered self-sequences of roughly equal length and merging ordered sub-sequences into whole ordered sequences.

Ideas:

// merge func merge(array:inout [Int], low:Int, mid:Int, high:Int){ var tempArray = Array<Int>() var indexA = low var indexB = midwhile (indexA < mid) && (indexB < high) {
        if array[indexA] < array[indexB]{
            tempArray.append(array[indexA])
            indexA += 1
        }else{
            tempArray.append(array[indexB])
            indexB += 1
        }
    }
    
    while indexA < mid {
        tempArray.append(array[indexA])
        indexA += 1
    }
    
    while indexB < high{
        tempArray.append(array[indexB])
        indexB += 1
    }
    
    var index = 0
    for item inFunc mergeSort(array:inout [Int], low: Int, high: Int) {array[low] = item index += 1} Int) -> Void { guard array.count > 1else {
        return
    }

    if low + 1 < high {
        
        letmid = (low + high) / 2 mergeSort(array: &array, low: low, high: mid) mergeSort(array: &array, low: mid, high: high) merge(array: &array, low: low, mid: mid, high: Var sortArray = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04] // mergeSort(array: &sortarray, low: 0, high: sortArray.count)Copy the code

Quick sort

Improvements to bubble sorting, often referred to as fast sorting.

Thought: first of all, from the selected row in a sequence of a record, called a pivot, through the comparison of keywords and pivot to be sorted before and after the sequence is divided into the pivot of two sequences, before the pivot of the subsequence of all keywords is not greater than the pivot, subsequence of the armature after all the key words of not less than the pivot; At this point, the pivot is in place, and then the two sub-sequences are sorted recursively in the same way to make the whole sequence orderly.

Func partiton(array:inout [Int], low: Int, high: func partiton(array:inout [Int], low: Int, high: Int) -> Int {var left = low, right = highletX = array[low] // Set pivot repeat{// Left and right move alternately from both ends of the sequence to the middlewhile(array[right] > x) && (left < right) {while(array[left] <= x) && (left <= right) {ifLeft < right {array.swapat (left, right)}}whileLeft < right // Pivot to correct positioniflow ! Array. swapAt(low, right) // Switch the pivot to the last number of the left ordered region, which is the right position}returnFunc quickSort (array:inout [Int], low: Int, high: Int) -> Void {guard array.count > 1else {
        return
    }
    
    ifLow < high {// The length is greater than 1letpivot = partiton(array: &array, low: low, high: high) quickSort(array: &array, low: low, high: QuickSort (array: &array, low: pivot + 1, high: Var sortArray = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04] // quickSort(array: &sortArray, low: 0, high: sortArray.count-1)Copy the code

Heap sort

Idea: First, build a big top heap to make the top node of the heap maximum; Swap the top node and the end node of the heap, and the heap length is reduced by 1 (that is, the maximum records are sorted in place); Then adjust the remaining nodes to the heap to get the sub-large value node; Repeat this process to get an ascending sequence.

/ / / heap sort
/ / screening pile
func shiftDown(array:inout Array<Int>,i:Int,length:Int) -> Void {
    var i = i;
    let temp = array[i];// Save the current element
    var k = 2*i + 1 // Since the root of the array is 0, the left child is numbered +1
    
    while k < length {// Start with the left child
        if((k+1 < length) && (array[k] < array[k+1])){// If the left child is smaller than the right child, k points to the right child
            k += 1;
        }
        if(array[k] > temp) {// If the child is larger than the parent, assign the child to the parent (without swapping).
            array[i] = array[k];
            i = k;
        } else {
            break;
        }
        k = k*2 + 1
    }
    
    array[i] = temp;// Put the temp value in the final position
}
func makeHeap(array:inout Array<Int>) -> Void {
    for i in (0. (array.count/2-1)).reversed() {
        // Adjust the structure from bottom to top and from right to left from the first non-leaf node
        shiftDown(array: &array, i: i, length: array.count)}}func heapSort(array:inout Array<Int>) -> Void {
    guard array.count > 1 else {
        return
    }
    
    // Build the big top heap
    makeHeap(array: &array)
    
    // Adjust heap filter + swap top and end heap elements
    for j in (1. (array.count-1)).reversed() {
        array.swapAt(0, j)// Swap the top element with the end element
        shiftDown(array: &array, i: 0, length: j)// Refilter the heap}}Copy the code