【技术积累】算法中的排序算法【一】

255 0 0

作者:TianYou

冒泡排序（Bubble Sort）

算法描述：通过不断地交换相邻两个元素，把最大的元素移到数组的最后面，然后不断缩小排序范围，直到整个数组有序。

算法步骤：

遍历整个待排序的数组。
比较相邻的两个元素。
如果前面的元素比后面的元素大，就交换它们
重复以上步骤，直到整个数组有序。

伪代码：

procedure bubbleSort(array A)
    n := length(A)
    repeat
        swapped := false
        for i from 1 to n-1 do
            if A[i] > A[i+1] then
                swap(A[i], A[i+1])
                swapped := true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

选择排序（Selection Sort）

算法描述：对于一组待排序的元素，先找到最小元素，然后把它放到第一位，接着再找到次小元素，放到第二位，依次类推，直到所有的排序工作都已经完成。

算法步骤：

找到数组中最小元素并记录其位置。
把最小元素放在数组的起始位置。
从下一个元素开始，重复以上步骤，直到整个数组有序。

伪代码：

procedure selectionSort(array A)
    n := length(A)
    for i from 1 to n-1 do
        minIndex := i
        for j from i+1 to n do
            if A[j] < A[minIndex] then
                minIndex := j
            end if
        end for
        swap(A[i], A[minIndex])
    end for
end procedure

插入排序（Insertion Sort）

算法描述：将一个记录插入到已经排好的有序序列中，从而得到一个新的，记录数增加1的有序序列。

算法步骤：

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果被扫描的元素大于新元素，将该元素往右移动一个位置。
重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
将新元素插入到该位置后。
重复以上步骤，直到整个数组有序。

伪代码：

procedure insertionSort(array A)
    n := length(A)
    for i from 2 to n do
        key := A[i]
        j := i - 1
        while j > 0 and A[j] > key do
            A[j+1] := A[j]
            j := j - 1
        end while
        A[j+1] := key
    end for
end procedure

希尔排序（Shell Sort）

算法描述：将原始数组按照一定的间隔分为若干子序列，然后对每个子序列进行插入排序，直到整个数组排序完成。

算法步骤：

确定分组间隔gap的大小（最开始可以设为数组长度的一半）。
按照gap的大小将原始数组分为若干个子序列。
对每个子序列进行插入排序。
缩小gap的大小，重复以上步骤，直到gap为1时，整个数组排序完成。

伪代码：

procedure shellSort(array A)
    n := length(A)
    gap := n / 2
    while gap > 0 do
        for i from gap to n-1 do
            temp := A[i]
            j := i
            while j >= gap and A[j-gap] > temp do
                A[j] := A[j-gap]
                j := j - gap
            end while
            A[j] := temp
        end for
        gap := gap / 2
    end while
end procedure

归并排序（Merge Sort）

算法描述：将原始数组分成若干个较小的子数组，对每个子数组进行排序，然后再将排好序的子数组合并成一个大的有序数组。

算法步骤：

把长度为n的数组分成两个长度为n/2的子数组。
对这两个子数组分别进行归并排序。
将排好序的两个子数组合并成一个大的有序数组。

伪代码：

procedure mergeSort(array A)
    n := length(A)
    if n > 1 then
        mid := n / 2
        left := A[1..mid]
        right := A[mid+1..n]
        mergeSort(left)
        mergeSort(right)
        merge(left, right, A)
    end if
end procedure

procedure merge(left, right, A)
    i := 1
    j := 1
    k := 1
    
    while i <= length(left) and j <= length(right) do
        if left[i] <= right[j] then
            A[k] := left[i]
            i := i + 1
        else
            A[k] := right[j]
            j := j + 1
        end if
        k := k + 1
    end while
    
    while i <= length(left) do
        A[k] := left[i]
        i := i + 1
        k := k + 1
    end while
    
    while j <= length(right) do
        A[k] := right[j]
        j := j + 1
        k := k + 1
    end while
end procedure

快速排序（Quick Sort）

算法描述：将原始数组分为两个子数组，其中一个子数组的所有元素都比另一个子数组的元素小，再递归地对两个子数组进行快速排序，直到整个数组有序。

算法步骤：

从数组中取一个基准元素（通常选择第一个元素）。
把数组中小于基准元素的元素放在基准元素左边，大于基准元素的元素放在基准元素右边。
对基准元素左右两个子集递归地进行快速排序。

伪代码：

procedure quickSort(array A, left, right)
if left < right then
pivot := partition(A, left, right)
quickSort(A, left, pivot-1)
quickSort(A, pivot+1, right)
end if
end procedure


function partition(A, left, right)
pivot := A[left]
i := left + 1
j := right


while true do
    while i <= j and A[i] < pivot do
        i := i + 1
    end while
    while i <= j and A[j] > pivot do
        j := j - 1
    end while
    
    if i <= j then
        swap(A[i], A[j])
    else
        break
    end if
end while

swap(A[left], A[j])
return j

end function

堆排序（Heap Sort）

