十大排序算法

目录

基本介绍

十大排序算法时间复杂度 

冒泡排序

 排序原理

代码实现 

测试： 

选择排序

排序原理 

代码实现 

测试： 

​插入排序 

排序原理 

代码实现 

测试

​快速排序

排序原理 

 代码实现

测试 

希尔排序

排序原理 

代码实现 

测试 

归并排序

排序原理 

代码实现 

测试

​堆排序

 排序原理

 代码实现

 测试

---

基本介绍

十大排序算法分为比较类排序和非比较类排序；

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

包括插入排序（直接插入排序、希尔排序）、选择排序（直接选择排序、堆排序）、交换排序（冒泡排序、快速排序）、归并排序（二路归并排序、多路归并排序）

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

包括计数排序、基数排序、桶排序。

十大排序算法时间复杂度 

  n ：数据规模

  k ：进制数量

  d ：最大值的位数

  m ：桶的数量

冒泡排序

一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数

列已经排序完成。这个算法的名字由来是因为元素会经由交换慢慢“浮“到数列的顶端。

 排序原理

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

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应      该会是最大的数;

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

4. 重复步骤1~3，直到排序完成 

代码实现 

public class Bubble {
    /**
     * 对数组内的元素进行排序
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        //循环的次数取决于需要比较数组的长度
        for (int i = a.length - 1; i > 0; i--) {
            //从0索引开始，依次和后面的元素比较
            //j 0;
    }
    /**
     * 交换a数组中，索引i和索引j处的值
     *
     * @param a
     * @param i
     * @param j
     */
    public static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试： 

public class BubbleTest {
    public static void main(String[] args) {
        Integer[] arr = {26,25,35,3,13,39,21,28};
        Bubble.sort(arr);
        System.out.println("冒泡" + ":" + Arrays.toString(arr));
    }
}

选择排序

选择排序的思想其实和冒泡排序有点类似，选择排序可以看成冒泡排序的优化。

排序原理 

首先，找到数组中最大(小)的那个元素

其次，将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换);

再次，在剩下的元素中找到最大(小)的元素，将它与数组的第二个元素交换位置。如此往

复，直到将整个数组排序。

这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最大(小)者。

代码实现 

public class Selection {
    /**
     * 对数组内的元素进行排序
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        //循环次数取决于需要比较的元素个数
        //如果最后剩两个元素还要进行比较，如果只剩下一个，就不要用比较
        for (int i = 0; i <= a.length - 2; i++) {
            //记录最小元素的索引
            int index = i;
            for(int j = i+1;j<=a.length-1;j++){
                if(greater(a[index],a[j])){
                    index = j;
                }
            }
            //把最小值给第i个元素
            exch(a,i,index);
        }
    }
    /**
     * 判断v是否大于w
     *
     * @param v
     * @param w
     * @return
     */
    public static boolean greater(Comparable v, Comparable w) {
        int result = v.compareTo(w);
        return result > 0;
    }
    /**
     * 交换a数组中，索引i和索引j处的值
     *
     * @param a
     * @param i
     * @param j
     */
    public static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试： 

public class SelectionTest {
    public static void main(String[] args) {
        Integer[] arr = {26,25,35,3,13,39,21,28};
        Selection.sort(arr);
        System.out.println("选择:"+ Arrays.toString(arr));
    }
}

 

插入排序 

插入排序是一种简单直观且稳定的排序算法。

排序原理 

1. 把所有的元素分为两组，已经排序的和未排序的;

2. 找到未排序的组中的第一个元素，向已经排序的组中进行插入;

3. 倒叙遍历已经排序的元素，依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位;

代码实现 

public class Insertion {
    /**
     * 对数组内的元素进行排序
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        //插入排序默认第0个元素已经排好序，直接从第1个元素开始，直到最后一个元素
        for (int i = 1;i0;j--){
                //如果第j-1个元素大于第j个元素，就互换位置，否则进入下一个循环
                if(greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else {
                    break;
                }
            }
        }
    }
    /**
     * 判断v是否大于w
     *
     * @param v
     * @param w
     * @return
     */
    public static boolean greater(Comparable v, Comparable w) {
        int result = v.compareTo(w);
        return result > 0;
    }
    /**
     * 交换a数组中，索引i和索引j处的值
     *
     * @param a
     * @param i
     * @param j
     */
    public static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试

public class InsertionTest {
    public static void main(String[] args) {
        Integer[] arr = {26,25,35,3,13,39,21,28};
        Insertion.sort(arr);
        System.out.println("插入" + ":" + Arrays.toString(arr));
    }
}

快速排序

快速排序是对冒泡排序的一种改进，也是分治法的一个典型应用。

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序原理 

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分;

2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值;

3. 然后,左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值,将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了

