实验一:排序算法性能分析
本文最后更新于 561 天前,其中的信息可能已经有所发展或是发生改变。

冒泡排序

bubble(vec)
	for i 0 to (len(vec) - 1) by 1 do
		// 设置flag为false
		flag ← false

		for j 0 to (len(vec) - 1 - i) by 1 do

			if vec[j] > vec[j + 1]) then
				swap(vec[j], vec[j + 1])
      			// 如果发生交换,设置flag为true
				flag ← true

		end
		// 如果不发生交换,数组有序,退出循环
		if flag = false then
			break

	end

return

选择排序

select(vec)
    left ← 0
    right ← len(vec) - 1

    while left < right do
        min ← left
        max ← right

        for i left to right by 1 do
            // 当指针指向的值小于当前最小值时,进行替换
            if vec[i] < vec[min] then
                min ← i
            // 当指针指向的值大于当前最大值时,进行替换
            if vec[i] > vec[max] then
                max ← i

        end

        swap(vec[left], vec[min])
        swap(vec[right], vec[max])
        left ← left + 1
        right ← right - 1

    end

return

插入排序

insert(vec)
    for i 1 to len by 1 do
        key ← vec[i]
        j ← i - 1
        while (j >= 0) && (key < vec[j]) do
            vec[j + 1] ← vec[j]
            j ← j - 1
        end
        vec[j + 1] ← key;
    end
end

归并排序

sort(vec, min, middle, max)

    for i min to middle by 1 to
        put vec[i] to leftVec
    end
    for j middle to max + 1 by 1 to
        put vec[j] to rightVec
    end

    left_pointer ← 0
    right_pointer ← 0
    pointer ← min

    //执行归并操作
    while left_pointer < len(leftVec) && right_pointer < len(rightVec) do
        if leftVec[left_pointer] > rightVec[right_pointer] then
            vec[pointer++] ← rightVec[right_pointer++]
        else
            vec[pointer++] ← leftVec[left_pointer++]
    end

    //如果左边的数组还没比较完,右边的数都已经完了,那么将左边的数抄到大数组中
    while left_pointer < len(leftVec) do
        put leftVec[left_pointer++] to vec
    end
    //同上,将右边的数抄到大数组中
    ...
end

merge(vec, min, max)
    if min = max then //如果一个数,不用排序
        return

    middle ← (min + max) / 2
    //将其平分为两个无序序列,分别进行排序
    merge(vec, min, middle)
    merge(vec, middle + 1, max)

    //如果最左边的最大值比左右边的最小值还小,则不用排序
    if vec[middle] < vec[middle + 1] then
        return

    //对两个有序序列进行归并排序
    sort(vec, min, middle + 1, max)

end

快速排序

sort(vec, begin, end)
    key ← vec[begin] // 将基准值设置为数组的第一个元素
    while begin < end do
        // 与右边比基准值小的数进行交换
        while begin < end && vec[end] >= key do
            end ← end - 1
        end
        swap(vec[begin], vec[end])

        // 与左边比基准值大的数进行交换
        while begin < end && vec[begin] <= key do
            begin ← end + 1
        end
        swap(vec[begin], vec[end])
    end

    return begin
end

quick(vec, begin, end)
    if begin < end then
        key ← sort(vec, begin, end)
        // 分解
        quick(vec, begin, key - 1)
        quick(vec, key + 1, end)
end

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