目录

排序相关概念

稳定性

 内部排序

外部排序

 十种排序算法特点总结

交换排序

冒泡排序（数组sort方法的原理）

图解

 js实现

特点

快速排序

图解

js实现

特点

选择排序

直接选择排序

图解

 js实现

特点

堆排序

大（小）顶堆

非叶节点

js实现 

特点

插入排序 

直接插入排序

图解

js实现 

特点

希尔排序

图解

js实现

特点

其它排序

桶排序

图解

js实现

特点

基数排序

图解

js实现

特点

归并排序

图解

 js实现

特点

计数排序

图解

 js实现

特点

---

排序相关概念

稳定性

不改变相同数值的顺序为稳定。例如在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的(记录的相对次序保持不变)；否则称为不稳定的。

 内部排序

指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。有冒泡、选择、插入、希尔、快速、堆排序（通常快速排序为最好的）。

外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。有归并、计数、桶、基数排序。

 十种排序算法特点总结

 

交换排序

冒泡排序（数组sort方法的原理）

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

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

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

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

图解

 js实现

function swap(arr, x, y) 
    let tmp = arr[x]
    arr[x] = arr[y]
    arr[y] = tmp

function bubbleSort(arr) 
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) 
        //比较出一轮中的最大值放入最后
        for (let j = 0; j < len - 1 - i; j++) 
            if (arr[j] > arr[j + 1]) 
                swap(arr, j, j + 1)
            
        
    
    return arr;

特点

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定

 

快速排序

1.以数组第一位为基准值，将小于的元素放在左边，大于的元素放在右边，分为左右两块。

2.在左右2块中重复第一步，不断循环，直到分区的大小为1则停止。

图解

注意左右分区，我们可以通过将基准元素和左边分区最右端元素交换实现

js实现

function swap(arr, x, y) 
    let tmp = arr[x]
    arr[x] = arr[y]
    arr[y] = tmp

//用于一次以基准值进行排序
function partition(arr, left, right) 
    //设定基准值pivot
    let pivot = left
    let index = pivot + 1
    for (let i = index; i <= right; i++) 
        //小于基准值的放左边，大于的不变
        if (arr[i] < arr[pivot]) 
            swap(arr, i, index)
            index++
        
    
    //和小于基准值的最右边一个交换位置，实现左边小于基准值，右边大于基准值
    swap(arr, pivot, index - 1)
    //返回基准值的位置
    return index - 1

function quickSort(arr, left, right) 
    let len = arr.length
    left = typeof left != 'number' ? 0 : left
    right = typeof right != 'number' ? len - 1 : right
    if (left < right) 
        //进行一次排序
        let partitionIndex = partition(arr, left, right)
        //递归对左边进行排序
        quickSort(arr, left, partitionIndex - 1)
        //递归对右边进行排序
        quickSort(arr, partitionIndex + 1, right)
    
    return arr

console.log(quickSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特点

1. 时间复杂度：O(N*logN)
2. 空间复杂度：O(logN)
3. 稳定性：不稳定

选择排序

直接选择排序

每一次遍历待排序的数据元素从中选出最小（或最大）的一个元素，存放在序列的起始（或者末尾）位置（和原存放位置上的元素交换顺序），直到全部待排序的数据元素排完。

图解

 js实现

//交换数组下标x位和y位的元素
function swap(arr, x, y) 
    arr[x] = arr[x] - arr[y]
    arr[y] = arr[y] + arr[x]
    arr[x] = arr[y] - arr[x]
    return arr

function selectionSort(arr) 
    let t = arr.length
    let x = 0
    while (x != t) 
        let min = 0;
        let tmp = Number.MAX_VALUE
        //选出最小的元素的下标
        for (let i = x; i < t; i++) 
            if (tmp > arr[i]) 
                tmp = arr[i]
                min = i
            
        
        //不是当前位置，则交换顺序
        if (x != min) 
            swap(arr, x, min)
        
        x++
    
    return arr

console.log(selectionSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特点

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

堆排序

1.将元素排序为一个大（小）顶堆，则顶部元素为最大（小）元素，将其与元素尾（头）部元素交换顺序。

2.重新排序剩下元素，再次形成大（小）顶堆，重复1操作，直到只剩一个元素。

大（小）顶堆

每个节点的值都大于（小于）或等于其子节点的值，在堆排序算法中用于升（降）序排列；

代码中表示为：

大顶堆arr[i]>=arr[2i+1]和arr[i]>=arr[2i+2]        父节点大于左右子节点

小顶堆arr[i]<=arr[2i+1]和arr[i]<=arr[2i+2]         父节点小于左右子节点

非叶节点

有孩子节点的节点。最后一个非叶节点在数组中的序号为元素个数除以2向下取整。

js实现 

// 建立大顶堆
function buildMaxHeap(arr) 
    let len = arr.length;
    //Math.floor(len/2)表示最后一个非叶节点（含有子节点的节点），
    //从后往前调整每一个非叶子节点的顺序，使堆变为大顶堆
    for (let i = Math.floor(len / 2); i >= 0; i--) 
        heapify(arr, i, len);
    

// 调整堆
function heapify(arr, i, len) 
    let left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
    //通过2次判断选出父节点和2个子节点中最大的一个
    if (left < len && arr[left] > arr[largest]) 
        largest = left;
    
    if (right < len && arr[right] > arr[largest]) 
        largest = right;
    
    //将最大的节点和父节点交换顺序
    if (largest != i) 
        swap(arr, i, largest);
        //递归对换顺序的节点进行调整，使其还是大顶堆
        heapify(arr, largest, len);
    

function swap(arr, i, j) 
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;

function heapSort(arr) 
    // 建立大顶堆
    buildMaxHeap(arr);
    let len = arr.length
    //每次建立一个大顶堆，将最大的元素（堆顶元素）放入尾部达到排序效果
    for (let i = len - 1; i > 0; i--) 
        swap(arr, 0, i);
        len--;
        heapify(arr, 0, len);
    
    return arr;

console.log(heapSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特点

1. 时间复杂度：O(N*logN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

 

插入排序 

直接插入排序

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序（默认是从后向前比较）。

图解

蓝色部分为无序表，黄色部分为有序表：

js实现 

使用的是一个数组，将数组下标为i之前的为有序，之后为无序。

 注意用的是改变原数组的方法，可以不用返回。

//将数组下标为的x元素取出插入为y的
function popInsert(arr,x,y)
    arr.splice(y,0,...arr.splice(x,1))

function insertSort(arr)
    let t=arr.length
    for (let i=1;i<t;i++)
        let j=i-1
        do
            if(arr[j]<arr[i])
                popInsert(arr,i,j+1)
                break
            
            j--
            //比较到下标为0的时候直接插入
            if(j<0)
                popInsert(arr,i,0)
            
        while(j>=0)
    
    return arr

console.log(insertSort([3,1,2,3134,113,342,123412,55,111,4,234,5,5]))

特点

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

 

希尔排序

希尔排序在直接排序之前，进行预排列，将某些极端数据更快的排列到数列前面，构成一个接近排列好的序列，最后再进行一次直接插入排序。

预排列的原理也是插入排列，只不过这里的将数组分成了gap组，分别对每一个小组进行插入排序。

图解

对于升序，当gap从5 – 2 – 1的过程中，排在后面的数值小的数能更快排到前面，当gap为1的时候实际上就是进行了一次插入排序

js实现

每次将下标位置差为gap的数进行直接排序，其中第一次gap=Math.floor(arr.length/2)，之后每次gap=Math.floor(gap/2)。

function shellsSort(arr)
    let t=arr.length
    let gap=t
    let tmp
    //gap取不同值的排序
    do
        //每次的分组
        gap=Math.floor(gap/2)
        for(let i=gap;i<t;i++)
            //只和上一个间距为gap的元素进行比较，判断是否要插入，还是维持原顺序
            if(arr[i-gap]>arr[i])
                tmp = arr[i]
                let j=i-gap
                //将插入位置之后的元素整体后移
                do
                    arr[j+gap]=arr[j]
                    j-=gap
                while(j>=0&&arr[j]>tmp)
                //插入对应位置
                arr[j+gap]=tmp
            
        
    while(gap>1)
    return arr

console.log(shellsSort([3,1,2,3134,113,342,123412,55,111,4,234,5,5]))

 

特点

1. 希尔排序是对直接插入排序的优化当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比
2. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，一般来说为O(n^1.3) 
3. 稳定性：不稳定

其它排序

桶排序

选出待排序元素中的最大最小值，根据最大最小值划分多个区域（桶），通过映射函数将元素分到不同区域（桶）中，对区域（桶）中的元素进行排序后，依次取出即可。

图解

将排序的元素放入对应的桶中

 对桶中的元素进行排序

js实现

//插入排序
function insertionSort(arr) 
    let len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) 
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) 
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        
        arr[preIndex + 1] = current;
    
    return arr;

function bucketSort(arr, bucketSize) 
    let minValue = arr[0];
    let maxValue = arr[0];
    //找到数组中的最大和最小值
    for (let i = 1; i < arr.length; i++) 
        if (arr[i] < minValue) 
            minValue = arr[i];
         else if (arr[i] > maxValue) 
            maxValue = arr[i];
        
    
    //桶的初始化
    let DEFAULT_BUCKET_SIZE = 5;
    // 设置一个桶能存储的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    //桶的个数
    let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    let buckets = new Array(bucketCount);
    for (let i = 0; i < buckets.length; i++) 
        buckets[i] = [];
    
    //利用映射函数将元素分配到各个桶中
    for (let i = 0; i < arr.length; i++) 
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    
    //删除arr数组中的所有元素
    arr.length = 0;
    for (let i = 0; i < buckets.length; i++) 
        // 对每个桶进行排序，这里使用了插入排序
        insertionSort(buckets[i]);
        // 将每个桶的数据从小到大拿出                    
        for (let j = 0; j < buckets[i].length; j++) 
            arr.push(buckets[i][j]);
        
    
    return arr;

console.log(bucketSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特点

1. 时间复杂度：O(N+K)
2. 空间复杂度：O(N+K)
3. 稳定性：稳定

基数排序

确定最大数的位数，先按第一位进行排序，在按第二位进行排序，直到按最后一位进行排序为止。

图解

js实现

function radixSort(arr) 
    let counter = [];
    //获取元素的最大位数
    let maxDigit = `$Math.max(...arr)`.length
    let mod = 10;
    let dev = 1;
    //从小到大依次对元素的每一位进行循环排序
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) 
        for (let j = 0; j < arr.length; j++) 
            //获取元素对应位上的数值
            let bucket = parseInt((arr[j] % mod) / dev);
            if (counter[bucket] == null) 
                counter[bucket] = [];
            
            //根据对应的数值，将元素放入对应的桶中
            counter[bucket].push(arr[j]);
        
        let pos = 0;
        //从0~9的桶中将元素取出，完成一次排序
        for (let j = 0; j < counter.length; j++) 
            let value = null;
            if (counter[j] != null) 
                while ((value = counter[j].shift()) != null) 
                    arr[pos++] = value;
                
            
        
    
    return arr;

console.log(radixSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5], 6))