算法描述：将原始数组看成一个完全二叉树，并将其调整为大根堆，然后将根节点（即最大值）与最后一个节点交换位置，缩小排序范围，重复以上步骤，直到整个数组有序。

算法步骤：

将原始数组调整为大根堆。
将堆顶元素（即最大元素）与最后一个叶子节点交换位置。
对减少一个元素的堆进行调整，使其重新成为一个大根堆。
重复以上步骤，直到整个数组有序。

伪代码：

procedure maxHeapify(A, i, heapSize)
    left := 2 * i
    right := 2 * i + 1
    largest := i
    
    if left <= heapSize and A[left] > A[largest] then
        largest := left
    end if
    
    if right <= heapSize and A[right] > A[largest] then
        largest := right
    end if
    
    if largest != i then
        swap(A[i], A[largest])
        maxHeapify(A, largest, heapSize)
    end if
end procedure

procedure buildMaxHeap(A, heapSize)
    for i from floor(heapSize/2) down to 1 do
        maxHeapify(A, i, heapSize)
    end for
end procedure

procedure heapSort(A)
    heapSize := length(A)
    buildMaxHeap(A, heapSize)
    
    for i from heapSize downto 2 do
        swap(A[1], A[i])
        heapSize := heapSize - 1
        maxHeapify(A, 1, heapSize)
    end for
end procedure
end function

计数排序（Counting Sort）

算法描述：对于有限的数列，使用一个全新的数列记录它们的出现次数，再根据出现次数将原始数列排序。

算法步骤：

找到原始数组的最大值max。
初始化一个长度为max的计数数组C，对每个元素统计它出现的次数。
对计数数组C进行累加，得到C的新数组D。
从右到左遍历原始数组，根据元素在计数数组D中的位置，将元素插入到新数组R中的合适位置。
返回新数组R。

伪代码：

procedure countingSort(A)
    max := 0
    for i from 1 to length(A) do
        if A[i] > max then
            max := A[i]
        end if
    end for
    
    C := array(0..max, 0)
    for i from 1 to length(A) do
        C[A[i]] := C[A[i]] + 1
    end for
    
    D := array(0..max, 0)
    for i from 1 to max do
        D[i] := D[i-1] + C[i]
    end for
    
    R := array(1..length(A), 0)
    for i from length(A) downto 1 do
        R[D[A[i]]] := A[i]
        D[A[i]] := D[A[i]] - 1
    end for
    
    return R
end procedure

桶排序（Bucket Sort）

算法描述：将原始数组分为若干个桶，每个桶的元素值范围相同，再对每个桶里的元素进行排序，将所有桶中的元素按顺序依次排列在一起。

算法步骤：

初始化若干个桶，桶的数量等于元素范围的个数。
遍历原始数组中的每个元素，将元素放入相应的桶中。
对每个桶中的元素进行插入排序，使得每个桶内的元素有序。
将所有桶中的元素按顺序依次排列在一起。

伪代码：

procedure bucketSort(A)
    n := length(A)
    buckets := array(length(A))
    
    for i from 1 to n do
        bucketIndex := ceil(A[i] * n / max(A))
        buckets[bucketIndex] := append(buckets[bucketIndex], A[i])
    end for
    
    for i from 1 to length(buckets) do
        insertionSort(buckets[i])
    end for
    
    R := concatenate all buckets
    return R
end procedure

基数排序（Radix Sort）

算法描述：将原始数组按照数位进行比较和排序，先比较最低位，然后依次向上比较，直到比较完最高位。

算法步骤：

从最低位开始，按照数位进行比较
对比较之后的元素按顺序排列。
将已经排好序的元素从原始数组中删除，并将它们按照排序顺序依次插入到新的数组中。
重复以上步骤，直到处理完最高位。

伪代码：

procedure radixSort(A)
    maxDigit := getMaxDigit(A)
    
    for i from 1 to maxDigit do
        buckets := array(0..9, empty array)
        for j from 1 to length(A) do
            digit := getDigit(A[j], i)
            buckets[digit] := append(buckets[digit], A[j])
        end for
        A := concatenate all buckets
    end for
    
    return A
end procedure

function getMaxDigit(A)
    max := 0
    for i from 1 to length(A) do
        if A[i] > max then
            max := A[i]
        end if
    end for
    return length(toString(max))
end function

function getDigit(num, i)
    return mod(floor(num / power(10, i-1)), 10)
end function

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/yyyyfly1/p/17488609.html

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

【技术积累】算法中的排序算法【一】

【技术积累】算法中的排序算法【一】

冒泡排序（Bubble Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

希尔排序（Shell Sort）

归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（Heap Sort）

计数排序（Counting Sort）

桶排序（Bucket Sort）

基数排序（Radix Sort）

相关课程

热门标签

【技术积累】算法中的排序算法【一】

【技术积累】算法中的排序算法【一】

冒泡排序（Bubble Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

希尔排序（Shell Sort）

归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（Heap Sort）

计数排序（Counting Sort）

桶排序（Bucket Sort）

基数排序（Radix Sort）

相关课程

热门标签

推荐文章