排序算法-N个正整数排序

算法

高德纳在《计算机程序设计艺术》里对算法归纳为以下几点：

1. 输入: 一个算法必须有零或以上的输入量
2. 输出: 一个算法应有一个或以上的输出量
3. 明确性: 算法的描述必须无歧义,实际运行结果是确定的
4. 有限性: 必须在有限个步骤内结束
5. 有效性: 又称可行性,能够被执行者实现

如果想详细研究算法推荐《数据结构与算法分析》

定义问题

数组array含有N个正整数
输入量为array
请将array中的数字从小到大排列
输出量为排好序的数组

代码例子

var array = [5,2,4,6,8]
function sort(){
   你的代码
}
sort(array) === [2,4,5,6,8]

当你遇到思路障碍怎么办?

• 将抽象的问题转化为具体的问题
• 将没见过的问题转化为见过的问题

排序算法

所有算法都可在此查看演示

冒泡排序(BUBBLE)

重复地比较要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。比较数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。每比较一整轮,最大的都会出现在最后故名---冒泡排序

流程如下:

1. 我们拿到一个数组
   
2. 开始从前两个开始比较,发现44>3,所以不用交换
   
3. 接着往后比较,发现38<44,所以交换他们两个的位置
   
4. 以此类推直到第一轮结束,我们得到了最大的那一个----50(冒的第一个泡)
   
5. 接着下一轮,又从头开始两个两个地比较,重复第一轮,我们就得到了第二个最大的------48
   
6. 如此进行多轮比较我们会得到一个从小到大的数组
   
7. 代码实现：

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

2. 选择排序(SELECT)

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
流程如下:

1. 拿到一个数组
   
2. 我们要选出这个数组中最小的元素然后把它和第一个数交换(放到最前面),所以我们先认为3为最小,然后和后面的数依次进行比较.
   
3. 当比到2的时候,我们发现3>2,所以我们就认为2为最小值,后面的数应该都和2进行比较.
   
4. 当比较完所有的元素,确定2为最小值的时候,把最小值也就是2与第一个元素的位置互换.
   
5. 然后从第二个元素开始新一轮的比较,过程和第一轮一样.把44看做最小值和后面的元素进行比较.
   
6. 经过多轮比较得到从小到大的数组.
   
7. 代码实现

function selectSort(arr) {
    var minIndex, temp;
    for (let i = 0; i < arr.length - 1; i++) {
        minIndex = i; // 先把第一个看做最小值
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

3, 插入排序(INSERT)

将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。是稳定的排序方法。
流程如下:

1. 拿到一个数组
   
2. 把第一个元素看做一个新数组,然后把第二个元素依次和新数组的元素进行比较(虽然只有一个...),然后插入到适当的位置.
   
   
3. 然后以此类推,把前两个元素看做是一个新数组,然后把第三个元素依次与新数组进行比较,然后插入到适当的位置.
   
   
4. 把剩下的元素依次插入,最后得到从小到大排列的数组.
   
5. 代码实现

function insertionSort(array) {
    for (let i = 1; i < array.length; i++) {
        let key = array[i];
        let j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
    return array;
}

4. 归并排序(MERGE)

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
流程如下:

1. 拿到一个数组
   
2. 我们把数组平均分成左右两部分,得到两个新数组,然后再把每个数组平均分成两部分,一直分到每个数组只有两个元素,然后比较第一组
   
3. 因为3<44所以位置不变然后比较第二组,因为38>5所以调换位置.
   
4. 重点来了,这个时候先不着急比较第三组而是把排好序的一二两组放在一起排序.
   
5. 之后就是比较第三组和第四组,然后同样把他们放在一起排好序.
   
6. 然后并不是比较第五组和第六组,而是把第一组和第二组产生的新数组和,第三组和第四组产生的新数组放在一起排序成为新数组.
   
7. 同样把剩下的按以上步骤重来一遍.我们得到两个排好序的数组.然后给这两个数组排序就完成了.
   
   排序后:
   
8. 代码实现

function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());
    while (right.length)
        result.push(right.shift());

    return result;
}

5. 快速排序

每个元素找到自己对应的位置(前面的都比我小,后面的都比我大)
流程如下:

1. 拿到一个数组
   
2. 拿第一个元素和后面的元素进行比较,找出所有比第一个元素小的元素,放在第一个元素的右边然后把第一个元素与这些比他小的元素的最后一个互换.
   
   
3. 前两个元素的位置已经没错了,然后以第三个元素为标准,和后面的元素进行比较.
   
4. 把比他小的元素放在他的右边(绿色),然后让它和绿色的最后一个交换位置.
   
5. 然后从左边没有确定位置的元素(非橙色)开始以上步骤----也就是19
   
6. 一直到所有元素的位置都正确.
   
7. 代码实现

function quickSort(array) {
    function quick(array, left, right) {
        let index;
        if (array.length > 1) {
            index = partition(array, left, right);
            if (left < index - 1) {
                quick(array, left, index - 1);
            }
            if (index < right) {
                quick(array, index, right);
            }
        }
        return array;
    }
    function partition(array, left, right) {
        const pivot = array[Math.floor((right + left) / 2)];
        let i = left;
        let j = right;
    
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                [array[i], array[j]] = [array[j], array[i]]
                i++;
                j--;
            }
        }
        return i;
    }
    quick(array, 0, array.length - 1);
};

6. 随机快速排序

顾名思义,就是在快速排序的基础上,加入随机的机制.
在快速排序的时候我们是从左到右来选取比较对象,在随机快速排序中我们是随机来选取对象.
流程如下:

1. 拿到一个数组
   
2. 随机选择一个元素.
   
3. 并且把比他小的放在他的右边
   
4. 然后把他和比他小的最右边的元素交换位置
   
5. 然后在随机选一个元素,重复步骤,知道所有元素都是在正确的位置上.
   
6. 代码实现

function quickSort(array) {
    function quick(array, left, right) {
        let index;
        if (array.length > 1) {
            index = partition(array, left, right);
            if (left < index - 1) {
                quick(array, left, index - 1);
            }
            if (index < right) {
                quick(array, index, right);
            }
        }
        return array;
    }
    function partition(array, left, right) {
        const pivot = array[Math.floor(Math.random()*array.length)];
        let i = left;
        let j = right;
    
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                [array[i], array[j]] = [array[j], array[i]]
                i++;
                j--;
            }
        }
        return i;
    }
    quick(array, 0, array.length - 1);
};