标签归档:golang

基础算法——排序【一】

  排序可以说时最基础的算法之一,排序就是将数据按照某种逻辑重新排列的过程,比如从大到小排序、从小到大排序;排序非常常见比如有购物车物品的排序、历史订单的排序等等;算法我们比较关心的主要有两点:时间复杂度空间复杂度,排序算法一样;这篇文章只介绍几种基本的排序算法:冒泡排序插入排序选择排序

选择排序

  算法逻辑上分为已排序未排序两个区间,从当前列表中选择最小的元素与当前列表第一个元素交换位置,从列表剩余元素中找到最小元素与列表第二个元素交换位置如此重复执行的算法为选择排序算法;
  选择排序与数据的初始状态无关,每次查找最小元素值时都会与数组中元素进行交换位置,因此选择排序为非稳定排序算法,在各种情况下算法时间复杂度都为O(n2),空间复杂度为O(n);

 func SelectionSort(data [] int) {
     n := len(data)
     if n <= 1 {
         return
     }
     for i := 0; i < n; i++ {
         //最小元素索引
         min := i
         for j := i + 1; j < n; j++ {
             if data[j] < data[min] {
                 min = j
             }
         }
         //交换元素,交换后未已排序数据
         data[i], data[min] = data[min], data[i]
     }
 }

插入排序

  与选择排序类似在逻辑上列表分为已排序和未排序两个区间,初始时已排序区间未为左边第一个元素,插入排序的核心为从右边未排序区间中选择元素插入到左边合适的位置,直到已排序列表长度等于原始列表长度;插入排序算法的关键步骤为元素比较与元素的移动,当从未排序端拿数据插入到已排序端时已排序端可能会存在大量的数据移动;
  与选择排序不同的是列表初始状态对插入排序的性能影响很大,当列表初始状态有序度很高时插入排序并不需要大量移动数据,从中可以看出插入排序为原地排序算法、算法是稳定的
  算法最好情况下时间复杂度为:O(n)、平均、最坏复杂度为:O(n2);

 func InsertionSort(data [] int) {
          n := len(data)
          for i := 1; i < n; i++ {
              value := data[i]
              //查找插入位置
              var j int
              for j = i - 1; j >= 0; j-- {
                  if data[j] > value {
                      //数据后移
                      data[j+1] = data[j]
                  } else {
                      break
                  }
              }
              data[j+1] = value
          }
 }

冒泡排序

  每次比较相邻两个元素是否满足,否则交换相邻两个元素,每次冒泡至少一个元素移动到它所属位置,重复N次完成列表排序;
  冒泡操作核心为项链元素交换,空间复杂度为O(1),为原地排序算法;算法是稳定的,最好情况时间复杂度为为O(n),平均与最坏情况时间复杂度为:O(n2);

 func BubbleSort(data [] int) {
     n := len(data)
     for i := 0; i < n; i++ {
         //是否有数据交换,用于当某轮中数据已排序时退出循环
         flag := false
         for j := 0; j < n-1-i; j++ {
             if data[j] > data[j+1] {
                 //冒泡
                 data[j], data[j+1] = data[j+1], data[j]
                 flag = true
             }
         }
         if !flag {
             break
         }
     }
      }

基础排序算法特性

enter image description here

参考资料: 《算法四》

再回首数据结构—链表

  链表与数组一样同为线性数据结构,不少编程语言也自带了链表的实现,链表可以存放不同数据类型的数据;
  与数组不同,数组占用内存结构必须为连续,而链表则不需要内存空间为连续的;链表由多个节点连接而成,每个节点除了存储当前节点的值外还存有指向链表中下一个节点的地址;链表也有多种结构:单链表、双向链表、循环链表等等;
  单链表的数据结构如下所示:

enter image description here

  通过上图可以看出链表的基本结构,每个节点由值与地址两部分组成,地址存储链中下一个节点的地址,由此将所有 节点串联起来;

链表的优势

  相比数组不需要连续的内存空间,系统存在内存碎片也可使用链表;
  如需要申请200MB大小的数组,但当前内存中没有足够大连续的内存空间,就算当前可用内存有200MB也不会申请成功;
  而链表则不同,只要可用内存有200MB就可使用,不需要内存块为连续的它通过指针将节点(内存块)串联起来;
  之前所说的动态数组其实只是伪动态当静态数组满时通过内部的resize创建一个新静态数组进行扩容,而链表为真动态;

  1、 数组插入删除
  数组为保持内存的连续性插入删除需要移动N个元素,时间复杂度为O(n)
  2、 链表插入删除
  链表未使用连续内存空间则也不需要移动元素,所以速度会比数组快不少;
  由于链表使用的不时连续存储空间,所以不能像数组一样通过寻址公式就能访问到指定的元素,需要通过一个一个遍历每个节点才能找到对应的节点,所以数组的随机访问时间复杂度为O(1),而链表为O(n);

enter image description here

插入删除 O(n) O(1) 随机访问 O(1) O(n)

链表插入与删除

  链表的插入与删除比数组快不少,链表并非使用连续的内存空间,不需要去维护内存连续性,就插入与删除而言双向链表又比单链表性能要好;

  要在节点c后插入O节点,需要从第一个节点开始遍历链表知道找到节点c然后执行如下操作:

enter image description here

 O.next = c.next
 c.next = O

  删除节点d需要找到该节点的前一个节点,找到节点c后执行如下操作:

enter image description here

 c.next = d.next
 d.next = null

  由于单链表只存储下一个节点地址需要遍历链表节点才能找到前一个节点,而双向链表既存储了下一个节点地址又存储上一个节点地址,双向链表性能比单链表要好;

链表要点

  1、如上面所说的插入元素在c节点后插入O节点,操作时需要注意要先执行O指向c的下一个节点,当一上来就执行c.next=O此时链表c节点后的节点就断开丢失了;
  2、链表删除时需要注意要释放节点,如上示例:执行c.next=d.next后如未执行d.next=null此时d节点就未被释放掉,虽然链表中未有节点指向该节点,但该节点并未断开连接;
  3、使用头节点简化插入、删除操作;

下面为使用Golang实现的链表

 type Node struct {
    e    interface{}
    next *Node
 }
 type LinkedList struct {
    head *Node
    size int
 }

 /**
 往链表头添加元素
  */
 func (l *LinkedList) AddFirst(e interface{}) {
    l.Add(0, e)
 }

 func (l *LinkedList) Add(index int, e interface{}) error {
    if index < 0 || index > l.size {
        return errors.New("Add failed. Illegal index.")
    }
    prev := l.head
    for i := 0; i < index; i++ {
        prev = prev.next
    }
    prev.next = &Node{e: e, next: prev.next}
    l.size++
    return nil
 }

 /**
 nil->3  2  1
 查找指定索引节点
  */
 func (l *LinkedList) Find(index int) *Node {
    cur := l.head.next
    for i := 0; i < index; i++ {
        cur = cur.next
    }
    return cur
 }

 /**
 删除指定位置节点
  */
 func (l *LinkedList) Remove(index int) error {
    node := l.head.next
    if node != nil {
        if prev := l.Find(index - 1); prev != nil {
            node = prev.next
            if node != nil {
            prev.next = node.next
            node.next = nil
        }
    }
}
return nil
 }