基本排序算法

学习笔记,以下代码部分拷贝的维基百科，见链接

时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。 时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

公式：
$$
\lim_{n\rightarrow+\infty} \frac{T(n)}{f(n)} = C(C为不为零的常数)
$$
C一般是算法中最大的语句频度，是最内层循环语句的执行次数。

基本排序算法

图片from: 数据结构常见的八大排序算法

直接插入排序

是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到**O(1)**的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

//JavaScript
function straightInsertSort(arr){
    let len = arr.length;
    
    for(let i = 1; i < len; i++){ //第一个元素无需排序
        let j = i - 1,
            value = arr[i];
        
        while(j>=0 && arr[j] > value){
            arr[j+1] = arr[j];
            j--;
        }
        
        arr[j+1] = value;
    }
}

希尔算法

在插入直接排序的基础上使用分组

//JavaScript
function shellSort(arr){
    let len = arr.length;
    
    for(let step = Math.floor(len / 2); step > 0; step = Math.floor(step / 2)){
         for(let i = 1; i < len; i++){
            let j = i - step,
                value = arr[i];

            while(j>=0 && arr[j] > value){
                arr[j+step] = arr[j];
                j -= step;
            }

            arr[j+step] = value;
        }
    }
}

选择排序

（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

图示：

//script
function selectSort(arr){
    if(!Array.isArray(arr)) return;
    let len = arr.length;
    
    for(let i = 0;i < len - 1; i++){
        let min = i;
        for(let j = i + 1; j < len; j++){
            if(arr[min] > arr[j])
                min = j;
        }
        
      let temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
    }
}

堆排序

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

图示：

function heapSort(arr) {
	var arr = arr.slice(0);
	function swap(i, j) {
		var tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	function max_heapify(start, end) {
		//建立父節點指標和子節點指標
		var dad = start;
		var son = dad * 2 + 1;
		if (son >= end)//若子節點指標超過範圍直接跳出函數
			return;
		if (son + 1 < end && arr[son] < arr[son + 1])//先比較兩個子節點大小，選擇最大的
			son++;
		if (arr[dad] <= arr[son]) {//如果父節點小於子節點時，交換父子內容再繼續子節點和孫節點比較
			swap(dad, son);
			max_heapify(son, end);
		}
	}

	var len = arr.length;
	//初始化，i從最後一個父節點開始調整
	for (var i = Math.floor(len / 2) - 1; i >= 0; i--)
		max_heapify(i, len);
	//先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢
	for (var i = len - 1; i > 0; i--) {
		swap(0, i);
		max_heapify(0, i);
	}
};

冒泡排序

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢「浮」到数列的顶端。

图示：

function bubbleSort(arr) {
    let i, j, temp,
        length = arr.length;
    for (i = 0; i < length - 1; i++){
        for (j = 0; j < length - 1 - i; j++){
                        if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
};

运行源码

Change The World

基本排序算法

时间复杂度

基本排序算法

直接插入排序

希尔算法

选择排序

堆排序

冒泡排序

参考