sort algorithm

发表于： 2021-03-22 分类于： algorithm

字数：3234 阅读：≈ 7分钟浏览：

排序算法复杂度

冒泡排序

将第一个数A跟第二个数B相比较，如果A>B，那么交换A，B位置，接下来将第二个数跟第三个数比较

func bubbleSort(array []int) {
    length := len(array)
    for i := 0; i < length; i++ {
    	for j := 0; j < length-1-i; j++ {
    		if (array[j] > array[j+1]) {
    			array[j], array[j+1] = array[j+1], array[j]
    		}
    	}
    }
}

第一次遍历, n-1这个数已经有序,第i次遍历，n-1-i后续数已经有序。外围for循环判断式可改为 i <lenght-1,因为当i=length-1时,只剩下第0个数本身，不需要再比较冒泡排序第一次执行，arr[n-1]为最大数值,较大的数不断往后冒泡。第i次排序后，[n-i, n-1]有序,如果在第i次中没有发生交换，那么说明整个序列已经有序

func bubbleSort(array []int) {
length := len(array)
for i := 0; i < length; i++ {
	flag := false
	for j := 0; j < length-1-i; j++ {
		if (array[j] > array[j+1]) {
			array[j], array[j+1] = array[j+1], array[j]
			flag = true
		}
	}
	if !flag {
		break
	}
}

第i次排序后，[n-i, n-1]有序,如果第i次排序中,在[lastPos, n-i]也没有发生交换，那么说明[lastPos, n-1]已经有序，下次循环区间可由[0, n-i-1]变为[0, n-lastPos-1]，缩小了循环空间

func bubbleSort(array []int) {
    length := len(array)
    for i := 0; i < length; i++ {
    	flag := false
    	lastPos := i
    	tmp := 0
    	for j := 0; j < length-1-lastPos; j++ {
    		if (array[j] > array[j+1]) {
    			array[j], array[j+1] = array[j+1], array[j]
    			flag = true
    			tmp = j
    		}
    	}
    	lastPos = tmp
    	if !flag {
    		break
    	}
    }
}

插入排序

向一个已经排序的序列中插入一个新值

func insertSort(array []int) {
    length := len(array)
    for i := 1; i < length; i++ {
    	j := i-1
    	for ; j >= 0; j-- {
    		if array[j] > array[j+1] {
    			array[j], array[j+1] = array[j+1], array[j]
    		}
    	}
    }
}

插入排序时间复杂度: 1 + 2 + … + n = O(n^2),空间复杂度O(1)。它的平均时间复杂度、最差复杂度、最好复杂度都是一样的。在排序过程中，如果数组元素不与排序规则一致，会导致大量元素交换。对于数组形式没有优化，如果元素以链表形式，那么可以将索引记住，在合适的地方才插入

希尔排序

将整个待排序的记录序列分割成为若干个子序列分别进行直接插入排序错误实现：

func shellSort(array []int) {
    length := len(array)
    d := length / 2
    for ; d > 0; d /= 2 {
    	i := d
    	for ; i < length; i += d {
    		j := i - d
    		for ; j >=0; j -=d {
    			if array[j] > array[j+d] {
    				array[j], array[j+d] = array[j+d], array[j]
    			}
    		}
    	}
    }
}

上述实现仅是在插入排序前增加了部分元素的交换，没有运用到分组思想正确实现：

func shellSort(array []int) {
    length := len(array)
    d := length / 2
    for ; d > 0; d /= 2 {
    	i := d
    	for ; i < length; i ++ {
    		j := i - d
    		for ; j >=0; j -=d {
    			if array[j] > array[j+d] {
    				array[j], array[j+d] = array[j+d], array[j]
    			}
    		}
    	}
    }
}

选择排序

在一个序列中搜索最小的数，在排除此数的序列中搜索最小的数，如此反复
```
func selectSort(array []int) {
    length := len(array)
    for i := 0; i < length; i++ {
    	minIndex := i
    	for j := i+1; j < length; j++ {
    		if array[minIndex] > array[j] {
    			minIndex = j
    		}
    	}
    	array[i], array[minIndex] = array[minIndex], array[i] }
}
```
选择排序是不稳定的，在交换时相对顺序会更改，例如序列(5, 5, 2, 3)

堆排序

2-路归并排序

归并排序时一个分治法典型应用，将已有序的子序列合并，得到完全有序的序列。将长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的序列边界条件确定：当子序列有且仅有一个元素时，直接返回子序列

func merge(array []int, low, mid, high int) {
	var tmp []int
	i, j := low, mid
	for ; i <= mid && j <= high; {
		if (array[i] < array[j]) {
			tmp = append(tmp, array[i])
			i++
		} else if (array[i] > array[j]) {
			tmp = append(tmp, array[j])
			j++
		} else {
			tmp = append(tmp, array[i])
			tmp = append(tmp, array[j])
			i++
			j++
		}
	}
	if i > mid {
		tmp = append(tmp, array[j:]...)
	}
	if j > high {
		tmp = append(tmp, array[i:mid+1]...)
	}
	if high-low+1 != len(tmp) {
		printArray(array)
		println(low)
		println(mid)
		println(high)
	}
	for k := 0; k < len(tmp); k++ {
		array[low] = tmp[k]
		low++
	}
}
func mergeSort(array []int, low, high int) {
	if low >= high {
		return
	}
	mid := (high + low) / 2
	mergeSort(array, low, mid)
	mergeSort(array, mid+1, high)
	merge(array, low, mid, high)
}

在第一遍实现时，没有注意到merge合并的条件必须时[low,mid]和[mid+1,high]

func merge(array []int, low, mid, high int) {
    var tmp []int
    i, j := low, mid+1
    for ; i <= mid && j <= high; {
		if (array[i] < array[j]) {
			tmp = append(tmp, array[i])
			i++
		} else if (array[i] > array[j]) {
			tmp = append(tmp, array[j])
			j++
		} else {
			tmp = append(tmp, array[i])
    			tmp = append(tmp, array[j])
    			i++
    			j++
    		}
    	}
    	if i > mid && j <= high{
    		tmp = append(tmp, array[j:high+1]...)
    	}
    	if j > high && i <= mid {
    		tmp = append(tmp, array[i:mid+1]...)
    	}
    	fmt.Println("--------------------------------")
    	fmt.Println(array[low:high+1])
    	fmt.Println(low, mid, high)
    	fmt.Println(tmp)
    	fmt.Println("--------------------------------")
    for k := 0; k < len(tmp); k++ {
    	array[low] = tmp[k]
    	low++
    }
}   

    func mergeSort(array []int, low, high int) {
        if low >= high {
            return
        }
        mid := (high + low) / 2
        mergeSort(array, low, mid)
        mergeSort(array, mid+1, high)
        merge(array, low, mid, high)
    }

快速排序

快速排序同样时运用分治法来排序。从序列中挑出一个元素，称为基准；小于基准值的元素放在左边，大于则放在右边，得到两个序列和一个基准值；对子序列做同样工作；当子序列仅有1个元素或0个时，结束

func quicSort(array []int, l, r int) {
    if l >= r {
	    return
	}
	i, j := l, r
	pviot := array[l]
	for ; i <= j; {
		for ; i < j && array[i] <= pviot; i++ {
		}
		for ; i < j && array[j] > pviot; j-- {
		}
		if i < j {
			array[i], array[j] = array[j], array[i]
            i++
		    j--
		} else {
			break
		}
		
	}
	array[i], array[l] = array[l], array[i]
	fmt.Println("-------------------------------")
	printArray(array)
	fmt.Println(i, j, l, r)
	fmt.Println("-------------------------------")
	quicSort(array, l, i-1)
	quicSort(array, i+1, r)
}

上述算法思路：以pviot（array[l])为基准，从左找小于或等于pviot的数，找到后记下索引i值；从右找大于pviot的数,找到后记下索引j值；如果i < j，那么交换i,j的值；如果 i找到或j找到，但另一个没有找到，此时i==j，跳出循环,将i,l对应值互换（显然，这一步时错误的，如果找到j但没找到i，互换后pviot值左边有一个比它大的数）。那么，找到索引i值，k := l, 将arr[k] = arr[i]; k = i，留下空位k，找到索引j值，arr[k] = arr[j]; k = j, 索引k一直在区间[i, j]中变动，直到i == j，此时 k == i,将 arr[k] = pviot。之后再快排左右两个子序列。(必须从右边寻找起，因为开始k起始值在左边)

