十大排序算法总结（java/JavaScript实现）

1830

冒泡排序

最简单的排序算法

时间复杂度

O(N²)

思路

对于每个元素i，若等于其后相邻的元素，则交换位置

代码

function bubbleSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        for(let j = 0; j < arr.length - 1 - i; j++){
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1);
            }
        }
    }
    console.log(arr);
}
function swap(arr,i,j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
bubbleSort([1,3,5,4,3,2,1,5,7,4,3,1])
复制代码
public class BubbleSort{
    public static void main(String[] rgs){
        int[] nums = {1,3,5,7,6,5,4,3,2,1,7};
        bubbleSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void bubbleSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){
            for(int j = 0; j < arr.length - 1 - i; j++){
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}
复制代码

选择排序

时间复杂度

O(n²)

思路

在每轮循环中，寻找未排序区间内最小的元素，与未排序区间的首元素交换，逐渐将整个区间整理为已排序区间

代码

function selectSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        let min = i;
        for(let j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        swap(arr,i,min);
    }
}
function swap(arr,i,j){
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
复制代码
public class SelectSort{
    public static void main(String[] args){
        int[] nums = {1,3,5,6,5,4,3,2,1};
        selectSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void selectSort(int[] nums){
        for(int i = 0; i < nums.length - 1; i++){
            int min = i;
            for(int j = i + 1; j < nums.length; j++){
                if(nums[j] < nums[min]){
                    min = j;
                }
            }
            swap(nums,i,min);
        }
    }
    public static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
复制代码

插入排序

时间复杂度

O(N²)

思路

将整个区间划分为两块，已排序和未排序。
从第1个元素开始，向前查找，若nums[i] < nums[i-1]，则交换位置

代码

function insertSort(nums){
    for(let i = 1; i < nums.length; i++){
        const temp = nums[i];
        let j = i;
        while(j > 0 && nums[j-1] > temp){
            nums[j] = nums[j-1];
            j--;
        }
        nums[j] = temp
    }
    console.log(nums);
}
复制代码
public class InsertSort{
    public static void main(String[] args){
        int[] nums = {1,3,5,7,2,4,6,8,7,6,5,4,3,2,1};
        insertSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void insertSort(int[] nums){
        for(int i = 1; i < nums.length; i++){
            int temp = nums[i];
            int j = i;
            while(j > 0 && nums[j-1] > temp){
                nums[j] = nums[j-1];
                j--;
            }
            nums[j] = temp;
        }
    }
}
复制代码

希尔排序

插入排序的优化版本

时间复杂度

  • 最坏时间复杂度：O(N²)，使用特殊希尔增量时为O(N*log²N)，小于O(N²)
  • 最优时间复杂度：O(N)
  • 平均时间复杂度：取决于希尔增量的选取

思路

希尔排序是对插入排序的优化。
在插入排序中，每次元素移动只能和相邻的元素交换，因此当一个较小元素出现在数组后方时，需要多次移动才能移到前端。
在希尔排序中，选取一个步长step，坐标相邻为step的元素组成一组。每个组内进行插入排序，这样可以实现元素的快速移动，避免插入排序中出现的极端情况。
步长的选择是希尔排序的重要部分，选择合理的步长可以降低时间复杂度，已知的最好步长序列是Sedgewick提出的(1, 5, 19, 41, 109,…)
实际编码中，可以用length/2作为起始步长，并逐渐减半

代码

function shellSort(nums){
    // 选取步长，每次减半
    for(let step = nums.length>>1; step >= 1; step = step>>1){
        // 向前插入排序
        for(let i = step; i < nums.length; i++){
            let temp = nums[i];
            let j = i;
            while(nums[j-step] > temp){
                nums[j] = nums[j-step];
                j -= step;
            }
            nums[j] = temp;
        }
    }
    console.log(nums);
}
复制代码
public class ShellSort{
    public static void main(String[] args){
        int[] nums = {1,3,5,7,6,5,4,3,2,1,7};
        sort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void sort(int[] nums){
        for(int step = nums.length / 2; step > 0; step /= 2){
            for(int i = step; i < nums.length; i++){
                int temp = nums[i];
                int j = i;
                while(j > 0 && nums[j-1] > temp){
                    nums[j] = nums[j-1];
                    j--;
                }
                nums[j] = temp;
            }
        }
    }
}
复制代码

快速排序

时间复杂度

O(N*logN)

思路

  1. 每轮将第一个元素作为标准v，将数组的区间分为两部分：大于v的和小于v的
  2. 找到v最终的坐标后，对前后两个部分递归调用quickSort进行排序

代码

JS版

function sort(arr){
    quickSort(arr,0,arr.length-1);
    return arr;
}

function quickSort(arr,start,end){
    if(start < 0 || end >= arr.length || start >= end)  return;
    const index = partition(arr,start,end);
    quickSort(arr,start,index-1);
    quickSort(arr,index+1,end);
}

function partition(arr,start,end){
    let left = start, right = end, p = start + 1;
    while(left < right){
        if(arr[p] < arr[start]){
            left++;
            p++;
        }else{
            swap(arr,p,right);
            right--;
        }
    }
    swap(arr,start,left);
    return left;
}

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

console.log(sort([1,3,5,7,8,6,4,2,1,4,5,6,3]))
复制代码

Java版

public class QuickSort{
    public static void main(String[] args){
        int[] arr = {1,3,5,7,9,8,6,4,2,4,7};
        quickSort(arr,0,arr.length-1);
        for(int n : arr)
            System.out.println(n);
    }
    public static void quickSort(int[] arr,int start,int end){
        if(start < 0 || end >= arr.length || start >= end) return;
        int index = partition(arr,start,end);
        quickSort(arr, start, index-1);
        quickSort(arr, index+1, end);
    }

    public static int partition(int[] arr, int start, int end){
        int left = start, 
            right = end,
            p = start + 1;
        while(left < right){
            if(arr[p] < arr[start]){
                p++;
                left++;
            }else{
                swap(arr,p,right);
                right--;
            }
        }
        swap(arr,start,left);
        return left;
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
复制代码

归并排序

分治法的经典应用

时间复杂度

O(N*logN)

思路

现将数组分成两个部分，将两个子数组分别排序后归并到一起，即为答案

代码

function sort(arr){
    mergeSort(arr,0,arr.length-1);
    console.log(arr);
}
function mergeSort(arr,start,end){
    if(end === start) return;
    let mid = Math.floor((end + start) / 2);
    mergeSort(arr,start,mid);
    mergeSort(arr,mid+1,end);
    merge(arr,start,mid,end);
}
function merge(arr,start,mid,end){
    let l = start, r = mid+1, temp = [];
    while(l <= mid && r <= end){
        if(arr[l] < arr[r]){
            temp.push(arr[l++]);
        }else{
            temp.push(arr[r++]);
        }
    }
    while(l <= mid){
        temp.push(arr[l++]);
    }
    while(r <= end){
        temp.push(arr[r++]);
    }
    for(let i = start; i <= end; i++){
        arr[i] = temp[i-start];
    }
}

sort([1,3,5,7,2,4,6,8,7,6,5,4,3,2,1])
复制代码
public class MergeSort{
    public static void main(String[] args){
        int[] nums = {1,3,5,7,2,4,6,8,7,6,5,4,3,2,1};
        mergeSort(nums,0,nums.length-1);
        for(int n : nums)
            System.out.println(n);
    }
    public static void mergeSort(int[] nums, int start, int end){
        if(start == end)    return;
        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, end);
    }
    public static void merge(int[] nums, int start, int mid, int end){
        int l = start, r = mid + 1, cur = 0;
        int[] temp = new int[end-start+1];
        while(l <= mid && r <= end){
            if(nums[l] < nums[r]){
                temp[cur++] = nums[l++];
            }else{
                temp[cur++] = nums[r++];
            }
        }
        while(l <= mid){
            temp[cur++] = nums[l++];
        }
        while(r <= end){
            temp[cur++] = nums[r++];
        }
        for(int i = start; i <= end; i++){
            nums[i] = temp[i-start];
        }
    }
}
复制代码

堆排序

时间复杂度

O(NlogN)

思路

  1. 将给定数组整理为一个大顶堆

    大顶堆：一种特殊的二叉树。对于每个节点，其子节点的值一定小于自身

  2. 将堆顶元素和堆中最后一个元素交换位置，将其视为移出大顶堆
  3. 将剩余元素重新整理为大顶堆
  4. 重复上述过程，直到堆中只有一个元素

代码

function heapSort(nums){
    // 构造大顶堆
    buildMaxHeap(nums);

    // 将大顶堆的堆顶元素与堆中最后一个元素交换位置，并移出大顶堆
    for(let i = nums.length-1; i > 0; i--){
        swap(nums,0,i);

        // 将剩余部分重新整理为大顶堆
        heapify(nums,0,i-1);
    }
    console.log(nums);
}

/**
 * 将数组构造成大顶堆
 */
function buildMaxHeap(nums){
    const len = nums.length;
    let leaf = len>>1;
    for(;leaf>=0; leaf--){
        heapify(nums,leaf,len-1);
    }
}

/**
 * 将nums数组的[0,len]区间内，以i为根节点的子树整理为大顶堆
 */
function heapify(nums,i,len){
    // 子节点指针，先指向左孩子
    let child = i*2+1;

    // 若超出范围，则返回
    if(child > len) return;

    // 若右孩子存在，将child指向子节点中较大的一个
    if(child < len && nums[child+1] > nums[child]){
        child++;
    }

    // 若子节点比根节点大，则交换两节点，递归调用heapify函数
    if(nums[child] > nums[i]){
        swap(nums,i,child);
        heapify(nums,child,len);
    }

}

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

heapSort([1,3,5,7,2,4,6,8,7,6,5,4,3,2,1])
复制代码
public class HeapSort{
    public static void main(String[] args){
        int[] nums = {1,3,5,7,2,4,6,8,7,6,5,4,3,2,1};
        HeapSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void HeapSort(int[] nums){
        buildMaxHeap(nums);
        for(int i = nums.length-1; i > 0; i--){
            swap(nums,0,i);
            heapify(nums,0,i-1);
        }
    }

    public static void buildMaxHeap(int[] nums){
        int len = nums.length;
        int leaf = len>>1;
        for(; leaf >= 0; leaf--){
            heapify(nums,leaf,len-1);
        }
    }

    public static void heapify(int[] nums, int root, int len){
        int child = root * 2 + 1;
        if(child > len) return;
        if(child < len && nums[child+1] > nums[child]){
            child++;
        }
        if(nums[child] > nums[root]){
            swap(nums,child,root);
            heapify(nums,child,len);
        }
    }
}
复制代码

计数排序

时间复杂度

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)

思路

计数排序是非比较算法。

  1. 首先确定数组的最大值。构造一个额外空间bucket，用于存放各个数据出现的次数
  2. 遍历数组，统计各个数据出现的次数
  3. 遍历bucket，将数字写入待排序数组nums

代码

function countSort(nums,max){
    const bucket = Array(max+1).fill(0);
    let index = 0;
    for(let item of nums){
        bucket[item]++;
    }
    for(let i = 0; i < bucket.length;i++){
        while(bucket[i] > 0){
            nums[index++] = i;
            bucket[i]--;
        }
    }
    console.log(nums);
}
复制代码
import java.util.Arrays;
public class CountSort{
    public static void main(String[] args){
        int[] nums = {1,3,5,7,2,4,6,8,7,6,5,4,3,2,1};
        countSort(nums,8);
        for(int n : nums)
            System.out.println(n);
    }
    public static void countSort(int[] nums, int max){
        int[] bucket = new int[max+1];
        int index = 0;
        Arrays.fill(bucket,0);
        for(int i:nums){
            bucket[i]++;
        }
        for(int i = 0; i <= max; i++){
            while(bucket[i] > 0){
                nums[index++] = i;
                bucket[i]--;
            }
        }
    }
}
复制代码

桶排序

时间复杂度

当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间，即O（n）

思路

  1. 现将数组分配到有限个桶内（尽量均匀分配）
  2. 对每个桶内的元素进行排序（递归调用桶排序或是用其他排序方法）
  3. 将桶内元素整合到待排序数组中

代码

function bucketSort(nums){
    if(nums.length <= 1)    return;
    // 数组中的最大值和最小值
    const min = Math.min(...nums);
    const max = Math.max(...nums);

    // 桶的体积，这里设置为5
    const bucketSize = 5;

    // 桶的数量
    const bucketNum= Math.floor((max - min) / bucketSize) + 1;

    // 用来存放每组数据的桶 
    const bucket = Array(bucketNum).fill(0).map(() => []);

    for(let n of nums){
        const idnex = Math.floor((n-min) / bucketSize);
        bucket[idnex].push(n);
    }
    let cur = 0;
    for(let i = 0; i < bucketNum; i++){
        if(bucket[i].length > 0){
            // 对桶内的元素进行排序，这里使用的是插入排序，可以选择用任何排序算法
            insertSort(bucket[i]);
            for(let j = 0; j < bucket[i].length; j++){
                nums[cur++] = bucket[i][j]
            }
        }
    }
    console.log(nums);
}
复制代码
import java.util.Arrays;
public class BucketSort{
    public static void main(String[] args){
        int[] nums = {1,3,5,7,2,4,6,8,7,6,5,4,3,2,1};
        bucketSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void bucketSort(int[] nums){
        int max = nums[0], min = nums[0];
        for(int i:nums){
            if(i > max) max = i;
            else if(i < min) min = i;
        }
        int bucketNum = 5, bucketSize = nums.length;
        int[][] bucket = new int[bucketNum][bucketSize];
        int[] bIndex = {0,0,0,0,0};
        for(int i=0;i<bucketNum;i++){
            Arrays.fill(bucket[i],-1);
        }
        for(int i: nums){
            int index = (i-min) / bucketSize - (i-min) % bucketSize == 0 ? 0 : 1;
            bucket[index][bIndex[index]++] = i;
        }
        int cur = 0;
        for(int i = 0; i < bucketNum; i++){
            Arrays.sort(bucket[i]);
            for(int n:bucket[i]){
                if(n != -1){
                    nums[cur++] = n;
                }
            }
        }
    }
}
复制代码

基数排序

只适用于整数、有限位数的小数、格式有规律的字符串（如日期）

思路

对于一些长度为n位的整数，共需从低位到高位进行n轮排序。
使用10个桶（bucket），分别代表该位数字是0-9的数据。
每轮循环中，进行分配和回收

  • 分配：将数据根据某一位的数字，分配到对应的bucket中
  • 回收：从每个bucket中依次回收所有数据，写入原数组中

在完成最后一趟回收后，原数组的更新完成。

代码

function radixSort(nums){
    // 求数字的长度
    const len = String(Math.max(...nums)).length;

    const bucket = Array(10).fill(0).map(() => []);
    
    for(let i = 0; i < len; i++){
        // 从最后一位开始，对每一位进行排序
        assign(bucket,nums,i);

        // 一轮排序完成后，进行回收
        recycle(bucket,nums);
    }
    console.log(nums)
}

function assign(bucket,nums,i){
    for(let n of nums){
        const bit = getBit(n,i);
        bucket[bit].push(n);
    }
}

function recycle(bucket,nums){
    let cur = 0;
    for(let i = 0; i < bucket.length; i++){
        for(let n of bucket[i]){
            nums[cur++] = n;
        }
        bucket[i] = [];
    }
}

/**
 * 获取数字n的从右数第i位，从0开始计
 */
function getBit(n,i){
    const str = String(n);
    const index = str.length - 1 - i;
    return index >= 0 ? Number(str[index]) : 0;
}

radixSort([99,189,204,357,100,121,156,80])
复制代码
import java.util.Arrays;
public class RadixSort{
    public static void main(String[] args){
        int[] nums = {999,189,204,357,100,121,156,800};
        radixSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void radixSort(int[] nums){
        int len = (nums[0] + "").length();
        int[][] bucket = new int[10][nums.length];
        for(int i = 0; i < 10; i++){
            Arrays.fill(bucket[i],-1);
        }
        for(int i = 0; i < len; i++){
            int[] cur = {0,0,0,0,0,0,0,0,0,0};
            assign(bucket, cur, nums, i);
            recycle(bucket, nums);
        }
    }
    public static void assign(int[][] bucket, int[] cur, int[] nums, int i){
        for(int n: nums){
            int bit = getBit(n,i);
            bucket[bit][cur[bit]++] = n;
        }
    }

    public static void recycle(int[][] bucket, int[] nums){
        int cur = 0;
        for(int i = 0; i < 10; i++){
            for(int n: bucket[i]){
                if(n != -1){
                    nums[cur++] = n;
                }
            }
            bucket[i] = new int[nums.length];
            Arrays.fill(bucket[i],-1);
        }
    }

    public static int getBit(int n, int i){
        int len = (n + "").length();
        if(len <= i) return 0;
        int x = n % (int)Math.pow(10,i);
        int y = n % (int)Math.pow(10,i+1);
        return (y - x) / (int)Math.pow(10,i);
    }
}
复制代码
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
前端
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4202
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3895
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3842
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
相关推荐
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
手摸手教你实现vue的动态路由（addRoute版）-一一网
手摸手教你实现vue的动态路由（addRoute版）
手摸手教你实现vue的动态路由（addRoute版）
4年前 3118
Unity实用功能之使用TextMeshPro组件-一一网
Unity实用功能之使用TextMeshPro组件
Unity实用功能之使用TextMeshPro组件
4年前 3062
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …-一一网
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …...
4年前 2847
Windi CSS 在 Vue3 + Vite 项目中的使用-一一网
Windi CSS 在 Vue3 + Vite 项目中的使用
Windi CSS 在 Vue3 + Vite 项目中的使用
3年前 2728
vue3 使用 qrcode.vue 生成二维码-一一网
vue3 使用 qrcode.vue 生成二维码
vue3 使用 qrcode.vue 生成二维码
4年前 2621
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云