 代码实现

public class Quick {
    //对数组内元素进行排序
    public static void sort(Comparable[] a){
        int start = 0;
        int end = a.length - 1;
        sort(a,start,end);
    }
    //对数组中从索引start到索引end之间的元素进行排序
    private static void sort(Comparable[] a,int start,int end){
        //安全性校验
        if(end <= start){
            return;
        }
        //对a数组进行切分，分成左子组和右子组
        int partition = partition(a, start, end);
        //让左子组有序
        sort(a,start,partition-1);
        //让右子组有序
        sort(a,partition+1,end);
    }
    //对数组中从索引start到索引end之间的元素进行分组，返回分组界限对应的索引
    public static int partition(Comparable[] a,int start,int end){
        //记录分界值
        Comparable key = a[start];
        //定义两个指针,分别指向待切分数组的最小索引处和最大索引处的下一个位置
        int left = start;
        int right = end + 1;
        while (true){
            //先移动右指针，直到找到比分界值小的元素
            while (less(key,a[--right])){
                if (right == start){
                    break;
                }
            }
            //再移动左指针，直到找到比分界值大的元素
            while (less(a[++left],key)){
                if(left == end){
                    break;
                }
            }
            //判断left是否大于等于right,如果是，说明扫描完成，结束循环，如果不是，交换元素
            if (left>=right){
                break;
            }else {
                exch(a,left,right);
            }
        }
        //更新分界值
        exch(a,start,right);
        return right;
    }
    //判断v是否小于w
    private static boolean less(Comparable v,Comparable w){
        int result = v.compareTo(w);
        return result < 0;
    }
    //交换a数组中，索引i和索引j处的值
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试 

public class QuickTest {
    public static void main(String[] args) {
        Integer[] arr = {26,25,35,3,13,39,21,28};
        Quick.sort(arr);
        System.out.println("快速" + ":" + Arrays.toString(arr));
    }
}

我们可以使用事后分析法对冒泡排序、选择排序和快速性能比较 

package linearTest;
import linear.*;
import java.util.ArrayList;
/**
 * @Description:
 * @ClassName: TestShellAndInsertion
 * @Author: 康小汪
 * @Date: 2024/1/29 17:29
 * @Version: 1.0
 */
public class TestSelectionAndBubble {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        for (int i = 10000;i>=0;i--){
            list.add(i);
        }
        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        //selection(a);
        bubble(a);
        //quick(a);
    }
    public static void bubble(Integer[] a){
        //获取执行之前的时间
        long start = System.currentTimeMillis();
        //执行算法
        Bubble.sort(a);
        //获取执行之后的时间
        long end = System.currentTimeMillis();
        //计算执行时间并输出
        System.out.println("冒泡排序执行时间:" + (end - start) + "ms");
    }
    public static void selection(Integer[] a){
        //获取执行之前的时间
        long start = System.currentTimeMillis();
        //执行算法
        Selection.sort(a);
        //获取执行之后的时间
        long end = System.currentTimeMillis();
        //计算执行时间并输出
        System.out.println("选择排序执行时间:" + (end - start) + "ms");
    }
    public static void quick(Integer[] a){
        //获取执行之前的时间
        long start = System.currentTimeMillis();
        //执行算法
        Quick.sort(a);
        //获取执行之后的时间
        long end = System.currentTimeMillis();
        //计算执行时间并输出
        System.out.println("快速排序执行时间:" + (end - start) + "ms");
    }
}

 

希尔排序

希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本

排序原理 

1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组;

2. 对分好组的每一组数据完成插入排序

3. 减小增长量，最小减为1,重复第二步操作。  

代码实现 

public class Shell {
    /**
     * 对数组内的元素进行排序
     */
    public static void sort(Comparable[] a) {
        //先确定增长量h
        int h = 1;
        while (h < a.length / 2) {
            h = 2 * h + 1;
        }
        //希尔排序
        while (h >= 1) {
            //确定待排序的元素
            for (int i = h; i < a.length; i++) {
                //把待排序的元素插入到有序数组中
                for (int j = i; j >= h; j -= h) {
                    if (greater(a[j], a[j - h])) {
                        //待排序的元素已经在对应的位置了，结束循环
                        break;
                    } else {
                        //交换元素
                        exch(a, j, j - h);
                    }
                }
            }
            //减小h
            h = h / 2;
        }
    }
    /**
     * 判断v是否大于w
     */
    public static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }
    /**
     * 交换a数组中，索引i和索引j处的值
     */
    public static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试 

public class ShellTest {
    public static void main(String[] args) {
        Integer[] arr = {26,25,35,3,13,39,21,28};
        Shell.sort(arr);
        System.out.println("希尔" + ":" + Arrays.toString(arr));
    }
}

我们可以使用事后分析法对希尔排序和插入排序性能比较

public class TestShellAndInsertion {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        for (int i = 100000;i>=0;i--){
            list.add(i);
        }
        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        //shell(a);
        insertion(a);
    }
    public static void shell(Integer[] a){
        //获取执行之前的时间
        long start = System.currentTimeMillis();
        //执行算法
        Shell.sort(a);
        //获取执行之后的时间
        long end = System.currentTimeMillis();
        //计算执行时间并输出
        System.out.println("希尔排序执行时间:" + (end - start) + "ms");
    }
    public static void insertion(Integer[] a){
        //获取执行之前的时间
        long start = System.currentTimeMillis();
        //执行算法
        Insertion.sort(a);
        //获取执行之后的时间
        long end = System.currentTimeMillis();
        //计算执行时间并输出
        System.out.println("插入排序执行时间:" + (end - start) + "ms");
    }
}

归并排序

 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

排序原理 

1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。

2. 将相邻的两个子组进行合并成一个有序的大组;

3. 不断的重复步骤2，直到最终只有一个组为止。

代码实现 

package linear;
/**
 * @Description:
 * @ClassName: Quick
 * @Author: 康小汪
 * @Date: 2024/1/29 16:06
 * @Version: 1.0
 */
public class Merge {
    //完成归并操作需要的辅助数组
    private static Comparable[] assist;
    /**
     * 对数组内元素进行排序
     */
    public static void sort(Comparable[] a) {
        //初始化辅助数组assist
        assist = new Comparable[a.length];
        //定义start和end变量，记录数组中的最小索引和最大索引
        int start = 0;
        int end = a.length - 1;
        //调用sort的重载方法，将数组从start到end索引的元素进行排序
        sort(a, start, end);
    }
    /**
     * 对数组中从索引start到索引end之间的元素进行排序
     */
    private static void sort(Comparable[] a, int start, int end) {
        //安全性校验
        if(start >= end ){
            return;
        }
        //对start到end之间的数组进行分组，分成两个组
        //定义一个变量，用来确定分组的界限
        int mid = start + (end - start) / 2;
        //分别对每个组进行排序
        sort(a, start, mid);
        sort(a, mid + 1, end);
        //最后把两个组合并
        merge(a, start, mid, end);
    }
    /**
     * 对数组中从索引start到索引mid为一个子组，从索引mid+1到end之间为一个子组，把子组合并成一个有序的大组
     */
    public static void merge(Comparable[] a, int start, int mid, int end) {
        //定义三个指针
        int ass = start;
        int p1 = start;
        int p2 = mid + 1;
        //遍历，移动p1指针和p2指针，比较对应索引处的值，谁小，就把谁放到辅助数组的对应索引处
        while (p1 <= mid && p2 <= end) {
            if (less(a[p1], a[p2])) {
                assist[ass++] = a[p1++];
            } else {
                assist[ass++] = a[p2++];
            }
        }
        //遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应元素放进辅助数组的对应索引处
        while (p1 <= mid) {
            assist[ass++] = a[p1++];
        }
        //遍历，如果p2指针没有走完，那么顺序移动p2指针，把对应元素放进辅助数组的对应索引处
        while (p2 <= end) {
            assist[ass++] = a[p2++];
        }
        //把辅助数组中的元素拷贝到原数组中
        for (int index = start; index <= end; index++) {
            a[index] = assist[index];
        }
    }
    //判断v是否小于w
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    //交换a数组中，索引i和索引j处的值
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试

public class MergeTest {
    public static void main(String[] args) {
        Integer[] arr = {26, 25, 35, 3, 13, 39, 21, 28};
        Merge.sort(arr);
        System.out.println("归并" + ":" + Arrays.toString(arr));
    }
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆具备以下特点

1)完全二叉树;

2)二叉树每个结点的值都大于或等于其左右子树结点的值称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