func quicSort(array []int, l, r int) {
	if l >= r {
		return
	}
	i, j := l, r
	k := l
	pviot := array[l]
	fmt.Println("++++++++++++++++++++++++++++++++")
	fmt.Println(i, j, k, pviot)
	for ; i < j; {
		for ; i < j && array[j] > pviot; j-- {
		}
		if i < j {
			array[k] = array[j]
			k = j
			j--
		}
		fmt.Println(array[l:r+1])
		for ; i < j && array[i] <= pviot; i++ {
		}
		if i < j {
			array[k] = array[i]
			k = i
			i++
		}
		fmt.Println(array[l:r+1])
	}
	fmt.Println("++++++++++++++++++++++++++++++++")
	array[k] = pviot
	fmt.Println("----------------------------")
	fmt.Println(k, i, j)
	fmt.Println(pviot)
	printArray(array)
	fmt.Println("----------------------------")
	quicSort(array, l, k-1)
	quicSort(array, k+1, r)
}

上述算法{10, 4, 3}通过,{10, 4, 7,2, 13, 89, 4, 3}没有通。实验数据对比得出，k值变动并不会一直在区间[i,j]，这是因为每次交换数值时，k值会被移动到区间外，发现i < j条件改为 i < k可能可行，理论推导不可行，k值变动中会有如下情况{14, 89, 3}这个序列中k = 0, j = 2, 于是k, j 交换对应值, k=2,此时元素89不能被移动到k值右边。脑已经有些乱了，推倒重新开始实现

func quickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	//分子序列
	pviot := arr[left]
	i, j := left+1, right
	for ;i < j; {
		for ; i < j && arr[i] <= pviot; i++ {
		}
		for ; i < j && arr[j] > pviot; j-- {
		}
		if i < j {
			arr[i], arr[j] = arr[j], arr[i]
			i++
			j--
		}
	}
	if arr[i] <= pviot {
		arr[left], arr[i] = arr[i], arr[left]
	} else {
		for k := left; k < i-1; k++ {
			arr[k] = arr[k+1]
		}
		i = i-1
		arr[i] = pviot
	}
	quickSort(arr, left, i-1)
	quickSort(arr, i+1, right)
}

上述实现正确，但i==j这个元素处理会导致过多的数组移动，能否在一开始就将数组移动，那么必须利用空位pviot

k := left
for ;i < j; {
	for ; i < j && arr[i] <= pviot; i++ {
	}
	for ; i < j && arr[j] > pviot; j-- {
	}
	if i < j {
		arr[k] = arr[j]
		arr[j] = arr[i]
		k = i
		i++
		j--
	}
}

使用k表示空位索引，如果从左找起，找到的i==j值远离k，一样存在区间[k, i]的移动；所以需要从右开始找起,同样会存在[k, i]区间，那么从一遍找起

func quickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	//分子序列
	pviot := arr[right]
	i := left-1
	for j := left; j <= right-1; j++ {
		if arr[j] < pviot {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i+1], arr[right] = arr[right], arr[i+1]
	quickSort(arr, left, i)
	quickSort(arr, i+2, right)
}

上述实现如果将pviot := arr[left], j := left+1，此实现如下：

func quickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	//分子序列
	pviot := arr[left]
	i := left
	for j := left+1; j <= right; j++ {
		if arr[j] < pviot {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i+1], arr[left] = arr[left], arr[i+1]
	quickSort(arr, left, i)
	quickSort(arr, i+2, right)
}

i+1 这一步有可能 i == right,导致数组溢出请参考 https://www.cnblogs.com/sunriseblogs/p/10009890.html

20201214

插入排序

void insertSort(int arr[], int n) {
    for(int i = 0; i < n-1; i++) {
        int j = i;
        int tmp = arr[j+1];
        for(; j >= 0; j--) {
            if(tmp >= arr[j]) {
                break;
            }
            arr[j+1] = arr[j];
        }
        arr[j+1] = tmp;
        print(arr, n);
    }
}

归并排序

void merge(int arr[], int low, int mid, int high) {
    int *tmp = new int[high-low+1];
    int i = low, j = mid + 1;
    int k = 0;
    for(; i <= mid && j <= high;) {
        if(arr[i] < arr[j]) {
            tmp[k++] = arr[i++];
        } else if(arr[i] > arr[j]) {
            tmp[k++] = arr[j++];
        } else {
            tmp[k++] = arr[i++];
            tmp[k++] = arr[j++];
        }
    }

    while(i <= mid) {
        tmp[k++] = arr[i++];
    }

    for(int i = low, j = 0; j < k; i++,j++) {
        arr[i] = tmp[j];
    }
}

void mergeSort(int arr[], int low, int high) {
    if(low >= high) {
        return;
    }
    int mid = low + (high - low)/2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid+1, high);
    merge(arr, low, mid, high);
}

快速排序

void Qsort(int arr[], int low, int high) {
    if(high <= low) return;
    int i = low, j = high + 1;
    int key = arr[low];

    while(true) {
        while(arr[++i] < key) {
            if (i == high) {
                break;
            }
        }

        while(arr[--j] > key) {
            if(j == low) {
                break;
            }
        }
        if(i >= j) {
            break;
        }
        swap(arr[i], arr[j]);
    }
    swap(arr[j], arr[low]);
    Qsort(arr, low, j-1);
    Qsort(arr, j+1, high);
}

冒泡排序

void bulbSort(int arr[], int n) {
    int i = 0;
    int len = n-1;
    for(; i < n; i++) {
        int flag = true;
        int tmp;
        for(int j = 0; j < len; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                flag = false;
                tmp = j;
            }
        }
        len = tmp;
        if(flag) {
            break;
        }
    }
}

基数排序

void radixSort(int *arr, int n) {
    int maxBit = 2;
    for(int i = 0; i < maxBit; i++) {
        int buf[10][100] = {0};
        int pow = 1;
        for(int j = 0 ; j < i; j++) {
            pow *= 10;
        }
        for(int i = 0; i < n; i++) {
            int index = (arr[i] / pow) % 10;
            for (int j = 0; j < 100; j++) {
                if (buf[index][j] == 0) {
                    buf[index][j] = arr[i];
                    break;
                }
            }
        }

        for(int i = 9, k = 0; i >= 0; i--) {
            for(int j = 0; j < 100; j++) {
                if(buf[i][j] != 0) {
                    arr[k++] = buf[i][j];
                }
            }
        }
    }
}

Reference

十大经典排序算法(动图演示): https://www.cnblogs.com/onepixel/articles/7674659.html
冒泡排序的改进: https://blog.csdn.net/tjunxin/article/details/8711389
归并排序的递归和迭代解法：https://zhuanlan.zhihu.com/p/124356219
https://www.geeksforgeeks.org/quick-sort/
快速排序: https://mp.weixin.qq.com/s/9JScICC2Tgz8vd4OPCzFqQ
跳跃表: https://mp.weixin.qq.com/s/XY1gPvdV7hWTDYNDDW2zoQ
希尔排序: https://www.cnblogs.com/chengxiao/p/6104371.html