最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

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

来源:博客园

冒泡排序(Bubble Sort)

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

算法步骤:

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

伪代码:


(资料图)

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 swappedend procedure

选择排序(Selection Sort)

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

算法步骤:

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

伪代码:

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 forend procedure

插入排序(Insertion Sort)

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

算法步骤:

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

伪代码:

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 forend procedure

希尔排序(Shell Sort)

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

算法步骤:

  1. 确定分组间隔gap的大小(最开始可以设为数组长度的一半)。
  2. 按照gap的大小将原始数组分为若干个子序列。
  3. 对每个子序列进行插入排序。
  4. 缩小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 whileend procedure

归并排序(Merge Sort)

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

算法步骤:

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

伪代码:

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 ifend procedureprocedure 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 whileend procedure

快速排序(Quick Sort)

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

算法步骤:

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

伪代码:

procedure quickSort(array A, left, right)if left < right thenpivot := partition(A, left, right)quickSort(A, left, pivot-1)quickSort(A, pivot+1, right)end ifend procedurefunction partition(A, left, right)pivot := A[left]i := left + 1j := rightwhile 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 ifend whileswap(A[left], A[j])return jend function

堆排序(Heap Sort)

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

算法步骤:

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

伪代码:

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 ifend procedureprocedure buildMaxHeap(A, heapSize)    for i from floor(heapSize/2) down to 1 do        maxHeapify(A, i, heapSize)    end forend procedureprocedure 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 forend procedureend function

计数排序(Counting Sort)

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

算法步骤:

  1. 找到原始数组的最大值max。
  2. 初始化一个长度为max的计数数组C,对每个元素统计它出现的次数。
  3. 对计数数组C进行累加,得到C的新数组D。
  4. 从右到左遍历原始数组,根据元素在计数数组D中的位置,将元素插入到新数组R中的合适位置。
  5. 返回新数组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 Rend procedure

桶排序(Bucket Sort)

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

算法步骤:

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

伪代码:

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 Rend procedure

基数排序(Radix Sort)

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

算法步骤:

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

伪代码:

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 Aend procedurefunction 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 functionfunction getDigit(num, i)    return mod(floor(num / power(10, i-1)), 10)end function

关键词: