GoGo

算法：优化冒泡排序

2018-10-23  本文已影响3人  小码侠

之前我们已经聊过 冒泡排序 ，但是当我们的元素列表中如果存在了一批已经排好序的数据，冒泡排序还是会坚挺的执行下去。造成资源的浪费，针对这种情况我们来优化一下。

如需要对以下数据排序：

{5, 2, 4, 3, 1, 6 ,7 ,8 ,9 ,10 }

原始冒泡排序效果

第 1 次

  1. [2 5 4 3 1 6 7 8 9 10]
  2. [2 4 5 3 1 6 7 8 9 10]
  3. [2 4 3 5 1 6 7 8 9 10]
  4. [2 4 3 1 5 6 7 8 9 10]
  5. [2 4 3 1 5 6 7 8 9 10]
  6. [2 4 3 1 5 6 7 8 9 10]
  7. [2 4 3 1 5 6 7 8 9 10]
  8. [2 4 3 1 5 6 7 8 9 10]
  9. [2 4 3 1 5 6 7 8 9 10]

第 2 次

  1. [2 4 3 1 5 6 7 8 9 10]
  2. [2 3 4 1 5 6 7 8 9 10]
  3. [2 3 1 4 5 6 7 8 9 10]
  4. [2 3 1 4 5 6 7 8 9 10]
  5. [2 3 1 4 5 6 7 8 9 10]
  6. [2 3 1 4 5 6 7 8 9 10]
  7. [2 3 1 4 5 6 7 8 9 10]
  8. [2 3 1 4 5 6 7 8 9 10]

第 3 次

  1. [2 3 1 4 5 6 7 8 9 10]
  2. [2 1 3 4 5 6 7 8 9 10]
  3. [2 1 3 4 5 6 7 8 9 10]
  4. [2 1 3 4 5 6 7 8 9 10]
  5. [2 1 3 4 5 6 7 8 9 10]
  6. [2 1 3 4 5 6 7 8 9 10]
  7. [2 1 3 4 5 6 7 8 9 10]

第 4 次

从第四次开始，排序已经没有效果了。

  1. [1 2 3 4 5 6 7 8 9 10]
  2. [1 2 3 4 5 6 7 8 9 10]
  3. [1 2 3 4 5 6 7 8 9 10]
  4. [1 2 3 4 5 6 7 8 9 10]
  5. [1 2 3 4 5 6 7 8 9 10]
  6. [1 2 3 4 5 6 7 8 9 10]

第 5 次

  1. [1 2 3 4 5 6 7 8 9 10]
  2. [1 2 3 4 5 6 7 8 9 10]
  3. [1 2 3 4 5 6 7 8 9 10]
  4. [1 2 3 4 5 6 7 8 9 10]
  5. [1 2 3 4 5 6 7 8 9 10]

第 6 次

  1. [1 2 3 4 5 6 7 8 9 10]
  2. [1 2 3 4 5 6 7 8 9 10]
  3. [1 2 3 4 5 6 7 8 9 10]
  4. [1 2 3 4 5 6 7 8 9 10]

第 7 次

  1. [1 2 3 4 5 6 7 8 9 10]
  2. [1 2 3 4 5 6 7 8 9 10]
  3. [1 2 3 4 5 6 7 8 9 10]

第 8 次

  1. [1 2 3 4 5 6 7 8 9 10]
  2. [1 2 3 4 5 6 7 8 9 10]

第 9 次

  1. [1 2 3 4 5 6 7 8 9 10]

优化后效果

第 1 次

  1. [2 5 4 3 1 6 7 8 9 10]
  2. [2 4 5 3 1 6 7 8 9 10]
  3. [2 4 3 5 1 6 7 8 9 10]
  4. [2 4 3 1 5 6 7 8 9 10]
  5. [2 4 3 1 5 6 7 8 9 10]
  6. [2 4 3 1 5 6 7 8 9 10]
  7. [2 4 3 1 5 6 7 8 9 10]
  8. [2 4 3 1 5 6 7 8 9 10]
  9. [2 4 3 1 5 6 7 8 9 10]