特点

1. 时间复杂度：O(N*K)
2. 空间复杂度：O(N+K)
3. 稳定性：稳定

归并排序

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4. 重复步骤 3 直到某一指针达到序列尾；

5. 将另一序列剩下的所有元素直接复制到合并序列尾。

图解

 js实现

function mergeSort(arr)   // 采用自上而下的递归方法
    let len = arr.length;
    if (len < 2) 
        return arr;
    
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));

function merge(left, right) 
    let 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;

console.log(mergeSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5], 6))

特点

1. 时间复杂度：O(N*logN)
2. 空间复杂度：O(N)
3. 稳定性：稳定

计数排序

1.找出待排序的数组中最大和最小的元素

2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项

3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

图解

 js实现

function countingSort(arr) 
    let maxValue = Math.max(...arr)
    let bucket = new Array(maxValue + 1),
        sortedIndex = 0;
    arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (let i = 0; i < arrLen; i++) 
        if (!bucket[arr[i]]) 
            bucket[arr[i]] = 0;
        
        bucket[arr[i]]++;
    

    for (let j = 0; j < bucketLen; j++) 
        while (bucket[j] > 0) 
            arr[sortedIndex++] = j;
            bucket[j]--;
        
    

    return arr;

console.log(countingSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))

特点

1. 时间复杂度：O(N+K)
2. 空间复杂度：O(K)
3. 稳定性：稳定