常见排序算法及应用

这里是一些常见的排序方法和它们的分析，可能也有应用，也可能有图

工具类

我们先拿出一些常用的方法，简化一下用在后面的调用：

function less(a, i, j) {
    return a[i] < a[j];
}

function swap(a, i, j) {
    const temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

选择排序

选择排序的思路是每次从未排序的部分中寻找最小的一个，把它放在已排序部分的末尾。

使用js实现如下：

function selectionSort(a) {
    for(let i = 0; i < a.length - 1; i ++) {
        let minIndex = i;
        for(let j = i + 1; j < a.length; j ++) {
            if(less(a, j, minIndex)) {
                minIndex = j;
            }
        }
        swap(a, i, minIndex);
    }
}

下一步 重置 自动

开始

插入排序

希尔排序

归并排序

快速排序

快速排序的一个简单实现：

选取最左一个值作为中心，把比它小的值挪到它左边，其余在右边，然后对它分成的两个部分使用快速排序。

用Js实现如下：

function quicksort(array, low, high) {
    if(low >= high) {
        return;
    }
    let lt = low, gt = high;
    const pivot = array[low];
    while(true) {
        while(array[++lt] < pivot && lt != high);
        while(array[--gt] > pivot);

        if(lt <= gt) {
            swap(array, lt, gt);
        }else {
            break;
        }
    }
    swap(array, low, gt);
    quicksort(array, low, lt - 1);
    quicksort(array, lt + 1, high);
}

但这不是一个好的实现。快速排序当面对一串已经排序的数据时，每次都把剩余部分分成了$0$和$当前长度-1$的两部分，最终能跑出~$\frac{1}{2}N^2$的时间来。

我们可以通过一个shuffle函数在$N$时间内把它打乱，但是当面对一串一模一样的数据时，依然是快排的最坏情况。如果待排序的数据中存在大量的重复，快排的效率就会下降。

因此我们可以通过将相同的数据都放在一起的方式来做一些改进，这个改进技术叫3 way partitioning.

冒泡排序

冒泡排序的思想是，（假设需要升序排列）从第一个数开始，不停比较相邻的两个数，将大的放在右边，一轮过后最大的数会到数组的最右边。第二轮则是从第一个数到倒数第二个数……

如果需要加快一下跳出可以加上一个flag, 如果一轮中没有出现交换，说明排序已经完成了，可以不再继续.

下面是一个go的版本:(只留function)

func bubbleSort(originalList []int32) {
	for i := 0; i < len(originalList)-1; i += 1 {
		switched := false
		for j := 0; j < len(originalList)-i-1; j += 1 {
			if originalList[j] > originalList[j+1] {
				temp := originalList[j+1]
				originalList[j+1] = originalList[j]
				originalList[j] = temp
				switched = true
			}
		}
		if ! switched {
			break
		}
	}
}

冒泡排序效果如下：

下一步 重置 自动