排序算法图文讲解（php，javascript，java）

大湿们常说，程序=算法+数据结构！砖家门的资料也介绍的非常详细，但是，比如小白我来讲，看的还是昏昏欲睡的感觉。尼玛！就不能简单些吗？我想，各位攻城师和程序猿们也大抵如此吧

首先，就从 排序算法走起！

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等

排序算法分类

一般分为两大类

• 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

• 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 

排序算法时间与空间复杂度

下面我们来细讲一下

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。

js实现：

function insertSort (arr) {
    if (!Array.isArray(arr) || arr.length < 2) {
        return arr
    }
    for (let i = 1; i < arr.length; i++) {
        for (let j = i; j >= 0; j--) {
            if (arr[j + 1] < arr[j]) {
                let swap = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = swap
            }
        }
    }
    return arr
}

php实现

function insertSort($arr){
    if(count($arr)<2){
        return $arr;
    }
    for($i=1;$i=0&&$temp<$arr[$j];$j--){
            $arr[$j+1]=$arr[$j];
        }
        $arr[$j+1]=$temp;
    }
    return $arr;
}
var_dump(insertSort([8,3,2,10,1]));

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤：

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

选择排序

选择排序(Selection sort)也是一种简单直观的排序算法。

算法步骤：

1）首先在未排序序列中找到最小元素，存放到排序序列的起始位置

2）再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。

3）重复第二步，直到所有元素均排序完毕。

js实现

/**
 *@param arr {Array}
 *@return {Array}
 */
function selectSort(arr) {
    let minIndex,temp;
    let len = arr.length;
    for (let i = 0; i < len-1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }

        }
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
    return arr;
}

Java实现：

public int[] selectSort2(int[] arr){
    int pos;
    for(int i=0;i<arr.length;i++){        pos=i;
        int temp=arr[i];
        int j=i+1;
        for(;j< arr.length&&arr[j]<temp;j++){            temp=arr[j];
            pos=j;
        }
        arr[pos]=arr[i];
        arr[i]=temp;
    }
    return arr;
}

php实现：

function selectSort($arr){
    $pos=0;
    for($i=0;$i<count($arr);$i++){
        $temp=$arr[$i];
        $j=$i+1;
        for(;$j<count($arr);$j++){
            if($arr[$j]<$temp){
                $temp=$arr[$j];
                $pos=$j;
            }
        }
        $arr[$pos]=$arr[$i];
        $arr[$i]=$temp;
    }
    return $arr;
}
var_dump(selectSort([8,3,2,10,1]));

冒泡排序

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

算法步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 js实现

function bubbleSort(arr) {
    if(arr&&arr instanceof Array &&arr.length>1){
        for(let i=0;i<arr.length-1;i++){
            for(let j=0;j<arr.length-i;j++){
                if(arr[j]<arr[j-1]){
                    let tem=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tem;

                }
            }
        }
    }
    return arr;
}

快速排序

12个小球，其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。

这个问题是一道流传已久的智力题。网络上也有很多讲解，还有泛化到N个球的情况下的严格证明。也有零星的一些地方提到从信息论的角度来看待最优解法。本来我一直认为这道题目除了试错之外没有其它高妙的思路了，只能一个个方法试，并尽量从结果中寻找信息，然后看看哪种方案最少。

然而，实际上它的确有其它的思路，一个更本质的思路，而且根本用不着信息论这么拗口的知识。

关于快速排序，推荐阅读《数学之美番外篇：快排为什么那样快》

js实现：

/**
 *
 * @param arr {Array}
 * @return {Array}
 */


function quickSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivotItem = arr.splice(pivotIndex, 1)[0];
    let left = [], right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] <= pivotItem) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat([pivotItem], quickSort(right));

}

图解快速排序步骤

归并排序:

解析:归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

js实现：

/**
 *
 * @param arr {Array}
 * @return {Array}
 */

function mergeSort(arr) {
    if(arr.length<2){
        return arr;
    }
    let pivotIndex=Math.floor(arr.length/2);
    let leftArr=arr.slice(0,pivotIndex);
    let rightArr=arr.slice(pivotIndex);

    return merge(mergeSort(leftArr),mergeSort(rightArr));
}
/**
 * @param leftArr {Array}
 * @param rightArr {Array}
 * @return {Array}
 */
function merge(leftArr,rightArr) {
    let result=[];
    while (leftArr.length&&rightArr.length){
        if(leftArr[0]<rightArr[0]){
            result.push(leftArr.shift())
        }else {
            result.push(rightArr.shift())
        }
    }

    return result.concat(leftArr,rightArr);
}

图解归并排序步骤

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率

• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时，再对全体记录进行依次直接插入排序。

算法步骤：

1. 选择一个增量序列t1，t2，……，tk，其中ti>tj，tk=1；

2. 按增量序列个数k，对序列进行k 趟排序；

3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

这个一下子讲不完，所以单独开一篇：《再谈希尔排序——看图理解希尔排序算法》

转载本站文章《排序算法图文讲解（php，javascript，java）》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/1.html