十大经典排序算法(2022年11月12日更新)

1、冒泡排序

冒泡排序是接下来的十大排序中最简单的排序。

1.1 方法描述

简单来说，排序方法就是重复地走过要排序的数列，一次比较相邻的两个元素，如果顺序不满足从小到大(从大到小)，就将这两个元素交换，重复地进行，知道没有再需要交换。排序方式：In-place（需要申请额外空间-临时变量）

1.2 算法描述

1. 从第一个元素开始比较，比较相邻的元素。如果第一个比第二个大(小)，就交换他们两个。
2. 对每一对相邻元素做同样的工作，不断重复，直到排序完成。

1.3 动图描述

1.4 代码实现(Java语言)

• 从小到大排序：

package Sort;  // 自己定义的包

import java.util.Scanner;  // 导入的外部jar包

public class BubbleSort {
    public static void main(String[] args) {
        /**
         * 从小到大排序：
         */
        System.out.println("请输入十个数：");
        Scanner sc = new Scanner(System .in);
        int [] arr = new int[10];
        // 数组输入方法:(for循环)
        for (int i = 0;i < arr.length;i++){ 
            arr[i] = sc.nextInt();
        }
        
        // 双层for循环，第一层循环为每个数除了最后一个数，都要进行党的的一遍循环，故循环次数为（arr.length - 1）次.
        for (int i = 0; i <arr.length;i++){
            for (int j = 0;j<arr.length-i-1;j++){
         // 若两数相比，前数比后数大，因为从小到大排序，故将两个数进行交换。交换需要一个临时变量，用来当中介，进行交换。
                if (arr[j+1] < arr[j]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        System.out.println("从小到大排序为：");
        // 使用foreach循环进行输出已排序好的数组。
        for (int i:arr) {
            System.out.print(i+" ");
        }
   }
}

• 从大到小排序：

package Sort;  // 自己定义的包

import java.util.Scanner;  // 导入的外部jar包

public class BubbleSort {

    public static void main(String[] args) {       
        /**
         * 从大到小：
         */
        System.out.println("请输入十个数：");
        Scanner scanner = new Scanner(System.in);
        int [] arr = new int[10];
        for(int i = 0;i <arr.length;i++){
            arr[i] = scanner.nextInt();
        }
        for (int i = 0;i < arr.length; i++){
            for (int j = 0; j < arr.length - i - 1; j++){
         // 从大到小和从小到大排序基本相同，只有接下来交换的部分，当两数进行比较时，后数大于前数时，进行交换。
                if (arr[j+1] > arr[j]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("从大到小为：");
        for (int i:arr ) {
            System.out.print(i+" ");
        }
    }

1.5 算法分析

• 最好情况-- O(n)：
  初始数组就为从大到小(从小到大)，只需要比较 O(n)，n为数组的元素。
• 最坏情况--O(n²)：
  若需要数组为从小到大排序，初始数组为从大到小。最坏的情况就是初始数组为倒序排序，故最坏情况为 O(n²)。所以复杂度为 O(n²)
• 稳定性：
  稳定。

2、选择排序

选择排序是表现最稳定的排序算法之一。

2.1 方法描述

首先在未排序的序列中找到最小(大)元素，存放到排序序列中的起始位置。然后，再从剩余未排序的元素中继续找最小(大)元素，然后存放到已排序序列的末尾。一次类推，直到所有元素均排序完成。

2.2 算法描述

n个元素的通过直接选择排序经过n-1次选择排序得到有序结果。

1. 将数组分为无序区和有序区。初始无序区为所有未排数，有序区为空。
2. 第 i 趟排序开始时，当前有序区为[1~i-1]，无序区为[i ~ n]。每趟排序从当前无序区找出最小(最大)元素，将他与 无序区的第一个元素交换。每一趟排序，无序区减少一个元素，而有序区增加一个元素。
3. n-1趟结束，数组排序结束。

2.3 动图描述

2.4 代码实现(Java语言)

package Sort;

import java.util.Scanner;

public class SelectionSort {
    public static int[] SelectionSort(int[] array) {
        if (array.length == 0){
            return array;
        }
        for (int i = 0;i < array.length; i++){
            int minIndex = i;
            for (int j = i; j < array.length; j++){
                if (array[j] < array[minIndex]){   // 找到最小的数
                    minIndex = j;    // 将最小的数的索引保存
                }
            }
            // 将找到的最小数与无序区的第一个数进行交换
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }

       return array;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入十个数：");
        int [] arr = new int[10];
        for (int i = 0;i < arr.length; i++){
            arr[i] = scanner.nextInt();
        }
        int[] sort = SelectionSort(arr);
        System.out.println("从小到大排序为：");
        for (int i:sort) {
            System.out.print(i+" ");
        }
    }
}

2.5 算法分析

• 最佳情况：
  O(n²)
• 最坏情况：
  O(n²)
• 稳定情况：
  不稳定。

3、插入排序

插入排序的算法描述是一种简单直观的排序算法。

3.1 方法描述

大致排序方法与选择排序方法相似。仍然是把将排序的数组分为两个区，无序区和有序区。先把第一个元素列为有序区，拿出无序区第一个元素与有序区的元素进行比较，若小于(大于)有序区的元素，则将它插入该元素的后一个位置。所以，每进行一次操作，无序区减少一个元素，而有序区增加一个元素。循环上面的操作，直到无序区元素为空，则停止该操作，输出有序数组。

3.2 算法描述

1. 从第一个元素开始，该元素默认为有序区。
2. 取出下一个元素。在有序区从后向前扫描。
3. 如果有序区的元素大于(小于)新元素，将该元素移到下一个位置。
4. 重复上述三步，直到无序区为空为止，输出有序数组。

3.3 动图描述

3.4 代码实现(Java语言)

package Sort; 

import java.util.Scanner;

public class InsertSort {
    public static int[] InsertSort(int[] array) {
        
        if (array.length == 0){
            return array;
        }
        int current ;   // 临时变量 插入的数
        for (int i = 0; i < array.length - 1; i++){
            current = array[i+1];  // 每次循环 将无序区的第一个元素当作插入的数，也就是赋值给current 当作临时变量
            int perIndex = i; // 有序区的最后一个元素的索引值
            // 若有序区的最后一个元素的索引值大于等于0 且要插入的数小于有序区的最后一个元素的索引值，就进入这个while循环。这个循环的目的是为了保持current可以从后向前依次比较。执行第一次while循环，说明current的值一定小于有序区的最后一个元素，所以将最后一个元素赋值给后一个元素，将preIndex的值减一，再次进行while循环的判断。
            while (perIndex >= 0 && current < array[perIndex]){
            // 这步操作是为了保证有空余的地方给元素插入，且有序区的最后一个元素仍然是最后一个元素，但是插入元素后，索引值会加一。
                array[perIndex + 1] = array[perIndex];
                perIndex--;
            }
       /**
       *跳出while循环后，有两种情况：
       *   1、有序区的所有值都比较完成，则perIndex为-1，则将
       *current的值直接插入有序区的第一个位置，也就是索引为0，故
       *(-1+1).
       *   2、有序区的所有值没有比较结束，在中途发现了不满足条件的，
       *跳出循环。那就之间将current插入比较完成的索引的后面位置，故
       *(preIndex+1).
       */
            array[perIndex + 1] = current;
        }
        //for循环结束，数组排序完成，返回结果。
        return array;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入十个数：");
        int [] arr = new int[10];
        for (int i = 0;i < arr.length;i++){
            arr[i] = scanner.nextInt();
        }
        int[] insertSort = InsertSort(arr);
        System.out.println("从小到大排序为：");
        for (int i:insertSort) {
            System.out.print(i+" ");
        }
    }
}

3.5 算法分析

• 最佳情况:
  O(n)
• 最坏情况：
  O(n²)
• 平均情况：
  O(n²)

4、希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也可以称为缩小增量排序。

4.1 方法描述

首先确定增量序列，在希尔排序中建议一种增量序列，在大多数的希尔排序中，通常使用该种增量序列，故称为希尔增量，但这个增量并不是最优的。希尔增量：gap = length / 2，缩小增量继续以 gap = length / 2的方式，故增量序列表示为 {n/2，(n/2)/2，……，1}.每一次排序，按照gap的数字来分组，对每组使用直接插入排序算法排序。随着增量的逐渐减少，每组包含的元素就越多。当增量降至一时，每个元素全部被分为一组，算法终止。

4.2 算法描述

1. 确定增量序列。{n/2，(n/2)/2，……，1}.
2. 按增量序列，对序列进行排序。
3. 每趟排序，根据对应的增量，将待排序列分割成若干长度的子序列，分别对各子序列进行直接插入排序。仅增量为1时，整个序列作为一个子序列来处理。

4.3 动图描述

4.4 代码实现

package Sort;

import java.util.Scanner;

public class ShellSort {
    public static int[] ShellSort(int[] array) {
        int len = array.length;  // 数组长度
        int temp = 0;            // 中间值，临时变量
        int gap = len / 2;       // 希尔增量
        while (gap > 0){
            // 未排序的数组每一个元素都要依次被放到子序列中，进行排序
            for (int i = gap; i < len; i++){
                temp = array[i]; //将每个子序列中的元素赋值给临时变量，执行插入排序。      
                int preIndex = i - gap; // 子序列中temp前面的那个元素的索引
            // 子序列进行插入排序，过程于插入排序相似，具体可以看上面插入排序详解。
                while (preIndex >= 0 && array[preIndex] > temp){  
             array[preIndex + gap] = array[preIndex]; 
             preIndex -= gap;  
                }
                array[preIndex + gap] = temp;  
            }
            // 增量除2，进行下次循环。
            gap /= 2;
        }
        return array;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入十个数：");
        int [] arr = new int[10];
        for (int i = 0 ;i < arr.length; i++){
            arr[i] = scanner.nextInt();
        }
        int[] ints = ShellSort(arr);
        for (int i:ints) {
            System.out.print(i + " ");
        }
    }
}

4.5 算法分析

• 最佳情况：
  O(nlog₂ n)

• 最坏情况：

  O(nlog₂ n)

• 平均情况：

  O(nlog₂ n)