 排序原理

将待排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点(堆顶)就是序列中最大的元素，将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

 代码实现

package linear;
/**
 * @Description:
 * @ClassName: Heap
 * @Author: 康小汪
 * @Date: 2024/1/29 20:08
 * @Version: 1.0
 */
public class Heap {
    /**
     * 对数组内元素进行排序
     */
    public static void sort(Comparable[] a) {
        //获取数组的长度
        int arrLen = a.length;
        //初始化一个大顶堆
        for (int i = arrLen - 1; i > 0; i--) {
            initHeap(a, arrLen);
            //将堆顶元素和最后一个元素互换
            exch(a, i, 0);
            //最后一个元素就是最大值，不在参与计算
            arrLen--;
        }
    }
    /**
     * 构建大顶堆
     */
    public static void initHeap(Comparable[] a, int arrLen) {
        //判断最后一个叶子结点有几个孩子
        boolean hasTwoChild = (arrLen % 2) == 1 ? true : false;
        //从最后一个叶子节点构建大顶堆
        for (int i = (arrLen - 2) / 2; i >= 0; i--) {
            //如果最后一个叶子节点有两个孩子
            if (hasTwoChild) {
                //判断它的右孩子是否大于它，并且右孩子是否大于等于左孩子
                if (less(a[i], a[(i * 2) + 2]) && less(a[(i * 2) + 1], a[(i * 2) + 2])) {
                    exch(a, (i * 2) + 2, i);
                    //交换之后，我们将其调整成大顶堆
                    downAdjust(a, (i * 2) + 2, arrLen);
                }
                //判断它的左孩子是否大于它，并且左孩子是否大于等于右孩子
                else if (less(a[i], a[(i * 2) + 1]) && less(a[(i * 2) + 2], a[(i * 2) + 1])) {
                    exch(a, (i * 2) + 1, i);
                    //交换之后，我们将其调整成大顶堆
                    downAdjust(a, (i * 2) + 1, arrLen);
                }
            } else {
                if (less(a[i], a[(i * 2) + 1])) {
                    exch(a, (i * 2) + 1, i);
                }
                hasTwoChild = true;
            }
        }
    }
    /**
     * 判断v是否小于w
     */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    /**
     * 交换a数组中，索引i和索引j处的值
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    /**
     * 调整成大顶堆
     */
    private static void downAdjust(Comparable[] a, int i, int arrLen) {
        //如果传进来的是叶子结点，直接return
        if (i > (arrLen - 2) / 2) {
            return;
        } else if ((i * 2) + 2 >= arrLen) {
            //当只有左孩子时
            if (less(a[i], a[(i * 2) + 1])) {
                exch(a, (i * 2) + 1, i);
            }
        } else {
            //当只有右孩子时
            if (less(a[i], a[(i * 2) + 2]) && less(a[(i * 2) + 1], a[(i * 2) + 2])) {
                exch(a, (i * 2) + 2, i);
                downAdjust(a, (i * 2) + 2, arrLen);
            } else if (less(a[i], a[(i * 2) + 1]) && less(a[(i * 2) + 2], a[(i * 2) + 1])) {
                exch(a, (i * 2) + 1, i);
                downAdjust(a, (i * 2) + 1, arrLen);
            }
        }
    }
}

 测试

public class HeapTest {
    public static void main(String[] args) {
        Integer[] arr = {26,25,35,3,13,39,21,28};
        System.out.println("原数组" + ":" + Arrays.toString(arr));
        Heap.sort(arr);
        System.out.println("堆排序后" + ":" + Arrays.toString(arr));
    }
}