Go语言的冒泡排序算法以及分治法求出逆序数_冒泡排序可以分治法吗

        冒泡排序应该算是大家学习算法的入门第一课了，很好理解，类似湖面看到的水泡，因为体积轻，然后就从下面慢慢往上浮起来。

比如数组[33, 8, 12, 7, 6]，我们在第一轮比较之后，会发现最大数沉底了，第二轮比较之后，第二大的数字也沉到倒数第二的位置了，一直进行下去，相反的小的数也就慢慢的浮上来了。

[8 12 7 6 33]
[8 7 6 12 33]
[7 6 8 12 33]
[6 7 8 12 33]

5个数字经过4轮之后，排序就做好了，代码很简单，两个for循环，外循环就是0到4，内循环就是随着每一轮递减一次循环即可，因为每一轮已经将大的数字放到后面了，已排好序，就不需要再次比较了。 

冒泡算法

package main
 
import "fmt"
 
func bubbleSort(arr []int) []int {
	len := len(arr) - 1
	for i := 0; i < len; i++ {
		for j := 0; j < len-i; j++ {
			//如果比相邻的大就交换位置
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}
 
func main() {
	arr1 := []int{33, 8, 12, 7, 6}
	arr2 := make([]int, len(arr1))
	copy(arr2, arr1)
	arr3 := bubbleSort(arr2)
	fmt.Printf("%v=>%v\n", arr1, arr3) //[33 8 12 7 6]=>[6 7 8 12 33]
	fmt.Printf("%p,%p", arr1, arr3)    //0xc00000e3f0,0xc00000e420
}

另外为了更清晰的表示前后数组(切片)的变化，使用了copy深拷贝，这种拷贝可以拷贝里面的值，如果是arr2:=arr1这样的赋值，是一种浅拷贝，也就是说拷贝的是引用，是一个地址，共享同一地址，这样你修改了arr1也会修改arr2

冒泡求逆序数

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数
逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。 如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。

那求逆序数的方法通过冒泡来实现就很简单了，也是两个循环，里面循环是第一轮从一个元素开始与后面元素一个一个比较，如果比后面的大就加1做个计数，第二轮从第二个元素开始与后面元素分别一一的去比较，一直这样循环完毕，就把逆序数统计出来了

package main
 
import "fmt"
 
func bubbleSort(arr []int) int {
	cnt := 0
	len := len(arr) - 1
	for i := 0; i < len; i++ {
		for j := i; j < len; j++ {
			if arr[i] > arr[j+1] {
				cnt = cnt + 1
			}
		}
	}
	return cnt
}
 
func main() {
	arr := []int{5, 3, 6, 2, 1, 4}
	arr2 := bubbleSort(arr)
	fmt.Printf("%v的逆序数：%v\n", arr, arr2)
}

[5 3 6 2 1 4]的逆序数：10  

Go分治法求逆序数

冒泡法虽然简单直观，但是其时间复杂度比较高 ：O(n^2)。
我们先来看一个快速但比较复杂点的计算方法是在归并排序的同时计算逆序数，采用分治法其时间复杂度为O(nlogn) C++版本：高级排序求逆序数之分治法 可以看出分治法其实属于递归变化的一种高级排序。
使用Golang语言来实现，这里我们将使用到切片类型，代码如下：

package main
 
import (
	"fmt"
)
 
func merge_count(A []int, B []int) (int, []int) {
	/*
	   合并且做了排序并统计逆序数
	       A列表的值大于B列表的值，就做统计,将B的值(小)添加到C列表
	       A列表的值小于B列表的值，就将A的值(小)添加到C列表
	   A和B列表是递归切割出来的
	   比较剩余之后的值添加到C列表
	*/
	lenA := len(A)
	lenB := len(B)
	i := 0
	j := 0
	rC := 0
	var C []int
	for i < lenA && j < lenB {
		if A[i] > B[j] {
			C = append(C, B[j])
			j += 1
			rC += lenA - i
		} else {
			C = append(C, A[i])
			i += 1
		}
	}
	if i < lenA {
		C = append(C, A[i:]...) //切片添加元素需要解包
	}
	if j < lenB {
		C = append(C, B[j:]...)
	}
	return rC, C
}
 
func sort_count(L []int) (int, []int) {
	/*
	   递归的切割，然后做合并
	*/
	if len(L) == 1 {
		return 0, L
	} else {
		rA, A := sort_count(L[0 : len(L)/2])
		rB, B := sort_count(L[len(L)/2:])
		rC, C := merge_count(A, B) //想明白程序的运行，这里可以做个断点查看
		return rA + rB + rC, C
	}
}
func main() {
	//A := []int{5, 3, 6, 2, 1, 4}
	A := []int{11, 5, 3, 6, 2, 9, 1, 4}
	fmt.Printf("%v", A)
	cnt, arr := sort_count(A)
	fmt.Printf("的逆序数：%v,%v", cnt, arr)
}

[5 3 6 2 1 4]的逆序数：10,[1 2 3 4 5 6]

[11 5 3 6 2 9 1 4]的逆序数：19,[1 2 3 4 5 6 9 11]

Python分治法求逆序数

对Golang不是很了解其语法的，可以先看下Python的方法，思想都是一样的，也就是说算法跟语言没有关系，不同的语言主要在于语法的区别，看个人的习惯。
这里用到的是列表，所以数据结构和算法还是核心，需要慢慢积累，另外不同语言的语法就是靠平时写代码过程中的注意和备注

def merge_count(A,B):
    '''
    合并且做了排序并统计逆序数
        A列表的值大于B列表的值，就做统计,将B的值(小)添加到C列表
        A列表的值小于B列表的值，就将A的值(小)添加到C列表
    A和B列表是递归切割出来的
    比较剩余之后的值添加到C列表
    '''
    lenA,lenB=len(A),len(B)
    i,j,rC=0,0,0
    C=[]
    while(i<lenA and j<lenB):
        if A[i]>B[j]:
            C.append(B[j])
            j+=1
            rC+=lenA-i
        else:
            C.append(A[i])
            i+=1
    if i<lenA:
        C=C+A[i:]
    if j<lenB:
        C=C+B[j:]
    return (rC,C)
 
 
def sort_count(L):
    '''
    递归的切割，然后做合并
    '''
    if len(L)==1:
        return (0,L)
    else:
        (rA,A)=sort_count(L[0:len(L)//2])
        (rB,B)=sort_count(L[len(L)//2:])
        (rC,C)=merge_count(A,B)#想明白程序的运行，这里可以做个断点查看
        return (rA+rB+rC,C)
 
L=[11,5,3,6,2,9,1,4]
print(sort_count(L))
#(19, [1, 2, 3, 4, 5, 6, 9, 11])