排序算法

冒泡排序

1
2
3
4
5
6
def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

选择排序

1
2
3
4
5
6
7
8
9
10
11
def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

插入排序

1
2
3
4
5
6
7
8
9
def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def insertion_sort(bucket):
    for i in range(1, len(bucket)):
        key = bucket[i]
        j = i - 1
        while j >= 0 and key < bucket[j]:
            bucket[j + 1] = bucket[j]
            j -= 1
        bucket[j + 1] = key

def bucket_sort(arr, bucket_size=None):
    if not arr:
        return arr

    min_value, max_value = min(arr), max(arr)

    default_bucket_size = 5
    bucket_size = bucket_size or default_bucket_size
    bucket_count = (max_value - min_value) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        buckets[(num - min_value) // bucket_size].append(num)

    arr.clear()
    for bucket in buckets:
        insertion_sort(bucket)
        arr.extend(bucket)

    return arr

arr_to_sort = [29, 10, 14, 37, 13]
sorted_arr = bucket_sort(arr_to_sort)
print(sorted_arr)

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def radix_sort(arr, max_digit):
    mod, dev = 10, 1
    for i in range(max_digit):
        counter = [[] for _ in range(10)]
        for num in arr:
            bucket = (num % mod) // dev
            counter[bucket].append(num)
        
        pos = 0
        for bucket in counter:
            if bucket:
                while bucket:
                    arr[pos] = bucket.pop(0)
                    pos += 1

        mod *= 10
        dev *= 10

    return arr

# 示例
arr_to_sort = [329, 457, 657, 839, 436, 720, 355]
max_digit = len(str(max(arr_to_sort)))  # 获取最大数字的位数
sorted_arr = radix_sort(arr_to_sort, max_digit)
print(sorted_arr)

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
func fibonacii(c1, c2 chan int) {
	x, y := 1, 1
	for {
		select {
		case c1 <- x:
			x, y = x+y, x
		case <-c2:
			fmt.Println("quit")
			return
		}
	}

}

反转字符串

JS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function sort(str) {
    var arr = str.split("");
    var len = arr.length;
    var loop = Math.floor(len / 2);

    for (let i = 0; i < loop; i++) {
        let temp = arr[i];
        arr[i] = arr[len - 1 - i];
        arr[len - 1 - i] = temp;
    }

    str = arr.join(""); 
    console.log(str);
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
func reverse(str string) string {
	runes := []rune(str)
	len := len(runes)
	loop := len / 2

	for i := 0; i < loop; i++ {
		runes[i], runes[len-1-i] = runes[len-1-i], runes[i]
	}

	return string(runes)
}

Python

1
2
3
4
5
6
7
8
9
10
def reverse_string(s):
    chars = list(s)
    length = len(chars)
    loop = length // 2

    for i in range(loop):
        chars[i], chars[length - 1 - i] = chars[length - 1 - i], chars[i]

    return ''.join(chars)

B+树

结点的定义

首先给出B+树结点的定义，在此叶子结点与索引结点使用了相同的数据结构：

1
2
3
4
5
6
7
8
9
10
type BPItem struct {
    Key     int64
    Val     interface{}
}
type BPNode struct {
    MaxKey    int64
    Nodes     []*BPNode
    Items     []BPItem
    Next     *BPNode
}

其中：

  • BPItem用于数据记录。
  • MaxKey：用于存储子树的最大关键字
  • Nodes：结点的子树（叶子结点的Nodes=nil）
  • Items：叶子结点的数据记录（索引结点的Items=nil）
  • Next：叶子结点中指向下一个叶子结点，用于实现叶子结点链表

B+树的定义

1
2
3
4
5
type BPTree struct {
    mutex      sync.RWMutex
    root      *BPNode
    width     int
    halfw     int

其中：

  • root：指向B+树的根结点
  • width：用于表示B+树的阶
  • halfw：用于[M/2]=ceil(M/2)

B+树的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func NewBPTree(width int) *BPTree {
    if width < 3 {
        width = 3
    }
    var bt = &BPTree{}
    bt.root = NewLeafNode(width)
    bt.width = width
    bt.halfw = (bt.width + 1) / 2
    return bt
}

//申请width+1是因为插入时可能暂时出现节点key大于申请width的情况,待后期再分裂处理
func NewLeafNode(width int) *BPNode {
    var node = &BPNode{}
    node.Items = make([]BPItem, width+1)
    node.Items = node.Items[0:0]
    return node
}

B+树的查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (t *BPTree) Get(key int64) interface{} {
    t.mutex.Lock()
    defer t.mutex.Unlock()

    node := t.root
    for i := 0; i < len(node.Nodes); i++ {
        if key <= node.Nodes[i].MaxKey {
            node = node.Nodes[i]
            i = 0
        }
    }

    //没有到达叶子结点
    if len(node.Nodes) > 0 {
        return nil
    }

    for i := 0; i < len(node.Items); i++ {
        if node.Items[i].Key == key {
            return node.Items[i].Val
        }
    }
    return nil
}

B+树的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func (t *BPTree) Set(key int64, value interface{}) {
    t.mutex.Lock()
    defer t.mutex.Unlock()
    t.setValue(nil, t.root, key, value)
}
func (t *BPTree) setValue(parent *BPNode, node *BPNode, key int64, value interface{}) {
    for i:=0; i < len(node.Nodes); i++ {
        if key <= node.Nodes[i].MaxKey || i== len(node.Nodes)-1 {
            t.setValue(node, node.Nodes[i], key, value)
            break
        }
    }

    //叶子结点，添加数据
    if len(node.Nodes) < 1 {
        node.setValue(key, value)
    }

    //结点分裂
    node_new := t.splitNode(node)
    if node_new != nil {
        //若父结点不存在，则创建一个父节点
        if parent == nil {
            parent = NewIndexNode(t.width)
            parent.addChild(node)
            t.root = parent
        }
        //添加结点到父亲结点
        parent.addChild(node_new)
    }
}

代码中使用递归调用实现数据的插入。插入时首先定位到叶子结点，然后调用 BPNode.setValue()来设置关键字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func (node *BPNode) setValue(key int64, value interface{}) {
    item := BPItem{key, value}
    num := len(node.Items)
    if num < 1 {
        node.Items = append(node.Items, item)
        node.MaxKey = item.Key
        return
    } else if key < node.Items[0].Key {
        node.Items = append([]BPItem{item}, node.Items...)
        return
    } else if key > node.Items[num-1].Key {
        node.Items = append(node.Items, item)
        node.MaxKey = item.Key
        return
    }

    for i:=0; i < num; i++ {
        if node.Items[i].Key > key {
            node.Items = append(node.Items, BPItem{})
            copy(node.Items[i+1:], node.Items[i:])
            node.Items[i] = item
            return
        } else if node.Items[i].Key == key {
            node.Items[i] = item
            return
        }
    }
}

添加关键字后若数量超过：BPTree.width，则需要调用 BPNode.splitNode()来进行结点分裂处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func (t *BPTree) splitNode(node *BPNode) *BPNode {
    if len(node.Nodes) > t.width {
        //创建新结点
        halfw := t.width / 2 + 1
        node2 := NewIndexNode(t.width)
        node2.Nodes = append(node2.Nodes, node.Nodes[halfw : len(node.Nodes)]...)
        node2.MaxKey = node2.Nodes[len(node2.Nodes)-1].MaxKey

        //修改原结点数据
        node.Nodes = node.Nodes[0:halfw]
        node.MaxKey = node.Nodes[len(node.Nodes)-1].MaxKey

        return node2
    } else if len(node.Items) > t.width {
        //创建新结点
        halfw := t.width / 2 + 1
        node2 := NewLeafNode(t.width)
        node2.Items = append(node2.Items, node.Items[halfw: len(node.Items)]...)
        node2.MaxKey = node2.Items[len(node2.Items)-1].Key

        //修改原结点数据
        node.Next = node2
        node.Items = node.Items[0:halfw]
        node.MaxKey = node.Items[len(node.Items)-1].Key

        return node2
    }

    return nil
}

B+树的删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func (t *BPTree) Remove(key int64) {
    t.mutex.Lock()
    defer t.mutex.Unlock()
    t.deleteItem(nil, t.root, key)
}
func (t *BPTree) deleteItem(parent *BPNode, node *BPNode, key int64) {
    for i:=0; i < len(node.Nodes); i++ {
        if key <= node.Nodes[i].MaxKey {
            t.deleteItem(node, node.Nodes[i], key)
            break
        }
    }

    if  len(node.Nodes) < 1 {
        //删除记录后若结点的子项<m/2，则从兄弟结点移动记录，或者合并结点
        node.deleteItem(key)
        if len(node.Items) < t.halfw {
            t.itemMoveOrMerge(parent, node)
        }
    } else {
        //若结点的子项<m/2，则从兄弟结点移动记录，或者合并结点
        node.MaxKey = node.Nodes[len(node.Nodes)-1].MaxKey
        if len(node.Nodes) < t.halfw {
            t.childMoveOrMerge(parent, node)
        }
    }
}

代码中使用递归调用实现删除操作。删除时首先定位到叶子结点，若找到则调用 BPNode.deleteItem()来删除关键字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (node *BPNode) deleteItem(key int64) bool {
    num := len(node.Items)
    for i:=0; i < num; i++ {
        if node.Items[i].Key > key {
            return false
        } else if node.Items[i].Key == key {
            copy(node.Items[i:], node.Items[i+1:])
            node.Items = node.Items[0:len(node.Items)-1]
            node.MaxKey = node.Items[len(node.Items)-1].Key
            return true
        }
    }
    return false
}

删除关键字后，若关键字的数量小于BPTree.halfw，则需要调用BPNode.itemMoveOrMerge()函数。
BPNode.itemMoveOrMerge()函数首先获取兄弟结点，并判断是否可以借用关键字，若可以进行关键字借用，否则与兄弟结点进行合并：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func (t *BPTree) itemMoveOrMerge(parent *BPNode, node *BPNode) {
    //获取兄弟结点
    var node1 *BPNode = nil
    var node2 *BPNode = nil
    for i:=0; i < len(parent.Nodes); i++ {
        if parent.Nodes[i] == node {
            if i < len(parent.Nodes)-1 {
                node2 = parent.Nodes[i+1]
            } else if i > 0 {
                node1 = parent.Nodes[i-1]
            }
            break
        }
    }

    //将左侧结点的记录移动到删除结点
    if node1 != nil && len(node1.Items) > t.halfw {
        item := node1.Items[len(node1.Items)-1]
        node1.Items = node1.Items[0:len(node1.Items)-1]
        node1.MaxKey = node1.Items[len(node1.Items)-1].Key
        node.Items = append([]BPItem{item}, node.Items...)
        return
    }

    //将右侧结点的记录移动到删除结点
    if node2 != nil && len(node2.Items) > t.halfw {