第 2 次

  1. [2 4 3 1 5 6 7 8 9 10]
  2. [2 3 4 1 5 6 7 8 9 10]
  3. [2 3 1 4 5 6 7 8 9 10]

第 3 次

  1. [2 3 1 4 5 6 7 8 9 10]
  2. [2 1 3 4 5 6 7 8 9 10]

第 4 次

  1. [1 2 3 4 5 6 7 8 9 10]

代码实现

package main

import "fmt"

func main() {
    //声明数组
    numbers := []int{5, 2, 4, 3, 1, 6, 7, 8, 9, 10}
    length := len(numbers)
    lastSwap := length
    count:=0
    //构建遍历循环
    for i := 0; i < length-1; i++ {
        fmt.Printf("**第 %d 次**\n\n", count+1)
        count++
        for j := 0; j < length-i-1; j++ {
            //fmt.Println(i,j)
            //对比两个相邻元素
            if numbers[j] > numbers[j+1] {
                //如果如果第一个比第二个大，就交换它们的位置。 【顺序】
                //倒序反之：如果第一个比第二个小，就交换它们的位置。
                numbers[j+1], numbers[j] = numbers[j], numbers[j+1]
                //记录最后交换的位置。因为从零开始，所以加1
                lastSwap = j+1
            }
            fmt.Printf("%d. %v\n", j+1, numbers)
        }
        fmt.Println("")
        //如果长度和最后位置不匹配，意味着还有数据进行交换。
        if length!=lastSwap {
            length = lastSwap //交换位置。
            i=-1 //重置外层循环，因为接下来会有`i++`，所以设置为 `-1`
        }
    }
}

PHP

<?php
$numbers = array(5, 2, 4, 3, 1, 6, 7, 8, 9, 10);
$len = count($numbers);
$last = $len;
//构建遍历循环
for ($i = 0; $i < $len - 1; $i++) {
    for ($j = 0; $j < $len - $i - 1; $j++) {
        //对比两个相邻元素
        if ($numbers[$j] > $numbers[$j + 1]) {
            //如果如果第一个比第二个大，就交换它们的位置。 【顺序】
            //倒序反之：如果第一个比第二个小，就交换它们的位置。

            list($numbers[$j + 1], $numbers[$j]) = array($numbers[$j], $numbers[$j + 1]);
            $last = $len;
        }
    }

    //如果长度和最后位置不匹配，意味着还有数据进行交换。
    if ($last != $len) {
        $len = $last;
        $i = -1;//重置外层循环，因为接下来会有`i++`，所以设置为 `-1`
    }
}

print_r($numbers);
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
    [8] => 9
    [9] => 10
)
 */

JS

let numbers = [5, 2, 4, 3, 1, 6, 7, 8, 9, 10];
let len = numbers.length;
let last = len;
//构建遍历循环
for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - i - 1; j++) {
        //对比两个相邻元素
        if (numbers[j] > numbers[j + 1]) {
            //如果如果第一个比第二个大，就交换它们的位置。 【顺序】
            //倒序反之：如果第一个比第二个小，就交换它们的位置。

            //解构交换位置
            [numbers[j + 1], numbers[j]] = [numbers[j], numbers[j + 1]];
            last = j + 1;
        }
    }
    if (last != len) {
        len = last;
        i = -1;
    }
}
console.log(numbers);
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

Python

# -*- coding: UTF-8 -*-
numbers = [5, 2, 4, 3, 1, 6, 7, 8, 9, 10]
length = len(numbers)
last = length
while 1 == 1:
    swapFlag = False # 记录是否交换过
    for i in range(length - 1):
        for j in range(length - i - 1):
            """
            如果如果第一个比第二个大，就交换它们的位置。 【顺序】
            倒序反之：如果第一个比第二个小，就交换它们的位置。
            """
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                last = j + 1
                swapFlag = True
        if length != last:
            length = last
            break
    if not swapFlag: # 已经没有数据可以交换了。直接退出。
        break
print(numbers)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

微信搜索：小码侠

长按二维码关注我们
上一篇下一篇

猜你喜欢

热点阅读